#include using namespace std; #include //used for INT_MAX int minimumDist(int vertex, int dist[], bool Dset[]) //method to find the vertex with minimum distance which is not yet included in Dset { int min = INT_MAX, index; for(int v = 0; v < vertex; v++) { if(Dset[v] == false && dist[v] <= min) { min = dist[v]; index = v; } } return index; } void dijkstra(int vertex, int graph[vertex][vertex], int src) { int dist[vertex]; bool Dset[vertex]; for(int i = 0; i < vertex; i++) { dist[i] = INT_MAX; Dset[i] = false; } dist[src] = 0; for(int c = 0; c < vertex; c++) { int u = minimumDist(vertex, dist, Dset); Dset[u] = true; for(int v = 0; v < vertex; v++) { if(!Dset[v] && graph[u][v] && dist[u] != INT_MAX && dist[u] + graph[u][v] < dist[v]) dist[v] = dist[u] + graph[u][v]; } } cout << "Vertex\t\tDistance from source" << endl; for(int i = 0; i < vertex; i++) { char c = 65 + i; cout << c << "\t\t" << dist[i] << endl; } } int main() { int vertex; cout << "Enter number of vertices"; cin >> vertex; int graph[vertex][vertex]; cout << "Enter graph as matrix"; for(int i = 0; i < vertex; i++) { for(int j = 0; j < vertex; j++) { cin >> graph[i][j]; } } dijkstra(vertex, graph, 0); return 0; } /* for given graph, there is 21 nodes input matrix is as follows: a b c d e f g h i j k l m n o p q r s t z a 0 2 4 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 b 2 0 3 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 c 4 3 0 0 2 2 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 d 1 0 0 0 0 5 4 0 0 0 0 0 0 0 0 0 0 0 0 0 0 e 0 1 2 0 0 0 0 3 0 0 0 0 0 0 0 0 0 0 0 0 0 f 0 0 2 5 0 0 3 3 2 4 0 0 0 0 0 0 0 0 0 0 0 g 0 0 0 4 0 3 0 0 0 0 2 0 0 0 0 0 0 0 0 0 0 h 0 0 0 0 3 3 0 0 0 0 0 1 0 0 0 8 0 0 0 0 0 i 0 0 0 0 0 2 0 0 0 3 0 3 2 0 0 0 0 0 0 0 0 j 0 0 0 0 0 4 0 0 3 0 6 0 0 6 3 0 0 0 0 0 0 k 0 0 0 0 0 0 2 0 0 6 0 0 0 4 0 0 0 0 2 0 0 l 0 0 0 0 0 0 0 1 3 0 0 0 3 0 6 0 0 0 0 0 0 m 0 0 0 0 0 0 0 0 2 0 0 3 0 5 4 2 0 0 0 0 0 n 0 0 0 0 0 0 0 0 0 6 4 0 5 0 0 0 2 1 0 0 0 o 0 0 0 0 0 0 0 0 0 3 0 6 4 0 0 2 0 0 6 0 0 p 0 0 0 0 0 0 0 0 0 0 0 0 2 0 2 0 1 0 2 1 0 q 0 0 0 0 0 0 0 0 0 0 0 0 0 2 0 1 0 8 0 3 0 r 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 8 0 0 5 0 s 0 0 0 0 0 0 0 0 0 0 2 0 0 0 6 2 0 0 0 0 2 t 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 3 5 0 0 8 z 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 2 8 0 input each element wise. */

dijkstra.cpp