1 Floyd算法

1.1 Code

/**
 * 弗洛伊德(Floyd)算法: 
        1 解决问题: 多源最短路径问题
                        求每一对顶点之间的最短路径
                        Background: 带权有向图
        2 算法思想: 动态规划(DP, Dynamic Programming) 
        3 时间复杂度: O(n^3) 
 */
#include<stdio.h>
#include<iostream>
using namespace std;
 
// 1 定义图模型(邻接矩阵表示法)的基本存储结构体
# define MaxInt 32767 // 表示极大值 即 ∞ (无穷大)
# define MVNum 100 // 最大顶点数 
typedef int VertexType; // 假设顶点的数据类型为整型
typedef int ArcType; // 假设Vi与Vj之边的权值类型为整型 
typedef struct {
    VertexType vexs[MVNum]; // 顶点表 (存储顶点信息)
    ArcType arcs[MVNum][MVNum]; // 邻接矩阵
    int vexnum,arcnum; // 图的当前顶点数与边数 
}AMGraph; // Adjacent Matrix Graph 邻接矩阵 
 
// 2 定义Floyd算法的辅助数据结构体
ArcType D[MVNum][MVNum]; // 记录顶点Vi和Vj之间的最短路径长度 
int Path[MVNum][MVNum];  // 最短路径上顶点Vj的前一顶点的序号 

/////////////////////// ↓算法区↓ ///////////////////////

void ShortestPath_Floyd(AMGraph G){
    //step1 初始化各对结点的已知路径和距离 
    for(int i=0;i<G.vexnum;i++){
        for(int j=0;j<G.vexnum;j++){
            D[i][j] = G.arcs[i][j]; //D[i][j] 初始化 
            if(D[i][j]<MaxInt && i!=j){ // 【易漏】 i != j (防止产生自回环)
                Path[i][j] = i; // 若 Vi与Vj之间存在弧(有序顶点对)： 将Vj的前驱置为 Vi 
            } else {
                Path[i][j] = -1;
            }
        }
    }
    //step2 动态规划(DP)动态更新： <Vi,Vj>更短的最短路径的距离和路径
    for(int k=0;k<G.vexnum;k++){ // 【易错】 中间结点Vk的循环 是在最外层 
        for(int i=0;i<G.vexnum;i++){
            for(int j=0;j<G.vexnum;j++){
                if(D[i][k] + D[k][j] < D[i][j]){ // 若从Vi【经Vk】到Vj的一条路径更短 
                    D[i][j] = D[i][k] + D[k][j]; // 更新D[i][j] 
                    Path[i][j] = Path[k][j]; // 【易错】 更改Vj的前驱为 Vk 
                }
            }
        }
    }
} 

// 初始化(邻接矩阵)带权有向图的图模型 
void InitAMGraph(AMGraph &G){
    cout<<"Please Input Vertexs Number:";
    cin>>G.vexnum;
    cout<<"\nPlease Directed Edge Number:";
    cin>>G.arcnum;
    
    for(int i=0;i<MVNum;i++){
        for(int j=0;j<MVNum;j++){
            if(i!=j){ // 【易错】 初始化<Vi, Vj>时: <Vi,Vj> 路径长度无穷大 (i!=j) 
                G.arcs[i][j] = MaxInt;
            } else { //  【易错】 初始化<Vi, Vj>时: <Vi,Vi>【自回环】路径长度为0 (i==i) 
                G.arcs[i][j] = 0;
            }
        }
    }
    for(int i=0;i<G.vexnum;i++){
        G.vexs[i] = i;
    }
    cout<<"\nPlease Input All Directed Edges and their Weight now.";
    int i,j;
    int weight;
    for(int k=0;k<G.arcnum;k++){
        cout<<"\n("<<(k+1)<<") Directed Edges(i,j,weight): ";
        cin>>i;
        cin>>j;
        cin>>weight;
        G.arcs[i][j] = weight;  
    }
    cout<<endl;
}

void OutputD(AMGraph G){
    for(int i=0;i<G.vexnum;i++){
        for(int j=0;j<G.vexnum;j++){
            cout<<"Shortest Distance Weight of the Pair of Directed Vertices ("<<i<<","<<j<<"): "<<D[i][j]<<endl; 
        }
    }
}

