实现Bellman-Ford算法C++

Question

我目前正在完成一个作业，实现贝尔曼-福德算法。到目前为止，我已经成功读取了提供的图形，并将其放入向量中（使用一维向量表示二维向量，并使用行优先顺序）。我使用一个结构体来跟踪边的权重，一个布尔值来判断是否为无穷大（即没有边存在），以及一个变量来跟踪前面的节点。

我被实际实现该算法所困扰。我已经阅读了http://en.wikipedia.org/wiki/Bellman%E2%80%93Ford_algorithm上的伪代码，但我很难理解如何使用该算法。前80行是读取文件，初始化向量，将值放入正确位置的过程。在此之下是我开始实现该算法的部分。我确实有一些具体问题。

1) 在我找到的所有算法解释中，你需要运行算法节点数减一次。在我查看的一些实现中，i往往从1开始。为什么会这样？此外，对于我的实现，这还有意义吗？

2) 此外，在维基百科的伪代码中，它说要检查每个边缘u,v，其中u是起始顶点，v是结束顶点。在我的矩阵中，就我所知，这意味着我需要检查每行、每列对的权重/值，并查看是否有更好的路径。我不确定我是否正确地解释了这一点，甚至是否在这个时候理解了它。任何建议/指导/提示/演示都将不胜感激。下面是源代码和讲师演示输入的粘贴。

#include <fstream>
#include <iostream>
#include <iomanip>
#include <vector>

using namespace std;

struct graphNode
{
    int value; //Weight of the edge
    bool isInfinity; //Boolean to flag an edge as infinity
    int pred; //predecessor node
};

// Code for reading inputfile cribbed and modified from https://dev59.com/IVvUa4cB1Zd3GeqPx-jG
int main(int argc, char** argv) 
{
    ifstream input; // ifstream for the input
    string inFile = ""; //name of the input file
    int row; //Variable to keep track of what row we're inputting data for
    int col; //Variable to keep track of a column thingie, expand on this later
    int infinity = 99999999;
    int nodeCount; //Number of nodes from input file
    int edgeCount = 0; //Number of edges from the input file

    vector<graphNode> edgeList; //2D list of edges, order is a->b
    edgeList.push_back(graphNode());
    edgeList[0].value = 0;
    edgeList[0].isInfinity = false;
    edgeList[0].pred = -1;

    if( argc == 2 ) 
    {
        inFile = argv[1];
    }
    else 
    {
        cout << "Usage: ./a.out inputFile\n";
        return 1;
    }

    input.open(inFile.c_str()); // opening the provided file

    if(input.is_open()) // making sure the input is open
    {
        input >> nodeCount; //Grabbing the number of nodes from the first value of the file

        for(int i = 1; i < nodeCount*nodeCount; i++)
        {
            edgeList.push_back(graphNode());
            edgeList[i].value = infinity;
            edgeList[i].isInfinity = true;
            edgeList[i].pred = -1;
        }

        //Putting data from the file into the vector array
        while(!input.eof())
        {
            input >> row; //For each cycle through the list, we grab the first number on the line to get which x value (start vertex) we're working with
            while(input.peek() != '\n' && input.peek() != '\r' && !input.eof())
            {
                input >> col;
                input >> edgeList[((row-1)*nodeCount)+(col-1)].value;
                edgeList[((row-1)*nodeCount)+(col-1)].isInfinity = false;
                edgeList[((row-1)*nodeCount)+(col-1)].pred = row;
                edgeCount++;
            }

        }
        input.close(); //Closing our input file since we don't need it anymore
    }
    else
    {
        cout << "Error, something happened with the input." << endl;
        return 1;
    }

    //for(int i = 0; i < nodeCount - 1; i++)
    //{
        //for(int r = 0; r < nodeCount - 1; r++)
        //{
            //for(int c = 0; r < nodeCount - 1; c++)
            //{
                //if(r == c) continue;
                //if(edgeList[r][c].isInfinity) continue;
                //if(edgeList[i][r] + edgeList[r][c] < edgeList[c][i])
}

演示输入：

10
3 6 4 9 0 7 8
8 5 3 7 3 4 -2
5 10 2 8 1 4 1
2 6 -3 1 3 7 1
1 10 -1 2 2 4 -2
10 9 -3 1 3 7 2 5 1
7 3 0 10 1 2 1 8 2
9 6 6 3 4 10 7
4 8 5 1 9 5 6
6 2 4 3 0 9 0

