c - 打印 dijkstra 算法中的路径

Question

我的计算机科学教授给了我一个 dijstras 算法的实现，他要求我们修改它以打印从源节点“src”(参见代码)到每个节点的路径，以及距离(它已经做)。我已经研究了这个问题大约一周了，并尝试了几件事。我一生都无法弄清楚......任何帮助将不胜感激。该图由邻接矩阵表示，并且有一个包含其大小的全局:

int n; //Global matrix's size
int minDistance(int dist[], bool sptSet[]){
    // Initialize min value
    int min = INT_MAX, min_index;
    int i = 0;
    for ( i = 0; i < n; i++)
        if (sptSet[i] == false && dist[i] <= min)
            min = dist[i], min_index = i; 
   return min_index;
}

int printSolution(int dist[]){
   printf("Vertex   Distance from Source\n");
   int i;
   for (i = 0; i < n; i++)
      printf("%d \t\t %d\n", i, dist[i]);
}

void dijkstra(int ** graph, int src){
    //correting zeros (won't work with negative values)
    correctZeros(graph);
    int dist[n]; 
    bool sptSet[n];
    int i;
    for (i = 0; i < n; i++)
        dist[i] = INT_MAX, sptSet[i] = false;
    dist[src] = 0;

    // Find shortest path for all vertices
    int count;
    for (count = 0; count < n; count++){
        int u = minDistance(dist, sptSet);
        sptSet[u] = true;
        int j;
        for (j = 0; j < n; j++){
            printf("%d", u);
            if (!sptSet[j] && graph[u][j] && dist[u] != INT_MAX && dist[u]+graph[u][j] < dist[j]){
                dist[j] = dist[u] + graph[u][j];

            }
        }
    }
    printSolution(dist);
}

Answer 1

您需要做的就是为每个节点存储最短路径的下一跳。每当您更新节点最短路径的距离时，此信息都会更新。