Single source shortest path : Dijkstra’s algorithm
Introduction
Similar to Prim’s minimum spanning tree, we generate the shortest path tree with a given source as a root node. In this algorithm, we will be maintaining two sets:
- i) One set will contain the vertices that are included in the shortest-path tree.
- ii) Another set will include the vertices that are not yet included in the shortest-path tree.
A step that we perform at every step of the algorithm is that we find a vertex that is in the other set, that is, the set of vertices that are not yet included and also has a minimum distance from the source.
Below are the steps of Dijkstra’s algorithm that are explained in detail in order to find out the shortest path from a single source vertex to all other vertices in the given graph.
Algorithm:
1) Create a shortest-path tree set – sptSet. The set must be such that it maintains a track of all the vertices that are included in the shortest-path tree, that is, whose minimum distance from the source is calculated and then finalized. Initially, this set will be empty.
2) All the vertices present in the input graph are assigned with a distance value. We will be initializing all distance values as INFINITE. The source vertex must be assigned a distance value of 0 so that it is picked first.
3) While sptSet doesn’t include all vertices
a) Pick a vertex u that is not present in sptSet and has a minimum distance value.
b) Include u to sptSet.
c) Next, we have to update the distance values of all the vertices that are adjacent to u. In order to update the distance values, we will iterate through all the adjacent vertices. For every adjacent vertex(call it v), if the sum of a distance value u from the source and the weight of edge u-v, is less than the distance value of v, then we have to update the distance value of v.
Example:
The sptSet is initially set as empty, the distances assigned to the vertices will be as follows:
{0, INF, INF, INF, INF, INF, INF, INF}
Here, INF will indicate an infinite value. We start by picking the vertex with a minimum distance value. Vertex 0 is picked first and is included in sptSet.
So, sptSet will now become {0}. After including vertex 0 to sptSet, we have to update the distance values of its adjacent vertices. We can see that the vertices adjacent to 0 are 1 and 7. Hence, the distance values of 1 and 7 will be updated as 4 and 8.
The following subgraph shows us the vertices and their respective distance values. In the graph, we only show the vertices that have finite distance values. The vertices included in the shortest-path tree are shown in green color.
Pick the vertex with minimum distance value and also that is not included in the shortest path tree (not present in sptSET). The vertex 1 will be picked and will be added to sptSet.
So, sptSet will become {0, 1}. Now, we have to update the distance values of the adjacent vertices of 1. The distance value of vertex 2 will become 12.
Pick the vertex with minimum distance value and also that is not included in the shortest path tree (not present in sptSET). Vertex 7 will be picked. So, sptSet will now become {0, 1, 7}.
Now, we have to update the distance values of the adjacent vertices of 7. The distance value of vertex 6 and 8 becomes finite now, that is they will be 15 and 9 respectively.
Pick the vertex with minimum distance value and also that is not included in the shortest path tree (not present in sptSET). Vertex 6 is picked that way. So, sptSet currently would be {0, 1, 7, 6}.
Now, we have to update the distance values of the adjacent vertices of 6. The distance values of vertex 5 and 8 will be updated.
The above steps are repeated until sptSet includes all the vertices that are present in the given graph. We finally get the following Shortest Path Tree.
How to implement the above algorithm?
In order to implement the above algorithm, we use a boolean array sptSet[]. This array is used to represent the set of vertices that are included in the shortest path tree. If the value of sptSet[v] is true, then vertex v is included in the shortest path tree, else it is not included. Another array dist[] is used to store the values of the shortest distance of all vertices.