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

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 中，键是一个节点，值是用来到达这张 map 的节点。
显然，源将成为这张 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;
    }
}

有了这张 map 后，获取路径就非常简单了，可以通过以下方式完成:

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

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