0

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;
}
4

0 に答える 0