Dijkstra Single-Source Shortest Path
When visualizing networks, different graph traversal algorithms are needed. Implementing the
Dijkstra algorithm is intended to review techniques that any computer science student
already knows.
Description
If the weights are positive, the Dijkstra algorithm solves the single-source shortest path problem.
The implementation requires a priority queue.
Main Idea
-
propagate along the shortest paths, i.e., follows the path to the node with the shortest distance
to the source node
-
once a node was visited, i.e., popped out of the priority queue, its distance to the source node is
known and will not be changed anymore
-
a path is followed if there is no other path with a shorter distance to the source node
-
once a node is reached, the computed distance is the shortest distance to the source node
Remarks
-
the distance update step is called relaxation
-
Once a node is popped out of the queue, the algorithm will no longer change its distance. Therefore,
Dijkstra is a greedy algorithm: it chooses the best option at each step.
-
The Dijkstra algorithm finds the shortest path, i.e., it solves the optimization problem of the single-source
shortest path.
-
An implementation based on a Fibonacci heap for the priority queue has time complexity
\(\mathcal{O}(m + n \log n)\), where \(n = |V(G)|\), and \(m = |E(G)|\).
Note:
Select and click a node to start a traversal. Click the background to reset. Depth is measured using the
weights of the edges and visualized using colors. Nodes of the same color are at the same distance from
the selected source node. You can select a breadth-first traversal to compare the results. The numbers
at the edges are the corresponding weights.
The JavaScript Code