傳回目錄：
Chilan Yu：《資料結構》目錄連結zhuanlan.zhihu.com
迪傑斯特拉算法隻能求出從源點到其他頂點的最短路徑，欲求任意一對頂點間的最短路徑，可以将每一頂點作為源點，重複調用迪傑斯特拉算法n次，其時間複雜度為
。
下面介紹一種形式更簡單的方法，即
佛羅伊德算法，其時間複雜度也是
。
2. 求任意一對頂點間的最短路徑 例7.5：利用佛羅伊德算法，求圖7.27（a）所示的帶權有向圖中G6的每一對頂點之間的最短路徑P及其長度D。7.27（c）給出了G6的每一對頂點之間的最短路徑P及其路徑長度D。 【
算法思想】
設圖g用鄰接矩陣法表示，求圖g中任意一對頂點vi、vj間的的最短路徑。（注：以下序号是與圖7.27中D、P的上标序号對應的）。
（-1）将vi到vj 的最短的路徑長度初始化為
，然後進行如下n次比較和修正：
（0）在vi、vj間加入頂點v0，比較（vi,v0,vj）和(vi,vj)的路徑的長度，取其中較短的路徑作為vi到vj 的且中間頂點号不大于0的最短路徑。
（1）在vi、vj間加入頂點v1，得（vi,…， v1）和(v1,…， vj)，其中（vi,…,v1）是vi到v1 的且中間頂點号不大于0的最短路徑，(v1,…,vj) 是v1到vj 的且中間頂點号不大于0的最……短路徑，這兩條路徑在上一步中已求出。将（vi,…,v1,…,vj）與上一步已求出的且vi到vj 中間頂點号不大于0的最短路徑比較，取其中較短的路徑作為vi到vj 的且中間頂點号不大于1的最短路徑。
（2）在vi、vj間加入頂點v2，得（vi,…,v2）和(v2,…,vj)，其中（vi,…,v2）是vi到v2 的且中間頂點号不大于1的最短路徑，(v2,…,vj) 是v2到vj 的且中間頂點号不大于1的最短路徑，這兩條路徑在上一步中已求出。将（vi,…,v2,…,vj）與上一步已求出的且vi到vj 中間頂點号不大于1的最短路徑比較，取其中較短的路徑作為vi到vj 的且中間頂點号不大于2的最短路徑。
………
依次類推，經過n次比較和修正，在第（n-1）步，将求得vi到vj 的且中間頂點号不大于n-1的最短路徑，這必是從vi到vj的最短路徑。
圖g中所有頂點偶對vi、vj間的最短路徑長度對應一個n階方陣D。在上述n+1步中，D的值不斷變化，對應一個n階方陣序列。
定義：
n階方陣序列：D-1, D0, D1, D2, …Dn-1
其中 :
顯然，Dn-1中為所有頂點偶對vi、vj間的最終最短路徑長度。
#include <iostream>
#include <stdio.h>
#include <stdlib.h>
using namespace std;
#define MAX_VERTEX_NUM 20//最多頂點個數
#define INFINITY 32768//表示極大值
#define ElemType int
typedef struct Graph{
int arcs[MAX_VERTEX_NUM][MAX_VERTEX_NUM];//二維數組存儲鄰接矩陣
int vexnum;//頂點數
}Graph;
/*矩陣建圖/網*/
//圖：0表示沒有邊，1表示有邊
//網：0表示沒有邊，非0表示邊上權值
void CreateMatrix(Graph * G){//一般從下标0開始存圖
cout << "請輸入矩陣：" << endl;
int x;
for(int i=0;i<G->vexnum;++i){
G->visited[i] = 0;
for(int j=0;j<G->vexnum;++j){
cin >> x;
if(x) G->arcs[i][j] = x;
else G->arcs[i][j] = INFINITY;
if(i==j) G->arcs[i][j] = 0;
}
}
}
typedef struct{
ElemType elem[MAX_VERTEX_NUM];//線性表占用的數組空間
int last;//記錄線性表中最後一個元素在數組elem[]中的位置（下标值），空表置為-1
}SeqList;
void AddTail(SeqList *L,ElemType e){//在順序表末尾插入一個元素e
L->last++;
L->elem[L->last] = e;
}
void InitList(SeqList * L){
L->last = -1;
}
SeqList JoinList(SeqList L1,SeqList L2){
for(int i=0;i<=L2.last;++i)
L1.elem[++L1.last] = L2.elem[i];
return L1;
}
void Floyd(Graph G,int dist[MAX_VERTEX_NUM][MAX_VERTEX_NUM],SeqList path[MAX_VERTEX_NUM][MAX_VERTEX_NUM]){
//path[i][j]為vi到vj的目前最短路徑
//dist[i][j]為vi到vj的目前最短路徑長度
for(int i=0;i<G.vexnum;++i){//初始化dist[i][j]和path[i][j]
for(int j=0;j<G.vexnum;++j){
InitList(&path[i][j]);
dist[i][j] = G.arcs[i][j];
if(dist[i][j]<INFINITY){
AddTail(&path[i][j],i);
AddTail(&path[i][j],j);
}
}
}
for(int k=0;k<G.vexnum;++k){
for(int i=0;i<G.vexnum;++i){
for(int j=0;j<G.vexnum;++j){
if(dist[i][k]+dist[k][j]<dist[i][j]){
dist[i][j] = dist[i][k]+dist[k][j];
path[i][j] = JoinList(path[i][k],path[k][j]);
}
}
}
}
}
int main()
{
Graph G;
SeqList path[MAX_VERTEX_NUM][MAX_VERTEX_NUM];
int dist[MAX_VERTEX_NUM][MAX_VERTEX_NUM];
cout << "請輸入頂點數：";
cin >> G.vexnum;
CreateMatrix(&G);
Floyd(G,dist,path);
for(int i=0;i<G.vexnum;++i){
for(int j=0;j<G.vexnum;++j){
cout << "從" << i << "到" << j << "：";
for(int k=0;k<=path[i][j].last;++k)
cout << path[i][j].elem[k] << " ";
cout << endl;
if(dist[i][j]==INFINITY) cout << -1 << endl;
else cout << "其最短路徑長度為" << dist[i][j] << endl;
}
}
return 0;
}
傳回目錄：
Chilan Yu：《資料結構》目錄連結zhuanlan.zhihu.com