void OutputPath(AMGraph G){
    for(int i=0;i<G.vexnum;i++){
        for(int j=0;j<G.vexnum;j++){
            cout<<"Path("<<i<<","<<j<<"): "<<Path[i][j]<<endl; 
        }
    }
//  int fullPath[G.vexnum]; //逆序记录 <Vi,Vj>的最短路径的序号 ; 最大路径长度不会超过 G.vexnum 
//  for(int i=0;i<G.vexnum;i++){
//      for(int j=0;j<G.vexnum;j++){
//          cout<<"Shortest Distance Path of the Pair of Directed Vertices ("<<i<<","<<j<<"): ";
//          for(int p=0;i<G.vexnum;p++){ // 初始化记录最短路径的临时表 
//              fullPath[p]= -1; // -1 表示结束符 
//          }
//          int m=i,n=j;
//          int cusor=G.vexnum-1;
//          while( (cusor>=0) && (Path[m][n]!=i || Path[m][n]!=MaxInt) ){
//              fullPath[cusor] = Path[m][n]; // Vj的前驱
//              n = fullPath[cusor]; // 【重难点】 源点m不变， 终点n更新为j的前驱 
//              cusor--; // 要保证 cusor>=0 
//          }
//          //输出全路径
//          cout<<" "<<i<<">";
//          cusor++; // 当前cusor的位置是源点i的前一个空置空间，值为-1 
//          while(fullPath[cusor] != -1){
//              cout<<fullPath[cusor]<<">"
//          }
//      }
//  }   
}

int main(){
    AMGraph G;
    InitAMGraph(G);//易错处 
    ShortestPath_Floyd(G); // 【重/难点】易错处 
    OutputD(G);
    OutputPath(G);
    return 0;
}
*/

1.2 Output

Please Input Vertexs Number:4

Please Directed Edge Number:8

Please Input All Directed Edges and their Weight now.
(1) Directed Edges(i,j,weight): 0 1 1

(2) Directed Edges(i,j,weight): 1 3 2

(3) Directed Edges(i,j,weight): 2 0 3

(4) Directed Edges(i,j,weight): 0 3 4

(5) Directed Edges(i,j,weight): 2 1 5

(6) Directed Edges(i,j,weight): 3 2 6

(7) Directed Edges(i,j,weight): 2 3 8

(8) Directed Edges(i,j,weight): 1 2 9

Shortest Distance Weight of the Pair of Directed Vertices (0,0): 0
Shortest Distance Weight of the Pair of Directed Vertices (0,1): 1
Shortest Distance Weight of the Pair of Directed Vertices (0,2): 9
Shortest Distance Weight of the Pair of Directed Vertices (0,3): 3
Shortest Distance Weight of the Pair of Directed Vertices (1,0): 11
Shortest Distance Weight of the Pair of Directed Vertices (1,1): 0
Shortest Distance Weight of the Pair of Directed Vertices (1,2): 8
Shortest Distance Weight of the Pair of Directed Vertices (1,3): 2
Shortest Distance Weight of the Pair of Directed Vertices (2,0): 3
Shortest Distance Weight of the Pair of Directed Vertices (2,1): 4
Shortest Distance Weight of the Pair of Directed Vertices (2,2): 0
Shortest Distance Weight of the Pair of Directed Vertices (2,3): 6
Shortest Distance Weight of the Pair of Directed Vertices (3,0): 9
Shortest Distance Weight of the Pair of Directed Vertices (3,1): 10
Shortest Distance Weight of the Pair of Directed Vertices (3,2): 6
Shortest Distance Weight of the Pair of Directed Vertices (3,3): 0
Path(0,0): -1
Path(0,1): 0
Path(0,2): 3
Path(0,3): 1
Path(1,0): 2
Path(1,1): -1
Path(1,2): 3
Path(1,3): 1
Path(2,0): 2
Path(2,1): 0
Path(2,2): -1
Path(2,3): 1
Path(3,0): 2
Path(3,1): 0
Path(3,2): 3
Path(3,3): -1

2 参考文献

• 《数据结构(C语言版/ 严蔚敏 李冬梅 吴伟民 编)》