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++) 

벨만 - 포드는 전자-1, V-1 이완에 없습니다까지해야 할 수도 있습니다.

e가 1과 같다고 가정합니다. 즉, 가장자리가 1입니다. 이 for 루프는 절대로 본문에 들어 가지 않으므로 프로그램은 해당 가장자리를 사용하는 경로를 감지하지 못합니다.