- Ron Holcomb

---

略微相关：将 while(!input.eof()) 更改为 while (input >> row) 并在循环内部立即删除提取。您还可以使用 std::getline() 和一个中间的 istringstream 来处理每一行的循环，使其更加简洁。 - WhozCraig

说句实话，这是我 Python 实现的链接，或许可以帮到你：https://github.com/ezod/hypergraph/blob/master/hypergraph/path.py#L58 - ezod

Answer 1

对于#1，您正在检查节点之间的边缘，以使最长路径不能超过nodeCount-1个边缘。例如，如果nodeCount==1，则无需检查任何边缘。

对于#2，您有一些有趣的数据结构。看起来您需要不同的结构。您的“graphNode”应该被称为“graphEdge”，但不包含“pred”变量。声明两个新结构：

vector<int> predecessor;
vector<int> distance;

每个节点的大小都是nodeCount。在维基百科中看到的“w”就是你的edgeList。

在你注释掉的最后一部分中，外部循环迭代了nodeCount次。虽然没有关系，但应该是nodeCount-1。然而，你后面的索引有问题，因为你有一个一维的edgeList，但你正在将其视为二维的。你可以通过edgeList [(r-1)*nodeCount + c]访问正确的边缘。

不确定这是否算作答案，但这是一个开始。

- dan

Answer 2

请查看这里关于Bellman-Ford算法的短视频。我认为它可能会帮助您更好地理解该算法：https://class.coursera.org/algo2-2012-001/lecture/preview 基本上，Bellman-Ford背后的主要思想是：

为了找到两个节点s和t之间的最短路径，您可以迭代地找到从s到t的最短路径，并在每个后续迭代中，允许算法使用比先前迭代中的路径多1条边。

在任何特定的迭代k中，您现在允许算法在路径中使用最多k条边，s和t之间的最短路径可以是以下两种情况之一：

1. 通过使用恰好k条边改进

2. 使用与前一次迭代相同的值，即使用最多(k-1)条边。

因此，在特定的迭代k中：

令d[k][t]为使用最多k条边从s到节点t的距离。然后：

d[ k ][ t ] = min{ 
d[k - 1][ t ], # Case 2
for all edges (u, t) in graph min d[k - 1][ u ] + c[ u ][ t ] # Case 1
}

上述min{ ., .}方程的第二部分仅查找从s到终点t的任何邻居u之间的最短路径，并添加边缘c [ u ] [ t] 的成本以从u到t，从而需要恰好 k条边。

因此，伪代码如下：

d[s][0] = 0 # The cost from s to itself requiring zero edges is 0.
d[u][0] = INFINITY for all other nodes other than s (i.e. you cannot reach them with no edges).

Let n = number of nodes in graph
for k = 1 to n - 1: # Allow one more edge in path in each iteration
  for every edge (u, v) in edges of graph: # Check whether can get a better cost to v using k edges by going through node u or k - 1 edges is enough.
    d[ v ][ k ] = min{ d[k - 1][ v ], d[k - 1][ u ] + c[ u ][ v ] }

回答你问题的第一部分，考虑到方程的外层循环遍历边的数量。它从1增加到n-1，其中n是图中节点的数量。之所以是n-1，是因为在路径中最多有(n-1)条边（即您需要连接所有n个节点以从s到t，它们之间有n-1条边）。

回答你问题的第二部分，您只需要考虑到每个目标节点的入站节点，并检查使用k-1条边到达这些节点中的任何一个节点的路径加上该节点到目标节点的成本是否比之前更少，正如我上面所解释的那样。

最后，要检查负循环（wiki代码中的最后一部分），您需要再运行算法一次。我们知道任何路径最多可以使用n-1条边。更多的边会是冗余的。因此，如果允许使用1条以上的边时任何路径的成本降低，它必须包含负循环，因为这是它的成本可能会降低的唯一方式。任何非负循环都会导致相同或更大的成本，因为它使用了更多的边。

我强烈建议观看上面链接中的Tim Roughgarden视频。请注意，他的处理方式与维基百科中的伪代码略有不同，但思想本质上是相同的。

- lightalchemist