我在 MS VS 2010 中实现了一个 floyd-warshall 算法。我正在使用向量容器。这些看似无辜的台词:
#include <iostream>
#include <iomanip>
#include <vector>
#include <fstream>
#include <string>
#include <limits>
using namespace std;
const double inf = numeric_limits<double>::infinity();
struct node{
int value;
//path not used here
//node *predecessor;
};
struct edge{
int source;
int target;
double weight;
};
vector<edge> EDGES;
当我在 main() 正文开始处的断点处停止时,导致调试器出现问题:我没有将 EDGES 作为它应该的漂亮菜单,而是在名称处得到一个红色感叹号,并且 CXX0004:错误:语法错误。尝试运行程序会导致调试断言:向量下标超出范围。在我制作的类似程序中,完全相同的行工作正常。怎么了?
这是整个代码:
#include <iostream>
#include <iomanip>
#include <vector>
#include <fstream>
#include <string>
#include <limits>
using namespace std;
const double inf = numeric_limits<double>::infinity();
struct node{
int value;
//path not used here
//node *predecessor;
};
struct edge{
int source;
int target;
double weight;
};
vector<edge> EDGES;
vector<node> V;
vector< vector< vector< double > > > R;
int u;//source
unsigned Ecount,Vcount;
void insert_from_keyboard(void)
{
unsigned i,j;
cout<<"Keyboard insertion selected. Enter vertex count: ";
cin>>Vcount;
V.resize(Vcount);
for(i=0;i<Vcount;i++)
V[i].value=i+1;//naming nodes, start from 1
R.resize(Vcount+1);
for(i=0;i<Vcount+1;i++)
{
R[i].resize(Vcount);
for(j=0;j<Vcount;j++)
R[i][j].resize(Vcount,inf);
}
cout<<"Nodes 1 to "<<Vcount<<" created.\nEnter edge count: ";
cin>>Ecount;
EDGES.resize(Ecount);
cout<<"Enter "<<Ecount<<" triplets representing directed edges (source, target, weight): ";
for(i=0;i<Ecount;i++)
cin>>EDGES[i].source>>EDGES[i].target>>EDGES[i].weight;
return;
}
bool floyd_warshall(void)
{
unsigned i,j,k;
for(i=0;i<Vcount;i++)
R[0][i][i] = 0;
for(i=0;i<Ecount;i++)
R[0][EDGES[i].source-1][EDGES[i].target-1] = EDGES[i].weight;
for(i=1;i<Vcount+1;i++)
for(j=0;j<Vcount;j++)
for(k=0;k<Vcount;k++)
R[i][j][k]= R[i-1][j][k] > R[i-1][j][i] + R[i-1][i][k] ? R[i-1][j][i] + R[i-1][i][k] : R[i-1][j][k];
for(i=0;i<Vcount;i++)
for(j=0;j<Vcount;j++)
if ( R[i][j][j]<0 )
return false;
return true;
}
void printR()
{
//printing routine, should not bother....
//the log function is used to calculate maximum length of numbers, used for formatting...
unsigned l,i,j, wl=5, wd=8;//width for printing whitespacEDGES l for L(...), d for data
for(l=0;l<Vcount+1;l++)
{
cout<<"R("<<setw(wl)<<l+1<<"):\n\n";
for(i=0;i<Vcount;i++)
{
cout<<setw(5+wl+wd/2)<<R[l][i][0];
for(j=1;j<Vcount;j++)
cout<<setw(wd)<<R[l][i][j];
cout<<endl;
}
cout<<"\n\n";
}
}
void insert_from_file(string filename)
{
unsigned i,j;
ifstream f (filename.c_str());
f>>Vcount>>Ecount;
V.resize(Vcount);
for(i=0;i<Vcount;i++)
V[i].value=i+1;//naming nodes, start from 1
R.resize(Vcount+1);
for(i=0;i<Vcount+1;i++)
{
R[i].resize(Vcount);
for(j=0;j<Vcount;j++)
R[i][j].resize(Vcount,inf);
}
EDGES.resize(Ecount);
for(i=0;i<Ecount;i++)
f>>EDGES[i].source>>EDGES[i].target>>EDGES[i].weight;
f.close();
cout<<"Insert from file "<<filename<<" successful\n\n";
}
int main(void)
{
//insert_from_keyboard();
insert_from_file("A22.txt");
bool result =floyd_warshall();
printR();
cout<<"Result of algorithm: "<<(result ? "TRUE, no negative" : "FALSE, negative" )<<" cycles encountered.\n";
system("PAUSE");
return 0;
}