MS VS 2010 でフロイド ウォーシャル アルゴリズムを実装しています。ベクター コンテナーを使用しています。これらの一見無害な行:
#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;
}