An algorithm that finds the shortest paths from one starting vertex to every vertex in a graph whose edge weights are 0 or greater. It repeatedly finalizes the nearest vertex whose distance is not yet final and updates the distances of its neighbors. It does not work correctly with negative edge weights.
Japanese name: ダイクストラ法
Dijkstra's algorithm appears in 3 practice questions across 1 topic, including Data Structures and Algorithms.
Set the distance of the start to 0 and all other vertices to infinity, and mark every vertex as not final. Pick the non-final vertex with the smallest distance, finalize it, and for each edge leaving it, update the distance of the vertex at the other end if “finalized distance + edge weight” is smaller than its current distance (relaxation). Repeat until every vertex is final. Recording the previous vertex at each update lets you trace the shortest path itself afterward.
Searching all vertices for the minimum each time takes O(V²) for V vertices. Using a priority queue based on a binary heap reduces this to O((V + E) log V), where E is the number of edges, which is much faster for sparse graphs such as road networks. The graph is usually stored as adjacency lists. Car navigation systems combine it with A* search, which adds an estimate of the remaining distance to steer the search toward the destination, and with speed-up techniques that use precomputed information.
Dijkstra's algorithm finalizes vertices on the assumption that going through other vertices can only increase a distance, never decrease it. With negative edges, a finalized distance can later become shorter, so correct answers are not guaranteed. When negative weights exist, the Bellman-Ford algorithm, which relaxes every edge V−1 times, is used; it can also detect negative cycles. For shortest paths between all pairs of vertices, the Floyd-Warshall algorithm (O(V³)), based on dynamic programming, is also used. In network routing, link-state protocols such as OSPF use Dijkstra's algorithm in each router to compute routes.
Answer: B. S→B→A→C→T, length 7
Dijkstra's algorithm repeatedly finalizes the nearest vertex whose distance is not yet final and updates the distances of its neighbors. From S (0), B is finalized at 1, and going through B gives A a distance of 1 + 2 = 3, shorter than the direct 4. Finalizing A (3) gives C 3 + 1 = 4 and T 3 + 6 = 9, and finalizing C (4) updates T to 4 + 3 = 7. The shortest path is therefore S→B→A→C→T with length 7. S→A→C→T (8) is longer because it takes S−A directly, and S→B→C→T (9) is longer because B−C has the large weight 5.
Answer: C. All edge weights are 0 or greater
Dijkstra's algorithm finalizes the unfinalized vertex with the smallest distance. This relies on the assumption that going through other vertices can only increase a distance, never decrease it. With a negative edge, a distance can become shorter later through another route; for example, in a directed graph with S→A 2, S→B 3 and B→A −2, A is finalized at 2 before the path S→B→A of length 1 is found. When negative weights exist, the Bellman-Ford algorithm or similar methods are used. Dijkstra's algorithm works with cycles and with directed edges as long as all weights are 0 or greater.
If every edge has weight 1, Dijkstra's algorithm finalizes vertices in the same order as breadth-first search. It can be seen as a generalization for different weights that replaces the queue with a priority queue returning the smallest distance first.
Yes. As long as the weights are 0 or greater, it finds correct shortest paths in directed and undirected graphs, including graphs with cycles.
Dijkstra's algorithm repeatedly finalizes the nearest vertex whose distance is not yet final and updates the distances of its neighbors.
In an undirected graph, the edge weights (distances) are S−…Dijkstra's algorithm finalizes the unfinalized vertex with the smallest distance.
Which condition on the graph is required for Dijkstra's alg…For processing that follows the edges out of each vertex in turn, such as breadth-first search and Dijkstra's algorithm, adjacency lists are more efficient.
Which is an appropriate way to store in memory a sparse gra…As an Amazon Associate I earn from qualifying purchases.
Breadth-first search Binary heap Binary search Binary search tree Depth-first search Dynamic programming Greedy algorithm Hash table Linked list Queue