每对顶点间的最短距离 Floyd_Warshall算法 C++实现

青旅半醒 2022-07-03 13:24 159阅读 0赞

**// 每对顶点间的最短距离Floyd\_Warshall算法.cpp : Defines the entry point for the console application.  
//**

**\#include "stdafx.h"  
\#include<iostream>  
\#define MAX 100  
\#define Infinity 65535  
\#define NIL 65535  
using namespace std;**

**//d  
int d1\[MAX\]\[MAX\];  
int d2\[MAX\]\[MAX\];  
//用来存储边的权值，即有向图的邻接矩阵  
int w\[MAX\]\[MAX\];  
//  
int parent1\[MAX\]\[MAX\];  
int parent2\[MAX\]\[MAX\];**

**//初始化，把w\[i\]\[j\]赋给d\[i\]\[j\]  
void initialise(int n)  
\{  
int i,j;  
for(i=1;i<=n;i++)  
for(j=1;j<=n;j++)  
d1\[i\]\[j\] = w\[i\]\[j\];  
\}**

**//求所有对顶点之间的最短距离  
void Floyd\_Warshall(int n)  
\{  
initialise(n);  
int i,j,k;  
for(k=1;k<=n;k++)  
\{  
for(i=1;i<=n;i++)  
for(j=1;j<=n;j++)  
\{  
if(d1\[i\]\[j\]<=(d1\[i\]\[k\]+d1\[k\]\[j\]))  
\{  
d2\[i\]\[j\] = d1\[i\]\[j\];  
parent2\[i\]\[j\] = parent1\[i\]\[j\];  
\}  
else  
\{  
d2\[i\]\[j\] = (d1\[i\]\[k\]+d1\[k\]\[j\]);  
parent2\[i\]\[j\] = parent1\[k\]\[j\];  
\}  
\}  
for(i=1;i<=n;i++)  
for(j=1;j<=n;j++)  
\{  
d1\[i\]\[j\] = d2\[i\]\[j\];  
parent1\[i\]\[j\] = parent2\[i\]\[j\];  
\}  
\}  
\}**

**void print\_i\_to\_j(int i,int j)  
\{  
int p = parent1\[i\]\[j\];  
if(p==NIL)  
\{  
cout<<"顶点"<<j<<" ";  
return;  
\}  
else  
\{  
print\_i\_to\_j(i,p);  
cout<<"顶点"<<j<<" ";  
\}  
\}**

**void print(int n)  
\{  
int i,j;  
for(i=1;i<=n;i++)  
\{  
for(j=1;j<=n;j++)  
cout<<parent1\[i\]\[j\]<<" ";  
cout<<endl;  
\}**

**\}**

**int \_tmain(int argc, \_TCHAR\* argv\[\])  
\{  
int cases;  
cout<<"请输入案例的个数："<<endl;  
cin>>cases;  
while(cases--)  
\{  
cout<<"请输入顶点个数："<<endl;  
int n;  
cin>>n;  
cout<<"请输入邻接矩阵(n\*n)(如果二点之间没有有向线段，输入65535)："<<endl;  
int i,j;  
//二点之间没有有向线段，输入65535  
for(i=1;i<=n;i++)  
for(j=1;j<=n;j++)  
\{  
cin>>w\[i\]\[j\];  
if(w\[i\]\[j\]==0||w\[i\]\[j\]==65535)  
parent1\[i\]\[j\] = NIL;  
else  
parent1\[i\]\[j\] = i;  
\}  
Floyd\_Warshall(n);  
cout<<"输出每一对顶点间的最短距离："<<endl;  
for(i=1;i<=n;i++)  
for(j=1;j<=n;j++)  
\{  
cout<<"顶点"<<i<<"到顶点"<<j<<"的最短距离为："<<d1\[i\]\[j\]<<endl;  
cout<<"顶点"<<i<<"到顶点"<<j<<"的最短路径为："<<endl;  
print\_i\_to\_j(i,j);  
cout<<endl;  
\}  
\}  
system("pause");  
return 0;  
\}**

