Bellman ford执行不起作用

我试图写bellman-ford算法，我发现它没有工作。问题是，我（和任何我问过的人）找不到这个错误，我认为这一定是一件简单的事。起初，它似乎是正确的，因为我使用它的每个例子都很好，对于一些较大的，它不会。该代码是：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，如果我们不能达到它。

来源

2017-04-27 Junak

请包括如何不起作用的精确描述。 “不起作用”在尝试修理某些东西时毫无用处 – user463035818

+10

Bellman-Ford工作得很好。这是你的实施贝尔曼福特不工作。 –

@MikeNakis阿格没有投票，因为我觉得自己喜欢两次。它可能被认为是挑剔的，但是imho区分破坏的算法和破坏的实现是非常重要的 – user463035818

的一个问题是这一行：

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

贝尔曼 - 福特可能需要多达V-1松弛，没有E-1。

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

来源

2017-04-27 11:48:54

好吧，好点，它应该是我= 0，但我不认为它应该在那里; – Junak

我的意思是，虽然它只有一个边缘，它只需要一次迭代就可以找到答案 – Junak

@Junak只需打开下一个算法书并查看Bellman-Ford算法。它使用N-1次迭代来放松边缘，其中N是顶点的数量。 – pschill

Bellman ford执行不起作用

回答

相关问题