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,

Path from vertex A to vertex B has minimum cost of 4 & the route is [ A -> E -> B ]

Path from vertex A to vertex C has minimum cost of 6 & the route is [ A -> E -> B -> C ]

Path from vertex A to vertex D has minimum cost of 5 & the route is [ A -> E -> D ]

Path from vertex A to vertex E has minimum cost of 3 & the route is [ A -> E ]

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++

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 134 135 136 137 138 139 140 |
#include <iostream> #include <vector> #include <queue> #include <climits> using namespace std; // Data structure to store graph edges struct Edge { int source, dest, weight; }; // data structure to store heap nodes struct Node { int vertex, weight; }; // class to represent a graph object class Graph { public: // An array of vectors to represent adjacency list vector<Edge> *adjList; // Constructor Graph(vector<Edge> const &edges, int N) { // allocate memory adjList = new vector<Edge>[N]; // add edges to the undirected graph for (Edge const &edge: edges) { // insert at end adjList[edge.source].push_back(edge); } } // Destructor ~Graph() { delete[] adjList; } }; void print_route(vector<int> const &prev, int i) { if (i < 0) return; print_route(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, int N) { // create min heap and push source node having distance 0 priority_queue<Node, vector<Node>, comp> min_heap; min_heap.push({source, 0}); // set infinite distance from source to v initially 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 vector<bool> done(N, false); done[0] = true; // stores predecessor of a vertex (to print path) vector<int> prev(N, -1); // run till min_heap is not empty while (!min_heap.empty()) { // Remove and return best vertex Node node = min_heap.top(); min_heap.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; min_heap.push({v, dist[v]}); } } // marked vertex u as done so it will not get picked up again done[u] = true; } 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 [ "; print_route(prev, i); cout << "]\n"; } } // main function int main() { // initialize 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} }; // Number of nodes in the graph int N = 5; // construct graph Graph graph(edges, N); shortestPath(graph, 0, N); return 0; } |

## Java

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 134 135 136 137 138 139 140 141 142 143 |
import java.util.*; // Data structure to store graph edges class Edge { int source, dest, weight; public Edge(int source, int dest, int weight) { this.source = source; this.dest = dest; this.weight = weight; } }; // Data structure to store heap nodes class Node { int vertex, weight; public Node(int vertex, int weight) { this.vertex = vertex; this.weight = weight; } }; // class to represent a graph object class Graph { // An array of Lists to represent adjacency list List<List<Edge>> adjList = null; // Constructor Graph(List<Edge> edges, int N) { adjList = new ArrayList<>(N); for (int i = 0; i < N; i++) { adjList.add(i, new ArrayList<>()); } // add edges to the undirected graph for (Edge edge: edges) { adjList.get(edge.source).add(edge); } } } class Dijkstra { private static void printRoute(int prev[], int i) { if (i < 0) return; printRoute(prev, prev[i]); System.out.print(i + " "); } // Run Dijkstra's algorithm on given graph public static void shortestPath(Graph graph, int source, int N) { // create min heap and push source node having distance 0 PriorityQueue<Node> minHeap = new PriorityQueue<>( (lhs, rhs) -> lhs.weight - rhs.weight); minHeap.add(new Node(source, 0)); // set infinite distance from source to v initially List<Integer> dist = new ArrayList<>( Collections.nCopies(N, Integer.MAX_VALUE)); // distance from source to itself is zero dist.set(source, 0); // boolean array to track vertices for which minimum // cost is already found boolean[] done = new boolean[N]; done[0] = true; // stores predecessor of a vertex (to print path) int prev[] = new int[N]; prev[0] = -1; // run till minHeap is not empty while (!minHeap.isEmpty()) { // Remove and return best vertex Node node = minHeap.poll(); // get vertex number int u = node.vertex; // do for each neighbor v of u for (Edge edge: graph.adjList.get(u)) { int v = edge.dest; int weight = edge.weight; // Relaxation step if (!done[v] && (dist.get(u) + weight) < dist.get(v)) { dist.set(v, dist.get(u) + weight); prev[v] = u; minHeap.add(new Node(v, dist.get(v))); } } // marked vertex u as done so it will not get picked up again done[u] = true; } for (int i = 1; i < N; ++i) { System.out.print("Path from vertex 0 to vertex " + i + " has minimum cost of " + dist.get(i) + " and the route is [ "); printRoute(prev, i); System.out.println("]"); } } public static void main(String[] args) { // initialize edges as per above diagram // (u, v, w) triplet represent undirected edge from // vertex u to vertex v having weight w List<Edge> edges = Arrays.asList( new Edge(0, 1, 10), new Edge(0, 4, 3), new Edge(1, 2, 2), new Edge(1, 4, 4), new Edge(2, 3, 9), new Edge(3, 2, 7), new Edge(4, 1, 1), new Edge(4, 2, 8), new Edge(4, 3, 2) ); // Set number of vertices in the graph final int N = 5; // construct graph Graph graph = new Graph(edges, N); shortestPath(graph, 0, N); } } |

`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:**

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

2. 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

Excellent explanation and an even better code. Can you please also discuss about k-shortest algorithms? Is there a way to alter djikstra to get the answer?

Can you please provide the java solution . I don’t know c++ and can you also explain me how to structure map + heap data structure if possible.

Abhishek, we have added the Java implementation to the solution. Happy coding 🙂

i’m not able to understand

List dist = new ArrayList(Collections.nCopies(N, Integer.MAX_VALUE));

what does nCopies do

can you please also share a code in which instead of using priority queue from collection class you are creating your own min/max heap. As it is required in various question as they are faster. Please help me

Hi, I ran the code and it worked excellent when I started from vertex 0. However, If I start from other vertices, it has problem with calculating the distance from that vertex to vertex 0. Also, it will print 0 first when I print the path. I don’t know how to fix it. Can you help me with that? Thank you so much!!!