**----------------------------------------程序测试-----------------------------------------------**

**请输入案例的个数：  
1  
请输入顶点个数：  
5  
请输入邻接矩阵(n\*n)(如果二点之间没有有向线段，输入65535)：  
0 3 8 65535 -4  
65535 0 65535 1 7  
65535 4 0 65535 65535  
2 65535 -5 0 65535  
65535 65535 65535 6 0  
输出每一对顶点间的最短距离：  
顶点1到顶点1的最短距离为：0  
顶点1到顶点1的最短路径为：  
顶点1  
顶点1到顶点2的最短距离为：1  
顶点1到顶点2的最短路径为：  
顶点1 顶点5 顶点4 顶点3 顶点2  
顶点1到顶点3的最短距离为：-3  
顶点1到顶点3的最短路径为：  
顶点1 顶点5 顶点4 顶点3  
顶点1到顶点4的最短距离为：2  
顶点1到顶点4的最短路径为：  
顶点1 顶点5 顶点4  
顶点1到顶点5的最短距离为：-4  
顶点1到顶点5的最短路径为：  
顶点1 顶点5  
顶点2到顶点1的最短距离为：3  
顶点2到顶点1的最短路径为：  
顶点2 顶点4 顶点1  
顶点2到顶点2的最短距离为：0  
顶点2到顶点2的最短路径为：  
顶点2  
顶点2到顶点3的最短距离为：-4  
顶点2到顶点3的最短路径为：  
顶点2 顶点4 顶点3  
顶点2到顶点4的最短距离为：1  
顶点2到顶点4的最短路径为：  
顶点2 顶点4  
顶点2到顶点5的最短距离为：-1  
顶点2到顶点5的最短路径为：  
顶点2 顶点4 顶点1 顶点5  
顶点3到顶点1的最短距离为：7  
顶点3到顶点1的最短路径为：  
顶点3 顶点2 顶点4 顶点1  
顶点3到顶点2的最短距离为：4  
顶点3到顶点2的最短路径为：  
顶点3 顶点2  
顶点3到顶点3的最短距离为：0  
顶点3到顶点3的最短路径为：  
顶点3  
顶点3到顶点4的最短距离为：5  
顶点3到顶点4的最短路径为：  
顶点3 顶点2 顶点4  
顶点3到顶点5的最短距离为：3  
顶点3到顶点5的最短路径为：  
顶点3 顶点2 顶点4 顶点1 顶点5  
顶点4到顶点1的最短距离为：2  
顶点4到顶点1的最短路径为：  
顶点4 顶点1  
顶点4到顶点2的最短距离为：-1  
顶点4到顶点2的最短路径为：  
顶点4 顶点3 顶点2  
顶点4到顶点3的最短距离为：-5  
顶点4到顶点3的最短路径为：  
顶点4 顶点3  
顶点4到顶点4的最短距离为：0  
顶点4到顶点4的最短路径为：  
顶点4  
顶点4到顶点5的最短距离为：-2  
顶点4到顶点5的最短路径为：  
顶点4 顶点1 顶点5  
顶点5到顶点1的最短距离为：8  
顶点5到顶点1的最短路径为：  
顶点5 顶点4 顶点1  
顶点5到顶点2的最短距离为：5  
顶点5到顶点2的最短路径为：  
顶点5 顶点4 顶点3 顶点2  
顶点5到顶点3的最短距离为：1  
顶点5到顶点3的最短路径为：  
顶点5 顶点4 顶点3  
顶点5到顶点4的最短距离为：6  
顶点5到顶点4的最短路径为：  
顶点5 顶点4  
顶点5到顶点5的最短距离为：0  
顶点5到顶点5的最短路径为：  
顶点5  
请按任意键继续. . .**