Can you help to adjust the void dijkstra(int s) function to find a path from source to every node so that the minimum cost on that path is maximum.
Ex:
From 1 to 2 we have 1 - 3 - 4 - 2 , costs(2+3+4+5)
From 1 to 2 we have 1 - 5 - 6 - 2 , costs(3+3+4+5)
I need the algorithm to choose path 1 - 5 - 6 - 2 since minimum cost = 3 > minimum cost in the first path.
======= Here is the code I'm looking to adjust ======
#include <stdio.h>
#define GRAPHSIZE 2048
#define INFINITY GRAPHSIZE*GRAPHSIZE
#define MAX(a, b) ((a > b) ? (a) : (b))
int e; /* The number of nonzero edges in the graph */
int n; /* The number of nodes in the graph */
long dist[GRAPHSIZE][GRAPHSIZE]; /* dist[j] is the distance between node i and j; or 0 if there is no direct connection */
long d[GRAPHSIZE]; /* d is the length of the shortest path between the source (s) and node i */
int prev[GRAPHSIZE][GRAPHSIZE + 1]; /* prev holds the nodes that could comes right before i in the shortest path from the source to i;
prev[0] is the number of nodes and prev[1..] are the nodes */
void printD() {
int i;
printf("Distances:\n");
for (i = 1; i <= n; ++i)
printf("%10d", i);
printf("\n");
for (i = 1; i <= n; ++i) {
printf("%10ld", d);
}
printf("\n");
}
/*
* Prints the shortest path from the source to dest.
*
* dijkstra(int) MUST be run at least once BEFORE
* this is called
*/
void printPath(int dest, int depth) {
int i, j;
printf("-%d\n", dest);
for (i = 1; i <= prev[dest][0]; ++i) {
for (j = 0; j <= depth; ++j)
printf(" |");
printPath(prev[dest], depth + 1);
}
}
void dijkstra(int s) {
int i, k, mini;
int visited[GRAPHSIZE];
for (i = 1; i <= n; ++i) {
d = INFINITY;
prev[0] = 0; /* no path has yet been found to i */
visited = 0; /* the i-th element has not yet been visited */
}
d = 0;
for (k = 1; k <= n; ++k) {
mini = -1;
for (i = 1; i <= n; ++i)
if (!visited && ((mini == -1) || (d < d[mini])))
mini = i;
visited[mini] = 1;
for (i = 1; i <= n; ++i)
if (dist[mini]) {
if (d[mini] + dist[mini] < d) { /* a shorter path has been found */
d = d[mini] + dist[mini];
prev[0] = 1;
prev[1] = mini;
} else if (d[mini] + dist[mini] == d) { /* a path of the same length has been found */
++prev[0];
prev[prev[0]] = mini;
}
}
}
}
int main(int argc, char *argv[]) {
int i, j;
int u, v, w;
FILE *fin = fopen("dist.txt", "r");
fscanf(fin, "%d", &e);
for (i = 0; i < e; ++i)
for (j = 0; j < e; ++j)
dist[j] = 0;
n = -1;
for (i = 0; i < e; ++i) {
fscanf(fin, "%d%d%d", &u, &v, &w);
dist[v] = w;
n = MAX(u, MAX(v, n));
}
fclose(fin);
dijkstra(1);
printD();
printf("\n");
for (i = 1; i <= n; ++i) {
printf("Path to %d:\n", i);
printPath(i, 0);
printf("\n");
}
return 0;
}