我正在尝试存储 Dijkstra 在计算从源到每个顶点的最短路径时所做的路径。这就是我现在正在做的事情,但我正在努力解决如何实际存储路径。我希望有人可以帮助我。您还应该注意,当前 u 值是整数,我想将此特定路径作为字符返回。数组大小为 26 x 26,因为字母表中有 26 个字符。可能的路径可以是 CBA 或 2、1、0。
void dijkstra(int graph[MAX_ROWS][MAX_COLUMNS], int src){
int dist[MAX_ROWS]; // The output array. dist[i] will hold the shortest distance from src to i
bool sptSet[MAX_ROWS]; // sptSet[i] will true if vertex i is included in shortest path tree or shortest distance from src to i is finalized
int i, count, v;
struct path {
char thepath[40];
} pathArray[MAX_ROWS];
// Initialize all distances as INFINITE and stpSet[] as false
for (i = 0; i < MAX_ROWS; i++)
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 (count = 0; count < MAX_ROWS-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);
int baby = u + 'A';
char girl = baby;
printf("Count : %d, u : %c\n", count, girl);
pathArray[v].thepath[v] = girl;
// Mark the picked vertex as processed
sptSet[u] = true;
// Update dist value of the adjacent vertices of the picked vertex.
for (v = 0; v < MAX_ROWS; 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] != INT_MAX && dist[u]+graph[u][v] < dist[v]){
dist[v] = dist[u] + graph[u][v];
}
}
// print the constructed distance array
printf("Vertex Distance from Source\n");
for (i = 0; i < MAX_ROWS; i++){
if (dist[i] != INT_MAX)
printf("%d \t\t %d Path: %s\n", i, dist[i], pathArray[i].thepath);
}
//printSolution(dist, MAX_ROWS, pathArray.thepath);
}