//Dijsktra Algorithm Model //For more information visit here: https://www.geeksforgeeks.org/dijkstras-shortest-path-algorithm-greedy-algo-7/ #include #include #include using namespace std; int V = 9; void printSolution(vector dists){ cout << "Vertex:" << '|' << "\t" << '|' << "Distance from source:" << endl; for(int i = 0; i < V; i++){ cout << '\t' << "\t\b\b" << i << '|' <<'\t' << '|' << dists[i] << endl; } } int minDistance(vector sptSet, vector dists){ int min = INT_MAX; int min_idx; for(int i = 0; i < V; i++){ if(dists[i] < min && sptSet[i] == false){ min = dists[i]; min_idx = i; } } return min_idx; } void dijkstra(vector > graph, int source){ vector dists(V, INT_MAX); vector sptSet(V, false); dists[source] = 0; for(int i = 0; i < V - 1; i++){ int v = minDistance(sptSet, dists); sptSet[v] = true; for(int d = 0; d < V; d++){ if(dists[v] + graph[v][d] < dists[d] && graph[v][d] != 0){ dists[d] = dists[v] + graph[v][d]; } } } printSolution(dists); } int main(){ vector > graph { { 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(graph, 0); return 0; }

Dijkstra's Algorithm Model