// created by Charmaine Labastida // https://www.sololearn.com/Discuss/2281611/dijkstra-problem-c // A C / C++ program for Dijkstra's single source shortest // path algorithm. The program is for adjacency matrix // representation of the graph. #include #include #include using namespace std; // Number of vertices in the graph #define V 21 // A utility function to find the vertex with minimum distance // value, from the set of vertices not yet included in shortest // path tree int minDistance(int dist[], bool sptSet[]) { // Initialize min value int min = INT_MAX, min_index; for (int v = 0; v < V; v++) if (sptSet[v] == false && dist[v] <= min) min = dist[v], min_index = v; return min_index; } // Function to print shortest path from source to j // using parent array void printPath(int parent[], int j) { // Base Case : If j is source if (parent[j]==-1) return; printPath(parent, parent[j]); printf("%c", j+65); } // A utility function to print the constructed distance // array void printSolution(int dist[], int n, int parent[]) { char src = 65; printf("Vertex\t\tDistance\tPath"); for (int i = 1; i < V; i++) { char c = 65 + i; //printf("\n%d -> %d \t\t %d\t\t%d ", src, i, dist[i], src); //cout << c << "\t\t" << dist[i] << endl; cout << "\n" << src << " -> " << c << "\t\t" << dist[i] << "\t\t" << src; printPath(parent, i); cout << '\n'; } } // Funtion that implements Dijkstra's single source shortest path // algorithm for a graph represented using adjacency matrix // representation void dijkstra(int graph[V][V], int src) { int dist[V]; // The output array. dist[i] will hold // the shortest distance from src to i // sptSet[i] will true if vertex i is included / in shortest // path tree or shortest distance from src to i is finalized bool sptSet[V]; // Parent array to store shortest path tree int parent[V]; // Initialize all distances as INFINITE and stpSet[] as false for (int i = 0; i < V; i++) { parent[0] = -1; dist[i] = INT_MAX; sptSet[i] = false; } // Distance of source vertex from itself is always 0 dist[src] = 0; // Find shortest path for all vertices for (int count = 0; count < V-1; count++) { // Pick the minimum distance vertex from the set of // vertices not yet processed. u is always equal to src // in first iteration. int u = minDistance(dist, sptSet); // Mark the picked vertex as processed sptSet[u] = true; // Update dist value of the adjacent vertices of the // picked vertex. for (int v = 0; v < V; v++) // Update dist[v] only if is not in sptSet, there is // an edge from u to v, and total weight of path from // src to v through u is smaller than current value of // dist[v] if (!sptSet[v] && graph[u][v] && dist[u] + graph[u][v] < dist[v]) { parent[v] = u; dist[v] = dist[u] + graph[u][v]; } } // print the constructed distance array printSolution(dist, V, parent); } // driver program to test above function int main() { int graph[V][V] = { { 0, 2, 4, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 }, { 2, 0, 3, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 }, { 4, 3, 0, 0, 2, 2, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 }, { 1, 0, 0, 0, 0, 5, 4, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 }, { 0, 1, 2, 0, 0, 0, 0, 3, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 }, { 0, 0, 2, 5, 0, 0, 3, 3, 2, 4, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 }, { 0, 0, 0, 4, 0, 3, 0, 0, 0, 0, 2, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 }, { 0, 0, 0, 0, 3, 3, 0, 0, 0, 0, 0, 1, 0, 0, 0, 8, 0, 0, 0, 0, 0 }, { 0, 0, 0, 0, 0, 2, 0, 0, 0, 3, 0, 3, 2, 0, 0, 0, 0, 0, 0, 0, 0 }, { 0, 0, 0, 0, 0, 4, 0, 0, 3, 0, 6, 0, 0, 6, 3, 0, 0, 0, 0, 0, 0 }, { 0, 0, 0, 0, 0, 0, 2, 0, 0, 6, 0, 0, 0, 4, 0, 0, 0, 0, 2, 0, 0 }, { 0, 0, 0, 0, 0, 0, 0, 1, 3, 0, 0, 0, 3, 0, 6, 0, 0, 0, 0, 0, 0 }, { 0, 0, 0, 0, 0, 0, 0, 0, 2, 0, 0, 3, 0, 5, 4, 2, 0, 0, 0, 0, 0 }, { 0, 0, 0, 0, 0, 0, 0, 0, 0, 6, 4, 0, 5, 0, 0, 0, 2, 1, 0, 0, 0 }, { 0, 0, 0, 0, 0, 0, 0, 0, 0, 3, 0, 6, 4, 0, 0, 2, 0, 0, 6, 0, 0 }, { 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 2, 0, 2, 0, 1, 0, 2, 1, 0 }, { 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 2, 0, 1, 0, 8, 0, 3, 0 }, { 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 8, 0, 0, 5, 0 }, { 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 2, 0, 0, 0, 6, 2, 0, 0, 0, 0, 2 }, { 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 3, 5, 0, 0, 8 }, { 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 2, 8, 0 } }; dijkstra(graph, 0); return 0; }

Dijkstra problem C++ fx2