Floyd-Warshall이 C에서 음수 루프를 사용했습니다

Question

플로이드 - 바르샬 알고리즘으로 그래프 검색을하고 있으며 부정 루프를 방지하기 위해이를 변경하는 방법을 모르겠습니다.

은 내가 입력하는 경우 :

From Cost To 
0  -1  1 
1  -2  0 

I 비용 매트릭스를 얻을 :

0 1 
0 -3 -4 
1 -5 -10 

을하고 그것이 그 여전히 부정적인 가장자리를 추가하기 때문에 충돌 및 추가 비용을 감소까지 반복 시작합니다.

int min(int a,int b) 
{return (a<b)? a:b;} 

더 비용이없는 곳 내 distanceMatrix이 INF 있습니다 분은

void FloydWarshall(int ***distanceMatrix, int maxVertices) 
{ 
int from, to, via; 

for(from = 0; from < maxVertices; from++) 
{ 
for(to = 0; to < maxVertices; to++) 
{ 
     for(via = 0; via < maxVertices; via++) 
     { 
     //Fix the negative looping 
     //EDIT FIX: 
     if((*distanceMatrix)[via][via]<0) 
     {fprintf(stderr, "Contains negative cycle!\n"); continue;} 
     //END EDIT 
     //Searches for the cheapest way from all-to-all nodes, if new path 
     // is cheaper than the previous one, its updated in matrix 
     (*distanceMatrix)[from][to] = min((*distanceMatrix)[from][to], 
     ((*distanceMatrix)[from][via]+(*distanceMatrix)[via][to])); 
     } 
} 
} 
} 

. 여전히 루프 추가 비용을 감소, 난 내 기능 대신이 수정 프로그램을 사용하는 경우에도, 그러나

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 

:

나는 통해 변경된 algorythm이 같았다 오래된 주제를했다. 수정 사항이 맞습니까? 그렇지 않다면 어떻게 재 작성해야합니까? 감사.

Answer 1

wikipedia 따라서

에서, 플로이드 - 워셜 알고리즘을 사용하여 음의주기를 검출하기 한 경로 행렬의 대각선을 검사 할 수 및 음수의 존재는 그래프에 포함한다는 것을 나타낸다 적어도 하나는 음수 사이클입니다. [2] 명백히, 무향 그래프에서 음의 에지 은 그 입사각 정점을 포함하는 음의 사이클 (즉, 폐쇄 된 워크)을 생성한다.

그래서 d[k][k] 경우 그냥 종료하고 부정적인주기가 말을해야 어느 작은 0보다.