Dijikstra计算后如何打印路径？

Question

我开始实现图形算法，但我不知道如何为这个 Dijkstra 实现打印从源到目标的路径？谢谢

#define INF 0x3f3f3f3f
typedef pair<int,int> ii;  // to vertex, weight
typedef vector<ii> vii;    // from source to vertexes with weight
typedef vector<vii> graph;  // graph

graph gg;
vector<int> Dist;

void Dijikstra(int source, int N){
    priority_queue<ii, vii, greater<ii>> Q;
    Dist.assign(N,INF);
    Dist[source] = 0;
    Q.push(make_pair(0,source));
    while (!Q.empty())
    {
        ii front = Q.top(); Q.pop();
        int d = front.first, u = front.second;
        if(d > Dist[u]) continue;
        for (int i = 0; i < gg[u].size(); i++)
        {
            ii v = gg[u][i];
            if(Dist[u]+v.second < Dist[v.first]){
                Dist[v.first]  = Dist[u] + v.second;
                Q.push(ii(Dist[v.first],v.first));          
            }
        }
    }
}

Answer 1

使用 dijkstra，每次将节点添加到 'visited set' 时，您都会将节点设置为 'parent' 或 'origin'，即添加它的访问集中的节点。到达目标节点后，从那里开始并向上移回父节点，直到回到源节点。

您可以先打印此序列，或者如果您正在寻找更直观的方法，您可以查看 graphviz 工具集和库。

Answer 2

Dijkstra算法伪代码：

function Dijkstra(Graph, source):
    create vertex set Q
    for each vertex v in Graph:  // Initialization
        dist[v] ← INFINITY       // Unknown distance from source to v
        prev[v] ← UNDEFINED      // Previous node in optimal path from source
        add v to Q               // All nodes initially in Q (unvisited nodes)
    dist[source] ← 0             // Distance from source to source
    while Q is not empty:
        u ← vertex in Q with min dist[u]  // Node with the least distance will be selected first
        remove u from Q     
        for each neighbor v of u:         // where v is still in Q.
            alt ← dist[u] + length(u, v)
            if alt < dist[v]:             // A shorter path to v has been found
                dist[v] ← alt 
                prev[v] ← u 
     return dist[], prev[]

重构路径：

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

Dijikstra计算后如何打印路径？

How to print the path after Dijikstra calculation?

c++

algorithm

dijkstra