最短路线修改

Question

有没有办法修改这个显示最短路径的路线？例如，如果我有一个数字列表，如 (3,1),(3,0),(4,3),(2,1) 从 4 到 1 的输出将是 4->3,3 ->1

// Prints shortest paths from src to all other vertices
void Graph::shortestPath(int src)
{
    // Create a priority queue to store vertices that
    // are being preprocessed. This is weird syntax in C++.
    // Refer below link for details of this syntax
    // http://geeksquiz.com/implement-min-heap-using-stl/
    priority_queue< iPair, vector <iPair> , greater<iPair> > pq;


    // Create a vector for distances and initialize all
    // distances as infinite (INF)
    vector<int> dist(V, INF);

    // Insert source itself in priority queue and initialize
    // its distance as 0.
    pq.push(make_pair(0, src));
    dist[src] = 0;

    /* Looping till priority queue becomes empty (or all
      distances are not finalized) */
    while (!pq.empty())
    {
        // The first vertex in pair is the minimum distance
        // vertex, extract it from priority queue.
        // vertex label is stored in second of pair (it
        // has to be done this way to keep the vertices
        // sorted distance (distance must be first item
        // in pair)
        int u = pq.top().second;
        pq.pop();

        // 'i' is used to get all adjacent vertices of a vertex
        list< pair<int, int> >::iterator i;
        for (i = adj[u].begin(); i != adj[u].end(); ++i)
        {
            // Get vertex label and weight of current adjacent
            // of u.
            int v = (*i).first;
            int weight = (*i).second;

            //  If there is shorted path to v through u.
            if (dist[v] > dist[u] + weight)
            {
                // Updating distance of v
                dist[v] = dist[u] + weight;
                pq.push(make_pair(dist[v], v));
            }
        }
    }

    // Print shortest distances stored in dist[]
    printf("Vertex   Distance from Source\n");
    for (int i = 0; i < V; ++i)
            printf("%d \t\t %d\n", i, dist[i]);
    }

放入一个存储路径编号的数组，如 4、3、3、1（使用上面的示例）似乎是最好的主意，但我不知道在这段代码中要将数组插入何处那。

Answer 1

听起来像是一道作业题。

如果这是一个 DFS，你存储路径编号的想法会很棒。不幸的是，Djikstra 的算法并不像 DFS 那样自然地跟踪路径；它只需要下一个最近的节点并更新距离值。在这方面它可能更类似于 BFS。

你可以做的是更新到每个节点的距离，以某种方式存储你来自哪个节点（如果允许，可能在你的 iPair 结构中，可能在 map/array 如果你有办法识别你的节点）。为了 post，我将其称为 "from" 参考。然后，每次找到到节点的较短路径时，您也可以从参考更新它。

那么你如何找到给定节点的路径呢？简单：只需从结束节点开始，然后按照 "from" 引用返回源。

Answer 2

正如您在 dist 向量中保存每个顶点的距离一样，将最后更新它的前驱顶点保存在名为 predecessor.

的向量中

vector<int> dist(V, INF);
vector<int> predecessor(V, 0);

然后每当你更新距离，更新前驱：

dist[v] = dist[u] + weight;
predecessor[v] = u;

最后，您可以追踪任何顶点到源的最短路径（向后）：

printf("Vertex   Distance from Source      shortest path from source\n");
for (int i = 0; i < V; ++i)
{
        printf("%d \t\t %d\t\t", i, dist[i]);
        int j = i;
        do
        {
             printf("%d,", j);
             j = predecessor[j];
        } while(j != src);
        printf("\n");
}

最短路线修改

Shortest route modification

c++

function

dijkstra