每对顶点间的最短路径算法时间复杂度改进C++实现

小咪咪 2022-07-03 13:00 165阅读 0赞

**// 每对顶点间的最短路径.cpp : Defines the entry point for the console application.  
//**

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

**//L2\[i\]\[j\]存储L1\[i\]\[j\]\*Lij  
int L1\[MAX\]\[MAX\];  
int L2\[MAX\]\[MAX\];  
//用来存储边的权值，即有向图的邻接矩阵  
int w\[MAX\]\[MAX\];**

**//初始化，把w\[i\]\[j\]赋给L1\[i\]\[j\]  
void initialise(int n)  
\{  
int i,j;  
for(i=1;i<=n;i++)  
for(j=1;j<=n;j++)  
L1\[i\]\[j\] = w\[i\]\[j\];  
\}  
//求每一对顶点间暂时最短距离  
void extend\_shortest\_paths(int n)  
\{  
int i,j,k,l;  
for(i=1;i<=n;i++)  
\{  
for(j=1;j<=n;j++)  
\{  
L2\[i\]\[j\] = Infinity;  
for(k=1;k<=n;k++)  
//改进  
L2\[i\]\[j\] = L2\[i\]\[j\]<(L1\[i\]\[k\]+L1\[k\]\[j\])?L2\[i\]\[j\]:(L1\[i\]\[k\]+L1\[k\]\[j\]);  
\}  
\}  
for(i=1;i<=n;i++)  
for(j=1;j<=n;j++)  
L1\[i\]\[j\] = L2\[i\]\[j\];  
\}**

**//求所有对顶点之间的最短距离  
void show\_all\_pairs\_shortest\_paths(int n)  
\{  
initialise(n);  
int m;  
for(m=2;m<=n-1;m++)  
extend\_shortest\_paths(n);  
\}  
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\];  
\}  
show\_all\_pairs\_shortest\_paths(n);  
cout<<"输出每一对顶点间的最短距离："<<endl;  
for(i=1;i<=n;i++)  
for(j=1;j<=n;j++)  
\{  
cout<<"顶点"<<i<<"到顶点"<<j<<"的最短距离为："<<L1\[i\]\[j\]<<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到顶点2的最短距离为：1  
顶点1到顶点3的最短距离为：-3  
顶点1到顶点4的最短距离为：2  
顶点1到顶点5的最短距离为：-4  
顶点2到顶点1的最短距离为：3  
顶点2到顶点2的最短距离为：0  
顶点2到顶点3的最短距离为：-4  
顶点2到顶点4的最短距离为：1  
顶点2到顶点5的最短距离为：-1  
顶点3到顶点1的最短距离为：7  
顶点3到顶点2的最短距离为：4  
顶点3到顶点3的最短距离为：0  
顶点3到顶点4的最短距离为：5  
顶点3到顶点5的最短距离为：3  
顶点4到顶点1的最短距离为：2  
顶点4到顶点2的最短距离为：-1  
顶点4到顶点3的最短距离为：-5  
顶点4到顶点4的最短距离为：0  
顶点4到顶点5的最短距离为：-2  
顶点5到顶点1的最短距离为：8  
顶点5到顶点2的最短距离为：5  
顶点5到顶点3的最短距离为：1  
顶点5到顶点4的最短距离为：6  
顶点5到顶点5的最短距离为：0  
请按任意键继续. . .**