c++ - 贝尔曼福特实现不起作用

我试图写贝尔曼福特算法，我看到它不起作用。问题是，我（和我问过的任何人）找不到错误，我认为这一定是一件很简单的事情。一开始它看起来是正确的，因为对于我使用的每一个例子，它都很好，但对于一些更大的例子，它却不是。代码是：

#include <iostream>
using namespace std;

long long tab[3001][3001];
long long t[3001];

int main ()
{
int v,e;
cin >> v >> e;
//number of vertices and edges
for (long long i=0;i<=v;i++)
{
    for (long long j=0;j<=v;j++)
    {
        tab[i][j]=20000000000;
    }
}
long long x,y,odl;
for (int i=0;i<e;i++)
{
    //unordered vertices
    cin >> x >> y >> odl;
    tab[x][y]=odl;
    tab[y][x]=odl;
}
for (long long i=1;i<=v;i++)
    tab[i][i]=0;



for (long long i=1;i<=v;i++)
    t[i]=tab[1][i];

bool q;

for (long long i=1;i<e;i++)
{
    q=false;
    for (long long j=1;j<=v;j++)
    {
        for (long long k=1;k<=v;k++)
        {
            if (t[j]>t[k]+tab[k][j])
            {
                t[j]=t[k]+tab[k][j];
                q=true;
            }
        }
    }
    //if there was no changes, break
    if (!q)
        break;
}
for (long long i=1;i<=v;i++)
{
    if (t[i]==20000000000)
        cout << -1<<endl;
    else
        cout << t[i]<<endl;

}
}

它应该不能从1到所有顶点（包括它本身）的最短路径，或者如果我们不能到达-1。

最佳答案

一个问题是这条线：

for (long long i=1;i<e;i++)

贝尔曼福特可能需要最多V-1放松，而不是E-1。
假设e等于1，即你有1条边。程序不会检测到使用该边的路由，因为此for循环永远不会进入主体。

关于c++ - 贝尔曼福特实现不起作用，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/43656345/