如何打印图中两个顶点之间的最短路径？

Question

我有一个 Djikstra 算法的工作实现，它计算任意两个节点之间的最短路径的长度。但如果我需要找到实际的路径，我该如何打印它呢？谢谢！

void djikstra( graph * mygraph )
{
    int dist[100] = {INT_MAX};
    int i;
    //int parent[mygraph->vertices] = {-99};
    for ( i = 0; i < 100; i++ )
        dist[i] = INT_MAX;
    bool arr[100];
    for ( i = 0; i < 100; i++ )
        arr[i] = false;
    int foo;
    cout<<"Enter the source vertex\n";
    cin>>foo;
    dist[foo] = 0;  
    vector<int> bar;
    while (bar.size() != mygraph->vertices)
    {
        int node = findmin(dist,mygraph->vertices,arr);
        arr[node] = true; // so that again and again same node having minimum distance is not returned
        bar.push_back(node);
        auto it = mygraph->edges[node].begin();
        while (it != mygraph->edges[node].end())
        {
            relax(node,it->first,it->second,dist); // here, it->first represents the node and it->second represents the weight
            it++;
        }
    }
    cout<<"Vertex\t"<<"Distance from source\n";
    for ( i = 0; i < mygraph->vertices; i++ )
    {
        cout<<i<<"\t"<<dist[i]<<"\n";
    }   
    cout<<"\n";
    return;
}

void relax ( int node, int a, int w, int dist[] )
{
    if (dist[a] > dist[node] + w)
    {
        dist[a] = dist[node] + w;
    }
}

Answer 1

您还需要保留一个映射，该映射从节点映射到其“父节点”。

在这个map中，key是一个节点，value是用来到达这个map的节点。
显然，源将是该地图中的根。

这是通过添加以下内容来完成的：

parentMap[a] = node;

在松弛步骤中：

void relax ( int node, int a, int w, int dist[] )
{
    if (dist[a] > dist[node] + w)
    {
        dist[a] = dist[node] + w;
        parentMap[a] = node;
    }
}

一旦你有了这张地图，获取路径就非常容易了，可以通过以下方式完成：

int current = target;
while (current != source) { 
   cout << current << ' ';
   current = parentMap[current];
}
cout << current << ' ';

注意，上面以相反的顺序打印路径。您可以使用列表（并将元素添加到其前面而不是打印元素）来获取正确顺序的路径。