0

我正在尝试存储 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);
}
4

1 回答 1

0

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

  • 首先，您通过 vertex 寻址路径v，但未初始化，并且在循环v之外没有任何意义。for
  • 此外，v字符串没有任何有意义的信息：它是一个顶点 ID。您也有到源的距离，但是您需要的字符串索引需要v从源顶点到达的步数，而您目前不存储这些。
  • 最后，您只能在找到所有距离后才能构建路径，而不是在寻路期间。

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

每当找到新的最短距离时，就设置前一个顶点：

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);

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

于 2014-03-22T07:31:21.720 回答