作者热门文章
- iOS/Objective-C 元类和类别
- objective-c - -1001 错误,当 NSURLSession 通过 httpproxy 和/etc/hosts
- java - 使用网络类获取 url 地址
- ios - 推送通知中不播放声音
我的代码似乎有问题。我得到了一些最短路径的意外值。我将结果与仅使用正距离的 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];
}
我相信这会成功的!
关于c++ - 弗洛伊德-沃歇尔算法,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/34110552/
我是一名优秀的程序员,十分优秀!