Grokking the Behavioral Interview
Get Educativeâ€™s popular interview prep course for free.
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.
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.
This algorithm performs these functions in the following steps:
D[v]
, where v
= number of vertices.V[]
.V[]
.D[current_vertex]
+
cost[current_vertex, neighbour]
<
D[neighbor]
. This is the relaxation step.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.
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.
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.
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.
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.
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.
Again, it marks vertex 6 as visited.
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 |
#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;}
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