c++ - Bellman ford 实现不起作用

Question

我尝试编写 bellman-ford 算法，但我发现它不起作用。问题是，我(和我问过的任何人)都找不到错误，我认为这一定很简单。起初它似乎是正确的，因为对于我使用它的每个示例，它都很好用，但对于一些更大的示例，它却没有。代码是:

#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。

Answer 1

这一行有一个问题:

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

Bellman-Ford 可能需要多达 v-1 个松弛，而不是 e-1。

假设 e 等于 1，即你有 1 条边。您的程序将不会检测到使用该边缘的路由，因为此 for 循环永远不会进入主体。