Given a source vertex s from set of vertices V in a weighted graph where all its edge weights w(u, v) are non-negative, find the shortest-path weights d(s, v) from given source s for all vertices v present in the graph.

**For example, **

We know that breadth-first search can be used to find shortest path in a unweighted graph or even in weighted graph having same cost of all its edges. But if edges in the graph are weighted with different costs, then BFS generalizes to **uniform-cost search**. Now instead of expanding nodes in order of their depth from the root, uniform-cost search expands the nodes in order of their cost from the root. A variant of this algorithm is known as Dijkstra’s algorithm.

Dijkstra’s algorithm is an algorithm for finding the shortest paths between nodes in a graph. For a given source node in the graph, the algorithm finds the shortest path between that node and every other node. It can also be used for finding the shortest paths from a single node to a single destination node by stopping the algorithm once the shortest path to the destination node has been determined.

Dijkstra’s Algorithm is based on the principle of relaxation, in which an approximation to the correct distance is gradually replaced by more accurate values until shortest distance is reached. The approximate distance to each vertex is always an overestimate of the true distance, and is replaced by the minimum of its old value with the length of a newly found path. It uses a priority queue to greedily select the closest vertex that has not yet been processed and performs this relaxation process on all of its outgoing edges.

Below is psedocode for Dijkstra’s Algorithm as per wikipedia.

function Dijkstra(Graph, source)

dist[source] = 0 // Initialization

create vertex set Q

for each vertex v in Graph

{

if v != source

{

dist[v] = INFINITY // Unknown distance from source to v

prev[v] = UNDEFINED // Predecessor of v

}

Q.add_with_priority(v, dist[v])

}

while Q is not empty

{

u = Q.extract_min() // Remove minimum

for each neighbor v of u that is still in Q

{

alt = dist[u] + length(u, v)

if alt < dist[v]

{

dist[v] = alt

prev[v] = u

Q.decrease_priority(v, alt)

}

}

}

return dist[], prev[]

For instance, consider below graph. We will start from vertex A. So vertex A has distance 0 and remaining vertices have undefined (infinite) distance from source. Let S be the set of vertices whose shortest path distances from source are already calculated.

Initially S = {} and we push source vertex to it. S = {A}.

We start from source vertex A and start relaxing A’s neighbors. Since vertex B can be reached from a direct edge from vertex A, we update its distance to 10 (weight of edge A-B). Similarly vertex E can be reached through a direct edge from A, so we update its distance from infinity to 3.

After processing all outgoing edges of A, we next consider vertex having minimum distance. B has distance of 10, E has distance 3 and all remaining vertices have distance infinity. So we choose E and push it into the Set S. Now our set becomes S = {A, E}. Next we relax E’s neighbors. E has 2 neighbors B and C. We have already found one route to vertex B through vertex A having cost 10. But if we visit vertex B through vertex E, we are getting even a cheaper route. i.e (cost of edge A-E + cost of edge E-B)= 3 + 1 = 4 < 10 (cost of edge A-B).

We repeat the process till we have processed all the vertices. i.e Set S become full

**C++ implementation –**

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 |
#include<bits/stdc++.h> using namespace std; // Number of nodes in the graph #define N 5 // data structure to store graph edges struct Edge { int source, dest, weight; }; // class to represent a graph object class Graph { public: // A array of vectors to represent adjacency list vector<Edge> adjList[N]; // Constructor Graph(vector<Edge> edges) { // add edges to the undirected graph for (unsigned i = 0; i < edges.size(); i++) { int source = edges[i].source; int dest = edges[i].dest; int weight = edges[i].weight; // insert at end adjList[source].push_back({source, dest, weight}); } } }; // data structure to store heap nodes struct Node { int vertex, weight; }; void printRoute(int prev[], int i) { if (i < 0) return; printRoute(prev, prev[i]); cout << i << " "; } // Comparison object to be used to order the heap struct comp { bool operator()(const Node lhs, const Node rhs) const { return lhs.weight > rhs.weight; } }; // Run Dijkstra's algorithm on given graph void shortestPath(Graph const& graph, int source) { // create min heap and push source node having distance 0 priority_queue<Node, vector<Node>, comp> minHeap; minHeap.push({source, 0}); // set infinite distance from source to v initally vector<int> dist(N, INT_MAX); // distance from source to itself is zero dist[source] = 0; // boolean array to track vertices for which minimum // cost is already found bool done[N] = {0}; done[0] = 1; // stores predecessor of a vertex (to print path) int prev[N] = {-1}; // run till minHeap is not empty while (!minHeap.empty()) { // Remove and return best vertex Node node = minHeap.top(); minHeap.pop(); // get vertex number int u = node.vertex; // do for each neighbor v of u for (auto i : graph.adjList[u]) { int v = i.dest; int weight = i.weight; // Relaxation step if (!done[v] && (dist[u] + weight) < dist[v]) { dist[v] = dist[u] + weight; prev[v] = u; minHeap.push({v, dist[v]}); } } // marked vertex u as done so it will not get picked up again done[u] = 1; } for (int i = 1; i < N; ++i) { cout << "Path from vertex 0 to vertex " << i << " has minimum " "cost of " << dist[i] << " and the route is - "; printRoute(prev, i); cout << endl; } } // main function int main() { // initalize edges as per above diagram vector<Edge> edges = { {0, 1, 10}, {0, 4, 3}, {1, 2, 2}, {1, 4, 4}, {2, 3, 9}, {3, 2, 7}, {4, 1, 1}, {4, 2, 8}, {4, 3, 2} }; // construct graph Graph graph(edges); shortestPath(graph, 0); return 0; } |

**Output: **

Path from vertex 0 to vertex 1 has minimum cost of 4 and the route is – 0 4 1

Path from vertex 0 to vertex 2 has minimum cost of 6 and the route is – 0 4 1 2

Path from vertex 0 to vertex 3 has minimum cost of 5 and the route is – 0 4 3

Path from vertex 0 to vertex 4 has minimum cost of 3 and the route is – 0 4

Dijkstra’s algorithm runs in **O(E log V) time** like Prim’s algorithm. Here E is the number of edges and V is number of vertices in the graph.

**References:**

https://en.wikipedia.org/wiki/Dijkstra%27s_algorithm

www.cse.unt.edu/~tarau/teaching/AnAlgo/Dijkstra’s%20algorithm.pdf

**Thanks for reading.**

Please use ideone or C++ Shell or any other online compiler link to post code in comments.

Like us? Please spread the word and help us grow. Happy coding 🙂

## Leave a Reply