// created by Charmaine Labastida // https://www.sololearn.com/Discuss/2281611/dijkstra-problem-c #include #include //used for INT_MAX #include int minimumDist( /*int vertex, */ std::vector dist, std::vector Dset) //method to find the vertex with minimum distance which is not yet included in Dset { int vertex = dist.size(); 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, */ std::vector> graph, int src) { int vertex = graph.size(); std::vector dist(vertex); std::vector 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]; } } std::cout << "Vertex\t\tDistance from source" << std::endl; for(int i = 0; i < vertex; i++) { char c = 65 + i; std::cout << c << "\t\t" << dist[i] << std::endl; } } int main() { int vertex; std::cout << "Enter number of vertices"; std::cin >> vertex; std::vector> graph(21, std::vector(21,0)); std::cout << "Enter graph as matrix"; for(int i = 0; i < vertex; i++) { for(int j = 0; j < vertex; j++) { std::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-problem-c++_fx