Dijkstra’s Shortest Path Algorithm
Given a graph and a source vertex in the graph, find shortest paths from source to all vertices in the given graph.
One algorithm for finding the shortest path from a starting node to a target node in a weighted graph is Dijkstra’s algorithm. The algorithm creates a tree of shortest paths from the starting vertex, the source, to all other points in the graph.
Dijkstra’s algorithm, published in 1959 and named after its creator Dutch computer scientist Edsger Dijkstra, can be applied on a weighted graph. The graph can either be directed or undirected. One stipulation to using the algorithm is that the graph needs to have a nonnegative weight on every edge.
Simply put, Dijkstra’s algorithm finds the shortest path tree from a single source node, by building a set of nodes that have a minimum distance from the source.
The graph will have the following:
- vertices, or nodes; weighted edges that connect two nodes.
- In the diagram above, the weight for each edge is written in gray.
Begin by initializing three values:
- Distance, an array of distances from the source node ss to each node in the graph, initialized the following way: distance[start] = 0; and for all other nodes v, distdist(v) = ∞(infinity). This is done at the beginning because as the algorithm loops, the distance from the starting node to each node v in the graph will be recalculated and finalized when the shortest distance to finish is found.
- Q, a queue of all nodes in the graph. At the end of the algorithm’s progress, Q will be empty.
- S, an empty set, to indicate which nodes the algorithm has visited. At the end of the algorithm, S will contain all the nodes of the graph.
Implementation
- While Q is not empty, pop the node v, that is not already in S, from Q with the smallest distance (v). In the first run, the starting node will be chosen because distance was initialized to 0. In the next run, the next node with the smallest distance value is chosen.
- Add node v to starting, to indicate that v has been visited.
- Update distance values of adjacent nodes of the current node v as follows: for each new adjacent node:
if distance (v) + weight(u,v) < distance (u), there is a new minimal distance found for u, so update distance (u) to the new minimal distance value; otherwise, no updates are made to distance (u).
The algorithm has visited all nodes in the graph and found the smallest distance to each node. Distance now contains the shortest path tree from the starting node.
Let’s visualize this by using the above graph to implement the steps discussed.
- Initialize distances according to the algorithm.
2. Pick first node and calculate distances to adjacent nodes.
3. Pick next node with minimal distance; repeat adjacent node distance calculations.
4. Final result of shortest-path tree.
I’m hoping a visual representation helps to better understand why this algorithm is a perfect base point for many problems that require distance between points on a graph.
References:
