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

Question

所以首先让我们定义Dijkstra算法：
Dijkstra 算法在具有非负边权重的有向图中找到单源最短路径。
我想知道如何使用 Dijkstra 算法保存从 s 到 t 的最短路径。
我在 google 上搜索，但找不到任何特别的东西；我也改变了 Dijkstra 算法，但我得不到任何答案。如何使用 Dijkstra?
保存从 s 到 t 的最短路径我知道我的问题是基本的和不专业的，但我们将不胜感激。感谢您考虑我的问题。

Answer 1

大多数使用此算法的库都可能会为您提供执行此操作的方法。但通常只跟踪到每个节点的路径。即给每个节点一个属性shortestPathToNode，您在其中存储节点列表

Answer 2

如果您查看您提供的维基百科 link 中的 pseudocode，您会在其中看到一个名为 prev[] 的数组。此数组包含，对于图中的每个节点 v，最短路径中的 previous 节点 u在源节点 s 和 v 之间。（此数组也称为 predecessor 或 parent 数组。）

也就是说s和v之间的最短路径是：

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

从s到u的路径中间可能有几个节点，所以要重建从s的路径 到 v，您只需使用主要伪代码 (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

Answer 3

一种极短的方法是使用递归和 "parent array." 如果将所有点的父项初始化为 -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;
}

请注意，您可以将其存储在全局向量（或与 C 语言无关的其他数据类型）中以备后用，而不是打印 "j"。

Answer 4

只是修改表格there

# 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;
}

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

how to save shortest path in dijkstra algorithm

algorithm

graph

dijkstra

shortest-path