实现Bellman-Ford算法C++

Question

我目前正在做家庭作业,以实施Bellman-Ford算法.到目前为止,我已经设法读取提供的图形,将其放入向量(使用1d向量表示具有行主要顺序的2d)用作矩阵.我正在使用一个跟踪边缘权重的结构,一个是否为无穷大(没有边缘存在)的布尔值以及一个跟踪前一个节点的变量.

我所困扰的实际上是实现了dang算法.我已经阅读了http://en.wikipedia.org/wiki/Bellman%E2%80%93Ford_algorithm中的伪代码,但我很难掌握如何使用该算法.前80行是在文件中读取,初始化向量,将值扔到正确位置的向量中.下面是我开始为算法实现的内容.我确实有一些具体的问题.

1)在我发现的算法的所有解释中,你使用算法#of nodes - 1次.在我看过的一些实现中,我倾向于从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 http://stackoverflow.com/questions/7651243/c-read-a-file-name-from-the-command-line-and-utilize-it-in-my-file
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

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]访问正确的边。

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