# Dijkstra’s shortest path algorithm in C++

In this tutorial, we are going to implement **Dijkstra’s shortest path algorithm using sets in C++ language. **Before we proceed further let’s take a quick look at what is **Dijkstra’s algorithm**?

## Dijkstra’s algorithm

**Dijkstra’s shortest path algorithm is** an algorithm which is used for finding the shortest paths between nodes in a graph, for example, road networks, etc. This algorithm is a generalization of the BFS algorithm. The algorithm works by keeping the shortest distance of vertex v from the source in the distance table. After the algorithm finishes, we will have the shortest distance from source s to each other vertex v.

For more information, you can visit,

https://en.wikipedia.org/wiki/Dijkstra’s_algorithm

## C++ Code to apply Dijkstra’s shortest path algorithm

We will use two sets in this particular code, one set contains vertices included in shortest path tree and other set includes vertices not yet included in shortest path tree. During every step, we will find a vertex which is in the other set and has a minimum distance from the source.

// A C++ program for Dijkstra's shortest path algorithm. #include<bits/stdc++.h> using namespace std; // Total number of vertices in graph #define V 9 // For printing the shortest path int shortest_path(int dist[], int n) { cout<<"Vertex "<<"\t"<<"Distance from Source\n"; for (int i = 0; i < V; i++) cout<<" \t\t \n"<< i<<" \t\t "<<dist[i]; } // For calculating minimum distance int minDist(int dist[], bool Set[]) { int min = INT_MAX, min_index; for (int i = 0; i < V; i++) if (Set[i] == false && dist[i] <= min) min = dist[i], min_index = i; return min_index; } // Calculate shortest paths from source to all other vertices void Dijkstra(int g[V][V], int src) { int dist[V]; bool Set[V]; for (int i = 0; i < V; i++) dist[i] = INT_MAX, Set[i] = false; dist[src] = 0; for (int c = 0; c < V- 1; c++) { int u = minDist(dist, Set); Set[u] = true; for (int j = 0; j < V; j++) if (!Set[j] && g[u][j] && dist[u] != INT_MAX && dist[u]+ g[u][j] < dist[j]) { dist[j] = dist[u] + g[u][j]; } } shortest_path(dist, V); } // Driver Program int main() { ios_base::sync_with_stdio(false); cin.tie(NULL); int G[V][V] = { { 0, 4, 0, 0, 0, 0, 0, 8, 0 }, { 4, 0, 8, 0, 0, 0, 0, 11, 0 }, { 0, 8, 0, 7, 0, 4, 0, 0, 2 }, { 0, 0, 7, 0, 9, 14, 0, 0, 0 }, { 0, 0, 0, 9, 0, 10, 0, 0, 0 }, { 0, 0, 4, 14, 10, 0, 2, 0, 0 }, { 0, 0, 0, 0, 0, 2, 0, 1, 6 }, { 8, 11, 0, 0, 0, 0, 1, 0, 7 }, { 0, 0, 2, 0, 0, 0, 6, 7, 0 }}; Dijkstra(G, 0); return 0; }

Output:

Vertex Distance from Source 0 0 1 4 2 12 3 19 4 21 5 11 6 9 7 8 8 14

Important points:

- It uses the greedy method ( always choose the nearest closest vertex from the source ).
- It does not work with negative weights.

You may also learn,

## Leave a Reply

You must be logged in to post a comment.