What is Dijkstra's algorithm?
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], wherev= 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.
Final output:
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 |
Visualization
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 verticesbool* visited = new bool[vertices];//array to keep record of distances of each vertex from starting vertexint* distances = new int[vertices];//Initial Step: set infinite as distance in all vertices except//starting vertex where distance is kept 0for(int i = 0; i<vertices; i++){distances[i] = INT_MAX;visited[i] = false;}distances[starting_vertex] = 0;//Repeating Stepint cur_vertex;//for all verticesfor(int i = 0; i<vertices; i++){// get next vertex to traverse: current shortest path from starting vertexint 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 visitedvisited[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 neighborsif(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 beV represents the total number of vertices in the graph.
RELATED TAGS
CONTRIBUTOR
