Floyd-Warshall에 부정적인 사이클이 있습니다. 정의되지 않은 경로는 어떻게 찾습니까?

Question

Floyd Warshall 알고리즘을 구현했으며 작동하지만 문제는 정의되지 않은 모든 경로를 찾을 수있는 방법을 모르는 것입니다. 웹에서 검색했지만 그래프에 음수 사이클이 있는지 여부를 감지하는 방법에 대한 해답을 찾을 수 있습니다.

vector< vector <int> > floyd_warshall(vector< vector<int> > d, int n){ 
    for(int i = 0; i < n; i++) d[i][i] = 0; 

    for(int i = 0; i < n; i++){ 
     for(int j = 0; j < n; j++){ 
      for(int k = 0; k < n; k++){ 
       if(d[j][i] + d[i][k] < d[j][k] and d[j][i] != INF and d[i][k] != INF){ 
        d[j][k] = d[j][i] + d[i][k]; 
       } 
      } 
     } 
    } 

    return d; 
} 

그래프의 알고리즘을 실행 한 후 :

from: to: weight: 
0  1  1 
1  2  -1 
2  1  -1 
1  3  1 
4  0  1 

I은 ​​인접 행렬 얻을 :

| 0  1  2  3  4 
--|---------------------------- 
0 | 0 -1 -2 -2  INF 
1 | INF -2 -3 -3  INF 
2 | INF -3 -4 -4  INF 
3 | INF INF INF 0  INF 
4 | 1 -2 -3 -7  0 

I 노드 나 음 사이클의 일부인 경우, 그것은이 있는지 알고 행렬의 위치 d [i] [i]에 음수 값. 따라서 행렬의 대각선을 검사하면 음수 사이클의 일부인 모든 노드를 찾을 수 있습니다. 위의 예제를 보면 노드 1과 노드 2가 음수 사이클의 일부임을 알 수 있습니다. 것은 정의 된 경로와 정의되지 않은 경로를 찾고 싶습니다. A에서 B까지의 여물에서 음수 사이클이 올 수있는 경우 경로의 길이는 임의로 작을 수 있으므로 정의되지 않아야합니다.

질문은 어떻게 정의되지 않은 경로를 모두 찾을 수 있습니까?

는 I 매트릭스 돌아 알고리즘을 원한다 (대신에 상술 한)

| 0  1  2  3  4 
--|---------------------------- 
0 | 0 -INF -INF -INF INF 
1 | INF -INF -INF -INF INF 
2 | INF -INF -INF -INF INF 
3 | INF INF INF  0 INF 
4 | 1 -INF -INF -INF 0 

D를 [I] [J] INF는 i와 j와 사이에 경로가 없다는 것을 의미 = - INF는 i와 j 사이에 임의의 작은 경로가 있음을 의미합니다 (경로가 음수 루프를 어딘가에 전달 함). 그렇지 않으면 i와 j 사이의 최단 길이 인 d [i] [j]입니다.

나는 모든 단일 경로에서 테스트 할 생각 이었지만, 아마도 너무 느릴 것입니다. 이 문제를 해결하기위한 표준 방법이 있어야합니다.

고맙습니다.

Answer 1

글쎄, 내 자신의 문제에 대한 해결책을 찾았습니다.

for(int i = 0; i < n; i++) 
    for(int j = 0; j < n; j++) // Go through all possible sources and targets 

     for(int k = 0; d[i][j] != -INF && k < n; k++) 
      if(d[i][k] != INF && // Is there any path from i to k? 
       d[k][j] != INF && // Is there any path from k to j? 
       d[k][k] < 0)  // Is k part of a negative loop? 

       d[i][j] = -INF; // If all the above are true 
            // then the path from i to k is undefined 

제대로 작동해야한다고 생각합니다.

Answer 2

Floyd-Warshall 알고리즘은 음수가 입력 그래프에 이 없으면 올바른 결과를 출력합니다. 부정적인주기가있는 경우 가장 짧은 (단순한) 경로를 계산하는 것은 NP 어려운 문제이며 Floyd-Warshall 알고리즘은 올바른 결과를 출력하지 않습니다.

그러나 행렬의 대각선에 음수 항목이 있는지 확인하여 음수 사이클의 존재를 감지 할 수 있습니다.

1. M[i, j] := ∞ ∀i 6= j 
2. M[i, i] := 0 ∀i 
3. M[i, j] := c((i, j)) ∀(i, j) ∈ E(G) 

4. for i := 1 to n do 
5. for j := 1 to n do 
6.  for k := 1 to n do 
7.  if M[j, k] > M[j, i] + M[i, k] 
      then M[j, k] := M[j, i] + M[i, k] 

8. for i := 1 to n do 
9. if M[i, i] < 0 then return(’graph contains a negative cycle’) 

Source

Answer 3

플로이드 - 워셜 알고리즘은 포지티브 또는 네거티브 가중 된 그래프에서 노드들의 모든 쌍들 사이의 최단 경로를 찾는 데 사용된다 : 이것은이 알고리즘의 라인 8 및 9 행에서 수행 가장자리 무게.

다음 알고리즘은 인접 행렬을 허용합니다. 여기서 Double.POSITIVE_INFINITY는 두 노드가 연결되지 않음을 나타냅니다. 각 노드마다 0의 가중치를 자체에 초기화하려고 할 것입니다.

이 메서드는 모든 노드 쌍 간의 최소 거리를 나타내는 초기 행렬을 업데이트합니다. 최단 경로가 임의로 작은 경우, 대답은 Double.NEGATIVE_INFINITY로 저장됩니다. 두 노드가 서로 연결할 수 없다면 여전히 Double.POSITIVE_INFINITY입니다. 이 구현은 Floyd Warshall을 두 번 실행하고 경로 길이가 이전보다 작 으면 우리는 음수 사이클이됩니다.

static void floydWarshall(double[][] dist) { 

    int n = dist.length; 

    // Compute shortest paths 
    for (int k = 0; k < n; k++) 
    for (int i = 0; i < n; i++) 
     for (int j = 0; j < n; j++) 
     if (dist[i][k] + dist[k][j] < dist[i][j]) 
      dist[i][j] = dist[i][k] + dist[k][j]; 

    // Identify negative cycles 
    for (int k = 0; k < n; k++) 
    for (int i = 0; i < n; i++) 
     for (int j = 0; j < n; j++) 
     if (dist[i][k] + dist[k][j] < dist[i][j]) 
      dist[i][j] = Double.NEGATIVE_INFINITY; 

}