문제 설명
Floyd‑Warshall 알고리즘 (Floyd‑Warshall algorithm)
내 코드에 문제가 있는 것 같습니다. 최단 경로에 대해 예상치 못한 값을 얻고 있습니다. 양의 거리만 사용하여 결과를 Dijkstra 및 Bellman의 알고리즘과 비교했으므로 문제는 입력에 있지 않습니다. 또한 무한 거리를 처음에는 0으로 입력한 다음 변환합니다(대각선 제외). 피드백을 보내주시면 감사하겠습니다.
#include <iostream>
#include <limits>
#define infinity std::numeric_limits<int>::max()
void Warshall(int **Adj_Matrix, int vertices){
int i,j,k;
for(k = 0; k < vertices; k++)
for(i = 0; i < vertices; i++)
for(j = 0; j < vertices; j++)
if(Adj_Matrix[i][j] > (Adj_Matrix[i][k] + Adj_Matrix[k][j]))
Adj_Matrix[i][j] = Adj_Matrix[i][k]+Adj_Matrix[k][j];
}
int main(){
int i,j,NumofVertices;
int **Adj_Matrix;
int *Cost_Row;
std::cout<<"Enter the number of vertices: ";
std::cin>>NumofVertices;
Adj_Matrix = new int*[NumofVertices];
for(i = 0;i < NumofVertices; i++){
Adj_Matrix[i] = new int[NumofVertices];
}
std::cout<<"Enter the adjacency matrix"<<std::endl;
for(i = 0; i < NumofVertices; i++){
for(j = 0; j < NumofVertices; j++){
std::cin>> Adj_Matrix[i][j];
if (Adj_Matrix[i][j] == 0 && i != j)
{
Adj_Matrix[i][j] = infinity;
}
}
}
Warshall(Adj_Matrix,NumofVertices);
for(i = 0; i < NumofVertices; i++){
for(j = 0; j < NumofVertices; j++){
std::cout<<"Shortest path between "<<i<<" and "<<j<<" is : ";
if(Adj_Matrix[i][j]==infinity)
std::cout<<"INF"<<std::endl;
else
std::cout<<Adj_Matrix[i][j]<<std::endl;
}
}
return 0;
}
참조 솔루션
방법 1:
The only problem I see with the current code is ::
if(Adj_Matrix[i][j] > (Adj_Matrix[i][k] + Adj_Matrix[k][j]))
So, just in case Adj_Matrix[i][k]
or Adj_Matrix[k][j]
is infinity, then if you try adding something to it, then it is an integer overflow, and the value would be undefined (mostly negative!) which would lead to modifying the value of Adj_Matrix[i][j]
!
To prevent this, you just need to add an if
condition, something like this::
for(k = 0; k < vertices; k++)
for(i = 0; i < vertices; i++)
for(j = 0; j < vertices; j++)
if(Adj_Matrix[i][k] != infinty && Adj_Matrix[j][k] != infinity && Adj_Matrix[i][j] > (Adj_Matrix[i][k] + Adj_Matrix[k][j]))
Adj_Matrix[i][j] = Adj_Matrix[i][k]+Adj_Matrix[k][j];
}
This will make it work, I believe!