弗洛伊德-沃歇尔算法
Floyd-Warshall algorithm
我的代码似乎有问题。我得到了一些最短路径的意外值。我将结果与仅使用正距离的 Dijkstra 和 Bellman 算法进行了比较,因此问题不在于输入。另外,我首先将无限距离输入为零,然后将它们转换(对角线除外)。如有任何反馈,我们将不胜感激。
#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;
}
我看到当前代码的唯一问题是 ::
if(Adj_Matrix[i][j] > (Adj_Matrix[i][k] + Adj_Matrix[k][j]))
所以,以防万一 Adj_Matrix[i][k]
或 Adj_Matrix[k][j]
是无穷大,那么如果你尝试向它添加一些东西,那么它就是一个整数溢出,并且该值将是未定义的(主要是负数! ) 这将导致修改 Adj_Matrix[i][j]
!
的值
为了防止这种情况,您只需要添加一个 if
条件,如下所示::
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];
}
我相信这会成功的!
我的代码似乎有问题。我得到了一些最短路径的意外值。我将结果与仅使用正距离的 Dijkstra 和 Bellman 算法进行了比较,因此问题不在于输入。另外,我首先将无限距离输入为零,然后将它们转换(对角线除外)。如有任何反馈,我们将不胜感激。
#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;
}
我看到当前代码的唯一问题是 ::
if(Adj_Matrix[i][j] > (Adj_Matrix[i][k] + Adj_Matrix[k][j]))
所以,以防万一 Adj_Matrix[i][k]
或 Adj_Matrix[k][j]
是无穷大,那么如果你尝试向它添加一些东西,那么它就是一个整数溢出,并且该值将是未定义的(主要是负数! ) 这将导致修改 Adj_Matrix[i][j]
!
为了防止这种情况,您只需要添加一个 if
条件,如下所示::
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];
}
我相信这会成功的!