# What is Dijkstra's algorithm?

Syed Hussain Abbas

Grokking the Behavioral Interview

### 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 + cost[3,5] < D?.

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 + cost[2, 3] < D? False

D+ cost[2,4] < D? 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 + cost[4, 5]<D? False

Next, it marks vertex 4 as visited.

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

D + cost[6,3] < D? 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

### Visualization 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[],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 = {                         { 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 