Bellman Ford가 무작위로 잘못된 결과를 내고 있습니다.

Question

CLRS에서 Bellman Ford Algorithm을 구현하려고하는데, 무작위로 거리 측정기에서 오버플 로인 것처럼 보입니다. 내 코드는 다음과 같이 코드에 대한

private void initSingleSource(Vertice source) { 
    for(Vertice vertice:vertices) { 
     vertice.distance = Integer.MAX_VALUE; 
     vertice.predecessor = null; 
    } 
    source.distance = 0; 
} 

private void relax(Vertice u, Vertice v, int weight) { 
    if(v.distance > u.distance + weight) { 
     v.distance = u.distance + weight; 
     v.predecessor = u; 
    } 
} 

public boolean bellmanFord(Vertice source) { 
    initSingleSource(source); 
    for(int i = 0; i < vertices.size()-1; i++) { 
     for(Vertice u: edges.keySet()) { 
      Hashtable<Vertice, Integer> table = edges.get(u); 
      for(Vertice v: table.keySet()) { 
       relax(u, v, table.get(v)); 
      } 
     } 
    } 
    for(Vertice u: edges.keySet()) { 
     Hashtable<Vertice, Integer> table = edges.get(u); 
     for(Vertice v: table.keySet()) { 
      if(v.distance > u.distance + table.get(v)) { 
       return false; 
      } 
     } 
    } 

    return true; 
} 

입력은 다음과 같습니다이다 나는 무작위로 얻을

g.addAdjList(A, B, 6); 
g.addAdjList(A, D, 7); 
g.addAdjList(B, C, 5); 
g.addAdjList(B, D, 8); 
g.addAdjList(B, E, -4); 
g.addAdjList(C, B, -2); 
g.addAdjList(D, C, -3); 
g.addAdjList(D, E, 9); 
g.addAdjList(E, C, 7); 
g.addAdjList(E, A, 2); 

정답 :

B 2 C 4 D 7 E - 2

그렇지 않으면 :

B -2147483636 C -2147483634 D -2147483631 E -2147483640

어떤 생각이 왜 이런 일이 일어나고 있는가?

Answer 1

relax이 u과 같이 호출되어 u.distance 수식 Integer.MAX_VALUE과 같이 호출 될 때 문제가 발생한다고 생각합니다. 그런 다음 u.distance + weight은 음수입니다 (합계가 범위를 벗어납니다). 이 음수 값은 v.distance보다 작으며 v.distance에 할당됩니다.

relax 호출 순서에 따라 문제가 발생할 수 있습니다. table.keySet()을 사용하면 순서가 임의입니다. DFS가 수행 할 순서대로 정점을 고려해야 할 운이 있다면 올바른 결과를 얻어야하지만 그럴 가능성은 없습니다.

가능한 해결 방법

private void relax(Vertice u, Vertice v, int weight) { 
    if(u.distance != Integer.MAX_VALUE && v.distance > u.distance + weight) { 
     v.distance = u.distance + weight; 
     v.predecessor = u; 
    } 
}