// 每對頂點間的最短路徑.cpp : Defines the entry point for the console application.
//
#include "stdafx.h"
#include<iostream>
#define MAX 100
#define Infinity 65535
using namespace std;
//
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]+w[k][j])?L2[i][j]:(L1[i][k]+w[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
請按任意鍵繼續. .
作者 heyongluoyao8
