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執行不起作用

回答

相關問題