DAA: Dijkstra’s Algorithm (Shortest Path)

Dijkstra’s Algorithm (Shortest Path)

Dijkstra’s algorithm finds the shortest distance from a source to all the vertices in a graph. This algorithm is used in network protocols like IS-IS and OSPF(Open source shortest path first).

For example, Suppose we draw a graph in which nodes represent the cities, and weighted edges represent the driving distances between pairs of cities connected by a direct road. When Dijkstra’s algorithm is applied,  it gives the shortest route between one city and all other cities.

Visualization

Take a graph with weights on edges.

Select a vertex and assign all others as infinity from that vertex. Here the vertex chosen will be marked as 0.

Go to its adjacent vertex and change the length as the weight on that edge to that vertex.

If the adjacent path length is less than the new path length, we do not change.

The length of already visited vertices will not change.

The vertex with minimum path length will be visited, So we choose 5 before 7.

The rightmost vertex will change two times.

Repeat till all the vertex are visited.

Steps to implement the algorithm

Keeping the above steps in mind, let us look at the algorithm.

Algorithm

1.  To keep track of vertices included in the shortest-path, we create a set sptSet (shortest path set). Initially, the set is empty.
2.  Like the above illustration, declare all distance values as INFINITE. The picked vertex will have a distance of 0.
3. Until all the vertexes are in sptSet
4. Take a vertex u, not in the spSet, and has a minimum value and add to sptSet.
5. Change distance value of all adjacent vertices of u. To update the distance values, loop through all adjacent vertices. For every adjacent vertex v, if the sum of a distance value of u (from source) and weight of edge u-v is less than the distance value of v, then update the distance value of v.

NOTE

1. A vertex v will be in SPT if spset[v] is true.
2.  Array distance[]  stores the shortest distance of every vertex.

C++ code:

 #include <bits/stdc++.h>
 using namespace std;
 const int numberVertex = 10; // The number of vertex in graph
 // To get minimum distance from adjacent nodes
 int minDistance(int distance[], bool ShortestPathTree[])
 {
           // Initialise min
     int min = INT_MAX, min_index;
           // Iterate in adjacent vertices
     for (int vertex = 0; vertex < numberVertex; vertex++) {
         if (ShortestPathTree[vertex] == false && distance[vertex] <= min) {
             min = distance[vertex];
             min_index = vertex;
         }
     }
     return min_index;
 }
 void dijkstra_Algo(int graph[numberVertex][numberVertex], int source)
 {
     int distance[numberVertex]; // to keep minimum distance from source to the vertexes
     bool ShortestPathTree[numberVertex];
     for (int i = 0; i < numberVertex; i++) {
         distance[i] = INT_MAX;
         ShortestPathTree[i] = false;
     }
     distance[source] = 0; // Initially distance from source is 0
     for (int count = 0; count < numberVertex - 1; count++) {
         int u = minDistance(distance, ShortestPathTree);
         ShortestPathTree[u] = true;
         for (int vertex = 0; vertex < numberVertex; vertex++)
             if (ShortestPathTree[vertex] == 0 && graph[u][vertex] != 0 && distance[u] != INT_MAX && distance[u] + graph[u][vertex] < distance[vertex])
                 distance[vertex] = distance[u] + graph[u][vertex];
     }
     for (int i = 0; i < numberVertex; i++)
         cout << "Node " << i << "\t\t"
              << "Distance " << distance[i] << endl;
 }
 int main()
 { // Create the graph with numberVertex
     int graph[numberVertex][numberVertex] = { { 0, 14, 0, 7, 0, 0, 0, 8, 0, 10 },
         { 14, 0, 8, 0, 0, 0, 0, 11, 0, 0 },
         { 0, 8, 0, 7, 0, 4, 0, 0, 2, 0 },
         { 7, 0, 7, 0, 9, 12, 0, 0, 0, 5 },
         { 0, 0, 0, 9, 0, 0, 0, 0, 0, 0 },
         { 0, 0, 4, 0, 0, 0, 2, 0, 0, 11 },
         { 0, 0, 0, 12, 0, 2, 0, 1, 6, 15 },
         { 8, 11, 0, 0, 0, 0, 1, 0, 7, 0 },
         { 0, 0, 2, 0, 0, 0, 6, 7, 0, 0 },
         { 10, 0, 0, 5, 0, 11, 15, 0, 0, 0 } };
     dijkstra_Algo(graph, 0);
     return 0;
 } 

Output:

Uses:

1) It is used in Google Maps and finding Shortest Path.

2) Social networking.

3) Flight agenda.