c - 我正在尝试在 Dijkstra 算法中存储路径

Question

我试图存储 Dijkstra 在计算从源到每个顶点的最短路径时所做的路径。这就是我目前正在做的事情，但我正在努力解决如何实际存储路径的问题。我希望有人能帮助我。您还应该注意，当前 u 值是整数，我想以字符形式返回此特定路径。数组大小为 26 x 26，因为字母表中有 26 个字符。可能的路径可以是 C B A 或 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);
}

Answer 1

您的 pathArray 方法存在一些问题:

• 首先，您通过顶点 v 寻址路径，但 v 未初始化，并且在 for 循环之外没有任何意义.
• 此外，v 对于字符串来说没有任何有意义的信息:它是一个顶点 ID。您还知道到源的距离，但您需要的字符串索引需要从源顶点到达 v 的步数，而您当前不存储该步数。
• 最后，您只能在找到所有距离后(而不是在寻路过程中)构建路径。

更好的方法是保留一个数组 prev[MAX_ROWS] 来存储从源到该顶点的最短路径中紧邻该顶点之前的顶点的顶点 ID。这意味着您本质上存储从目的地到源的路径。你不能反过来做，因为来自源的路径可能会 fork 。从另一端来看，这意味着所有路径最终都会在前往源时加入，因此将路径存储为先前点的列表是安全的。

只要找到新的最短距离，就可以设置前一个顶点:

if (!sptSet[v] && graph[u][v] && dist[u] != INT_MAX
&& dist[u]+graph[u][v] < dist[v])
{
    dist[v] = dist[u] + graph[u][v];
    prev[v] = u;
}

然后您可以打印从每个顶点 i 到源的路径:

v = i;
while (v != src) {
    putchar('A' + v);
    v = prev[v];
}
putchar('A' + src);
putchar(10);

如果要存储正向路径，可以实现递归方法，或者将路径写入字符串，然后反转。