//by Bell //challenge Oma Falk, adapted from geekforgeeks recipe // A C++ program for Dijkstra's single source shortest path algorithm. // The program is for adjacency matrix representation of the graph /*Dijkstra challenge Anton has a book but he wants a piano. Bertha would give him a cd for the book and 5$. Carl would give a poster for the book. For the CD and 15$ Dora would give her guitar. For the poster and 30$ Dora would give her guitar too. For the CD and 20$ Elton would give his drums. For the poster and35$ Elton would give his drums too. Sebastian would give his piano for the guitar and 20$ or for the drums and 10$. Anton wants to pay as little dollar as possible. Which deals will Anton do? */ #include #include #include using namespace std; // Number of vertices in the graph #define V 6 /* 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; //printf("%d \t\t %d\n",min,min_index); 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("%d ", j); } // A utility function to print // the constructed distance // array void printSolution(int dist[], int n, int path[]) { int src = 0; printf("Vertex\t Distance\tPath"); // for (int i = 1; i < V; i++) for (int i = 5; i < V; i++) { printf("\n%d -> %d \t\t %d\t\t%d ", src, i, dist[i], src); printPath(path, i); } } // Dijkstra's single source shortest path algorithm // for a graph of adjacency matrix representation void dijkstra(int graph[V][V], int src) { int dist[V]; // The output array. // dist[i] will hold shortest distance from src to i int path[V]; // The output paths array, will hold parents. // path[i] will hold paths from src to i bool sptSet[V]; // sptSet[i] will be true if vertex i is included in shortest path tree or shortest distance from src to i is finalized // Initialize all distances as INFINITE and stpSet[] as false for (int i = 0; i < V; i++) dist[i] = INT_MAX, sptSet[i] = false; // Distance of source vertex from itself is always 0 dist[src] = 0; // Source vertex has no parent path[0] = -1; // 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 the first iteration. */ int u = minDistance(dist, sptSet); // Mark the picked vertex as processed sptSet[u] = true; // Update dist value of vertices adjacent to 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] At the same time, store the parent of node in the path array*/ if (!sptSet[v] && graph[u][v] && dist[u] != INT_MAX && dist[u] + graph[u][v] < dist[v]){ dist[v] = dist[u] + graph[u][v]; path[v] = u;} } // print the constructed distance array printSolution(dist,V,path); } // driver program to test above function int main() { // # A B C D E S // # Book CD Post Gui Drum Piano int graph[V][V] = { { 99, 5, 0, 99, 99, 99 }, { 99, 99, 99, 15, 20, 99 }, { 99, 99, 99, 30, 35, 99 }, { 99, 99, 99, 99, 99, 20 }, { 99, 99, 99, 99, 99, 10 }, { 99, 99, 99, 99, 99, 99 } }; dijkstra(graph, 0); return 0; }

DijkstraOmaFalkPath