如何使用bellman ford算法返回所有具有平权的最短路径？

Question

正如title所说，我正在寻找的是打印“所有最短路径”，这些路径是通过权重联系在一起的。

示例：

我们有一个从0到1 -> 3的边的图，它的权重是6，但我们也有权重为6的路径0 -> 3，下面的算法只返回第一条路径，我想知道是否有可能返回两条或所有相同的路径。此外，还有一种更有效/更优雅的打印最短路径的方法。我只拿这段代码作为例子，我的代码非常相似，但只从源代码打印到最后一个顶点。

这里回答了一个类似的问题，但我无法理解代码，因为我熟悉c++。

#include <iostream>
#include <vector>
#include <iomanip>
#include <climits>
using namespace std;

// Data structure to store graph edges
struct Edge
{
    int source, dest, weight;
};

// Recurive Function to print path of given vertex v from source vertex
void printPath(vector<int> const &parent, int v)
{
    if (v < 0)
        return;

    printPath(parent, parent[v]);
    cout << v << " ";
}

// Function to run Bellman Ford Algorithm from given source
void BellmanFord(vector<Edge> const &edges, int source, int N)
{
    // count number of edges present in the graph
    int E = edges.size();

    // distance[] and parent[] stores shortest-path (least cost/path)
    // information. Initially all vertices except source vertex have
    // a weight of infinity and a no parent

    vector<int> distance (N, INT_MAX);
    distance[source] = 0;

    vector<int> parent (N, -1);

    int u, v, w, k = N;

    // Relaxation step (run V-1 times)
    while (--k)
    {
        for (int j = 0; j < E; j++)
        {
            // edge from u to v having weight w     
            u = edges[j].source, v = edges[j].dest;
            w = edges[j].weight;

            // if the distance to the destination v can be
            // shortened by taking the edge u-> v
            if (distance[u] != INT_MAX && distance[u] + w < distance[v])
            {
                // update distance to the new lower value
                distance[v] = distance[u] + w;

                // set v's parent as u
                parent[v] = u;
            }
        }
    }

    // Run Relaxation step once more for Nth time to
    // check for negative-weight cycles
    for (int i = 0; i < E; i++)
    {
        // edge from u to v having weight w
        u = edges[i].source, v = edges[i].dest;
        w = edges[i].weight;

        // if the distance to the destination u can be
        // shortened by taking the edge u-> v       
        if (distance[u] != INT_MAX && distance[u] + w < distance[v])
        {
            cout << "Negative Weight Cycle Found!!";
            return;
        }
    }

    for (int i = 0; i < N; i++)
    {
        cout << "Distance of vertex " << i << " from the source is "
             << setw(2) << distance[i] << ". It's path is [ ";
        printPath(parent, i); cout << "]" << '\n';
    }
}

// main function
int main()
{
    // vector of graph edges as per above diagram
    vector<Edge> edges =
    {
        // (x, y, w) -> edge from x to y having weight w
        { 0, 1, 2 }, { 1, 3, 4 }, { 0, 3, 6 }
    };

    // Set maximum number of nodes in the graph
    int N = 5;

    // let source be vertex 0
    int source = 0;

    // run Bellman Ford Algorithm from given source
    BellmanFord(edges, source, N);

    return 0;
}

Answer 1

从更抽象的角度来看，你有一些东西可以找到一个最小的东西，你想要改变它，以同样小的返回所有其他的东西。(同样的原则也适用于寻找更大的东西。然而，坚持使用“最小”这个词更容易解释。)

许多寻找极端事物的算法都会问“是A比B更极端”。例如，您可能会看到如下代码：

if ( A < B )
    smallest = A;

请注意，这是如何忽略平局(A == B)的，就像它忽略更糟糕的结果(A > B)一样。因此，您只能获得返回的第一个最佳结果。所以这是需要改变的。但是，您不能简单地将A < B更改为A <= B，因为这会在平局的情况下用A替换B，就像在A更好的情况下替换它一样。(您只会得到返回的最后一个最佳结果。)这三种情况(小于、等于和大于)需要分别处理。

要看的另一个方面是如何跟踪最小的东西。上面的代码片段表明smallest与A具有相同的类型；这不足以跟踪多个解决方案。您可能需要一个容器来跟踪解决方案。vector可能是一个合理的选择。

把这些放在一起，上面的代码可能会变得更像下面这样(在更改smallest的声明之后)：

if ( A < B ) {
    smallest.clear();
    smallest.push_back(A);
}
else if ( A == B ) {
    smallest.push_back(A);
}

如何将其应用于贝尔曼-福特？

幸运的是，代码的关键部分相对容易，因为有注释对其进行记录。更难的部分是更改代码以跟踪多个结果，因为当找到更短的路径时，会更新两条数据。看起来parent是需要扩展的数据。以下是对它的新声明：

vector< vector<int> > parent (N);

这使用了一个空向量而不是-1来表示“没有父元素”。对最短路径检查现在可以变成

if (distance[u] != INT_MAX) {
    // if the distance to the destination v can be
    // shortened by taking the edge u-> v
    if (distance[u] + w < distance[v])
    {
        // update distance to the new lower value
        distance[v] = distance[u] + w;
        // forget the previous parent list.
        parent[v].clear();
    }
    // if u-> v is a way to get the shortest
    // distance to the destination v.
    if (distance[u] + w == distance[v])
    {
        // add u as a possible parent for v
        parent[v].push_back(u);
    }
}

这与一般的方法略有不同，因为没有"else“。这是相同的逻辑，只是排列有点不同。请注意，当输入第一个if子句时，距离向量会更新，因此也会输入第二个if子句。

我认为处理找到的路径是一个单独的(并且不是微不足道的)问题，所以我将把它留给您来解决如何更新printPath()。不过，我将给出一个版本，它在接收新结果的同时保留旧的输出(只保留最短路径的第一个)。与其说这是一个建议，不如说是一个将新数据结构与旧数据结构联系起来的例证。

// Recursive function to print the path of (just) the first given vertex from source vertex.
void printPath(vector< vector<int> > const &parent, vector<int> const &vlist)
{
    if (vlist.empty())
        return;

    int v = vlist.front();
    printPath(parent, parent[v]);
    cout << v << " ";
}