如何在Dijkstra算法中保存最短路径

Question

首先，让我们定义Dijkstra算法：
Dijkstra算法用于在具有非负边权的有向图中查找单源最短路径。
我想知道如何使用Dijkstra算法保存从s到t的最短路径。
我在谷歌上搜索了一下，但没有找到特别的东西；我也改变了Dijkstra算法，但是得不到任何答案。如何使用Dijkstra保存从s到t的最短路径？
我知道我的问题很基础，也不专业，但是任何帮助都将不胜感激。感谢您考虑我的问题。

- Daniel.V

Answer 1

如果你查看你提供的维基百科链接中的伪代码，你会发现里面有一个名为prev[]的数组。对于图中的每个节点v，该数组包含源节点s和v之间最短路径上的前一个节点u。（该数组也称为前驱或父数组。）

换句话说，s和v之间的最短路径是：

s -> u -> v
where u = prev[v]

从 s 到 u 的路径中间可能有多个节点，所以要重构从 s 到 v 的路径，只需沿着由 prev[] 数组定义的路径向后走，使用主伪代码下面的代码片段即可（target 是 v）：

1  S ← empty sequence
2  u ← target
3  while prev[u] is defined:                 // Construct the shortest path with a stack S
4      insert u at the beginning of S          // Push the vertex onto the stack
5      u ← prev[u]                             // Traverse from target to source
6  end while

- beaker

---

我们如何存储重复路径？ - user248884

Answer 2

一种非常简短的方法是使用递归和“父数组”。 如果您将所有点的父项初始化为-1，然后在完成Dijkstra算法时更新父项数组，则可以从任何点递归回到源并打印出路径。这里是一个非常简短且易于理解的递归片段：

// Function to print shortest path from source to j using parent array
void path(parent array, int j)
{
    // Base Case : If j is source
    if (jth element of parent is -1) return;
 
    path(parent, jth element of parent);
    print j;
}

请注意，您可以将“j”存储在全局向量（或其他数据类型，适用于非C相关的语言）中以供以后使用，而不是将其打印出来。

- NL628

Answer 3

只是一个修改表单 那里

# define INF 0x3f3f3f3f
// iPair ==> Integer Pair
typedef pair<int, int> iPair;

void addEdge(vector <pair<int, int> > adj[], int u, int v, int wt)
{
    adj[u].push_back(make_pair(v, wt)); 
    adj[v].push_back(make_pair(u, wt));
}
void shortestPath(vector<pair<int, int> > adj[], int V, int src, int target)
{
    priority_queue< iPair, vector <iPair>, greater<iPair> > pq;
    vector<int> dist(V, INF);
    vector<bool> visited(V, false);
    vector<int> prev(V, -1);
    pq.push(make_pair(0, src));
    dist[src] = 0;
    while (!pq.empty() && !visited[target])
    {
        int u = pq.top().second; 
        pq.pop();
        if (visited[u]) {
            continue;
        }
        visited[u] = true;
        for (auto x : adj[u])
        {
            int v = x.first;
            int weight = x.second;

            if (dist[v] > dist[u] + weight)
            {
                //relax
                dist[v] = dist[u] + weight;
                pq.push(make_pair(dist[v], v));
                prev[v] = u;
            }
        }
    }

    vector<int> res;
    res.push_back(target);
    int temp = target;
    while (temp != 0)
    {
        temp = prev[temp];
        res.push_back(temp);
    }
    //cout << res;
}
int main()
{
    const int V = 9;
    vector<iPair > adj[V];
    addEdge(adj, 0, 1, 4);
    addEdge(adj, 0, 7, 8);
    addEdge(adj, 1, 2, 8);
    addEdge(adj, 1, 7, 11);
    addEdge(adj, 2, 3, 7);
    addEdge(adj, 2, 8, 2);
    addEdge(adj, 2, 5, 4);
    addEdge(adj, 3, 4, 9);
    addEdge(adj, 3, 5, 14);
    addEdge(adj, 4, 5, 10);
    addEdge(adj, 5, 6, 2);
    addEdge(adj, 6, 7, 1);
    addEdge(adj, 6, 8, 6);
    addEdge(adj, 7, 8, 7);

    shortestPath(adj, V, 0, 6);     //the last one means target
    return 0;
}

- Kargath

Answer 4

大多数使用此算法的库很可能会提供一种方法来实现这一点。但是通常只需跟踪到每个节点的路径即可。例如，为每个节点分配一个属性shortestPathToNode，其中存储节点列表。

- Calum