最短路线修改 [英] Shortest route modification

问题描述

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

Is there a way to modify this to show the route of the shortest path? For example, if i had a list of numbers like (3,1),(3,0),(4,3),(2,1) the output for getting from 4 to 1 would be 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（使用上面的例子）似乎是最好的想法，但我不知道在这段代码中插入数组的位置。

Putting in an array that stores the numbers of the path like 4,3,3,1 (using above example) seems like the best idea but i don't know where to insert the array in this code to do that.

推荐答案

正如您为 dist 向量中的每个顶点保存距离一样，将上次更新它的前一个顶点保存到名为前身。

Just as you save the distances for each vertex in the dist vector, save the predecessor vertex that last updated it in a vector called predecessor.

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

然后，每当您更新距离时，请更新前任：

Then whenever you update the distance, update the predecessor:

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

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

Finally, you can trace for any vertex the shortest path (Backward) to the source:

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");
}

这篇关于最短路线修改的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！