Trusted answers to developer questions

What is Dijkstra's algorithm?

Syed Hussain Abbas

Grokking the Behavioral Interview

Get Educativeâ€™s popular interview prep course for free.

Overview

Dijkstra's algorithm is a greedy algorithm designed by Edsger W. Dijkstra. It computes the shortest path of all the nodes/vertices of a graph from a particular node/vertex selected by the user. This algorithm can work on both directed and undirected graphs.

How does it work?

Dijkstra's algorithm employs an iterative process. Since it's a greedy algorithm, it looks for the current shortest path. It also employs relaxation, whereby it updates the distances based upon the cumulative shortest distance.

Algorithm steps

This algorithm performs these functions in the following steps:

Initial step:

• Maintain an array of distances D[v], where v = number of vertices.
• Maintain an array of the visited vertices V[].
• Select a vertex. This will be the starting vertex.
• Initialize the distance array with the maximum possible value.
• Update the distance of the selected vertex from 0.
• Update the distances of its neighbors according to their respective edge costs.

Repeating step:

• Select the neighbor with the shortest path from the current vertex.
• Update the current vertex.
• Add the previous vertex to the visited array V[].
• For all the neighbors of the current vertex, check whether D[current_vertex] + cost[current_vertex, neighbour] < D[neighbor]. This is the relaxation step.
• Repeat until all the vertices are visited.

At the end of these steps, we expect to obtain a final output of all the vertices with their respective shortest distances from the selected vertex.

Example

Initial step:

The algorithm selects vertex 1 as the starting vertex. The distance of all the non-connected vertices is set to the maximum value, while the distances of the connected vertices are set to the cost of their respective edges.

First iteration:

The algorithm selects vertex 3 next since it has the shortest distance currently. It then adds vertex 1 to the visited array. It then applies relaxation: D[3] + cost[3,5] < D[5]?.

The distance of 5 will be updated to 3. The algorithm then checks for the shortest distance between the unvisited vertices (2, 4, 5, and 6) and selects vertex 5.

Second iteration:

Next, it adds vertex 3 to the visited array. Relaxation is applied again and the distance of vertex 6 is updated to 12.

After checking the shortest distances of the unvisited vertices (2, 4, and 6) again, the algorithm next selects vertex 2 and marks vertex 5 as visited.

Third iteration:

Next, it applies the relaxation step to both vertex 3 and vertex 4 since there are now two outgoing edges from vertex 2:

D[2] + cost[2, 3] < D[3]? False

D[2]+ cost[2,4] < D[4]? True

Only the distance of vertex 4 is updated to 5. Out of the unvisited vertices (4 and 6), the algorithm selects vertex 4 based on the shortest distance and marks vertex 2 as visited.

Fourth iteration:

Next, it checks relaxation on vertex 5 since it is the only outgoing edge from vertex 4:

D[4] + cost[4, 5]<D[5]? False

Next, it marks vertex 4 as visited.

Finally, it selects vertex 6 and performs relaxation on vertex 3:

D[6] + cost[6,3] < D[3]? False.

Fifth iteration:

Again, it marks vertex 6 as visited.

Output

The following table shows the vertices along with their corresponding shortest distances from the starting vertex:

 Vertex Distance(D[V]) 1 0 2 4 3 2 4 5 5 3 6 12

Initial step
1 of 8

Implementation

#include<iostream>#include <bits/stdc++.h>using namespace std;//Total vertices in graphint vertices=6;//function to print final outputvoid printDistances(int* distances){    cout<<"Vertex:         Distance from start vertex:"<<endl;    for(int i=0;i<vertices;i++){        cout<<i<<"                     "<<distances[i]<<endl;    }}//Dijkstra's Algovoid dijkstra_algo(int edges[][6],int starting_vertex){    //array to keep record of visited vertices    bool* visited = new bool[vertices];    //array to keep record of distances of each vertex from starting vertex    int* distances = new int[vertices];              //Initial Step: set infinite as distance in all vertices except     //starting vertex where distance is kept 0    for(int i = 0; i<vertices; i++){        distances[i] = INT_MAX;        visited[i] = false;        }        distances[starting_vertex] = 0;           //Repeating Step    int cur_vertex;    //for all vertices    for(int i = 0; i<vertices; i++){        // get next vertex to traverse: current shortest path from starting vertex                int min=INT_MAX;                      for(int j = 0; j < vertices; j++){            if(distances[j]<=min && visited[j]==false){                min=distances[j];                cur_vertex=j;            }        }        //set current vertex as visited        visited[cur_vertex]=true;        for(int k = 0; k < vertices; k++){            //Firstly, get those vertices which haven't been visited yet and have an edge            //with the current_index            //these are neighbors of the current_vertex            // perform relaxation on these neighbors            if(visited[k]==false && edges[cur_vertex][k]  && distances[cur_vertex]+edges[cur_vertex][k]<distances[k]){                distances[k]=distances[cur_vertex]+edges[cur_vertex][k];            }        }    }    printDistances(distances);}int main() {  //adjacency matrix for edge costs.  //vertices are starting from 0.   int edges[6][6] = {                         { 0, 4, 2, 0, 0, 0 },                        { 0, 0, 6, 1, 0, 0 },                        { 0, 0, 0, 0, 1, 0 },                        { 0, 0, 0, 0, 7, 0 },                        { 0, 0, 0, 0, 0, 9 },                        { 0, 0, 3, 0, 0, 0 }                      };    dijkstra_algo(edges,0);  return 0;}

Time complexity

The algorithm is executed for all the vertices and at each step it performs relaxations. In case the graph is fully connected (worst-case scenario), the time complexity will be$O(V^2)$, where V represents the total number of vertices in the graph.

RELATED TAGS

CONTRIBUTOR

Syed Hussain Abbas
Trusted Answers to Developer Questions

Related Tags

Keep Exploring
Related Courses

Learn in-demand tech skills in half the time