我目前正在完成一个作业,实现贝尔曼-福德算法。到目前为止,我已经成功读取了提供的图形,并将其放入向量中(使用一维向量表示二维向量,并使用行优先顺序)。我使用一个结构体来跟踪边的权重,一个布尔值来判断是否为无穷大(即没有边存在),以及一个变量来跟踪前面的节点。
我被实际实现该算法所困扰。我已经阅读了http://en.wikipedia.org/wiki/Bellman%E2%80%93Ford_algorithm上的伪代码,但我很难理解如何使用该算法。前80行是读取文件,初始化向量,将值放入正确位置的过程。在此之下是我开始实现该算法的部分。我确实有一些具体问题。
我被实际实现该算法所困扰。我已经阅读了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
while(!input.eof())
更改为while (input >> row)
并在循环内部立即删除提取。您还可以使用std::getline()
和一个中间的istringstream
来处理每一行的循环,使其更加简洁。 - WhozCraig