This tool lets you follow, one step at a time, how Dijkstra's algorithm finds the shortest paths from a source to every vertex in a weighted graph. Edit the list of edges and weights and the diagram and step table update immediately. You can explore the idea behind car navigation route search and network routing (OSPF) with a table in the same format as exam questions.
Favorites and recently used calculators are stored only in this browser (localStorage).
Results
Shortest distance
–
Shortest path
–
Vertex finalized in this step Finalized Updated in this step Shortest path
Step table
Each row shows the vertex finalized in that step (highlighted) and the distance to each vertex at that point. Parentheses show the previous vertex, red marks distances updated in that step, and finalized vertices are left blank.
Shortest distances to all vertices:
Weights are limited to 0 or more because Dijkstra's algorithm can give wrong answers when there are negative edges. When several vertices have the same distance, the one whose name comes first is finalized first. When there are several edges between the same two vertices, the one with the smaller weight is used.
See it as a graph
Other inputs stay at their current values while the chosen input varies from 1/4 to 4 times its current value. The red dot is the current value.
How Dijkstra's algorithm works
Dijkstra's algorithm finds the shortest distance from one source to every vertex in a weighted graph whose edges carry weights of 0 or more (distance, time or cost). First, set the source's distance to 0 and every other vertex's to ∞. Then pick the non-final vertex with the smallest distance and finalize it, and for each non-final vertex connected to it by an edge, update its distance if “distance of the finalized vertex + edge weight” is smaller than its current distance. Repeat until every vertex is final. In the example “Road network with 6 vertices”, A→C→E→D→F is the shortest path, with length 20.
Why it gives the right answer
If all edge weights are 0 or more, no other non-final vertex can lead to the non-final vertex with the smallest distance by a shorter route, because going through another vertex only adds a weight of 0 or more to a distance that is already at least as large. So the vertex's distance can be declared shortest the moment it is chosen. With negative edges this reasoning fails, so graphs with negative weights call for the Bellman–Ford algorithm or similar methods. In the example “A detour that is shorter”, you can see that the route along three edges (3) is shorter than the direct edge between S and T (5).
Complexity and where it is used
With V vertices and E edges, the straightforward method of searching all non-final vertices for the minimum each time takes O(V²), and using a heap (priority queue) gives O((V + E) log V). Dijkstra's algorithm is used in route search in car navigation and map apps, in the routing protocol OSPF (each router builds its routing table from link costs with Dijkstra's algorithm), and for character movement in games. For large graphs such as maps, improved versions such as A* search, which estimates the direction of the destination to narrow the search, are also used.
Step tables in exams
Exams often ask you to fill in a step table, to say in which step a given vertex is finalized, or to give a shortest distance. When building the table, write the vertex finalized and the distances updated in each step separately, and remember that finalized vertices never change afterward. The shortest path is found by following the “previous vertex” back from the destination; in this tool's table, the previous vertex is shown in parentheses.
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.
AThe graph has no cycles (paths that return to the same vertex)
BThe edges have no direction
CAll edge weights are 0 or greater
Show answer and explanation
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.
Breadth-first search visits vertices in order of distance: first those one edge from the start, then those two edges away, and so on. Adding each newly found vertex to the back of a queue and taking vertices from the front preserves this nearest-first order, so the number of edges when a vertex is first reached is the shortest. Depth-first search (using recursion or a stack) goes as far as it can along one path, so it may first reach a vertex by a roundabout route, and shortest distances are not guaranteed. Using a stack instead of a queue turns the traversal into something close to depth-first search.
AAn administrator configures routes on each router by hand, and the same routes stay in use after a failure until the configuration is changed
BRouters exchange route information using routing protocols and automatically switch to another path when a failure makes a route unusable
CA route is chosen at random for each packet to spread the load evenly over several paths
Show answer and explanation
Answer: B. Routers exchange route information using routing protocols and automatically switch to another path when a failure makes a route unusable
Static routing means an administrator configures routes by hand. It is simple and predictable, and suits small networks or the default route of a site with only one exit, but it does not switch over automatically after a failure. In dynamic routing, routers exchange information with routing protocols such as OSPF or BGP to build their routing tables automatically, and recalculate another path when a link fails. On the internet, routes between organizations' networks (autonomous systems) are exchanged with BGP. Real networks commonly combine both.
FAQ
What should I do when there are negative edges?
Dijkstra's algorithm cannot be used, so use the Bellman–Ford algorithm. It repeats distance updates over all edges (number of vertices − 1) times, which takes O(VE), more than Dijkstra's algorithm, but it handles negative weights and can also detect negative cycles (loops whose total weight decreases the distance each time round).
How does it differ from breadth-first search?
If all edges have the same weight, breadth-first search (BFS) finds the path with the fewest edges. Dijkstra's algorithm can be seen as an extension of breadth-first search that handles different weights by using a priority queue, which returns the smallest distance first, instead of a queue.
How do I find shortest distances between all pairs of vertices?
Either repeat Dijkstra's algorithm once from each vertex, or use the Floyd–Warshall algorithm. Floyd–Warshall uses a triple loop and takes O(V³), but the procedure is simple and it can also handle negative edges (as long as there are no negative cycles).
How is it related to OSPF?
OSPF is a routing protocol in which routers exchange the state of their links (connections and costs), each router keeps a map of the whole network, and each computes the shortest paths from itself with Dijkstra's algorithm. In the example “Network routing”, you can see the path with the smallest total cost being chosen.