C++实现多源最短路径之Floyd算法示例

C++实现多源最短路径之Floyd算法示例

多源最短路径问题是指在给定图中任意两个顶点之间的最短路径问题。Floyd算法是解决该问题的一种经典算法，效率较低，但实现简单。

本篇文章将详细讲解如何使用C++语言实现Floyd算法，主要包含以下内容：

1. 代码实现
2. 算法详解
3. 示例说明

代码实现

#include<iostream>
using namespace std;

const int MAXN=5;
const int INF=0x3f3f3f3f;  //表示正无穷

int graph[MAXN][MAXN];

void Floyd(int graph[][MAXN],int n){
    for(int k=0;k<n;k++){
        for(int i=0;i<n;i++){
            for(int j=0;j<n;j++){
                 if(graph[i][k]!=INF && graph[k][j]!=INF && graph[i][j]>graph[i][k]+graph[k][j]){
                     graph[i][j]=graph[i][k]+graph[k][j];
                 }
            }
        }
    }
}

int main(){
    for(int i=0;i<MAXN;i++){
        for(int j=0;j<MAXN;j++){
            graph[i][j]=INF;
        }
    }
    graph[0][1]=graph[1][0]=2;
    graph[0][2]=graph[2][0]=6;
    graph[0][3]=graph[3][0]=4;
    graph[1][3]=graph[3][1]=3;
    graph[2][3]=graph[3][2]=1;
    graph[1][4]=graph[4][1]=5;
    graph[2][4]=graph[4][2]=2;
    graph[3][4]=graph[4][3]=5;
    Floyd(graph,MAXN);
    for(int i=0;i<MAXN;i++){
        for(int j=0;j<MAXN;j++){
            cout<<graph[i][j]<<' ';
        }
        cout<<endl;
    }

    return 0;
}

算法详解

Floyd算法的具体实现过程如下：

1. 初始化：将每对节点之间的距离赋值到图中。
2. 三层循环：算法核心部分，枚举每个节点作为中转节点，计算每对节点之间经过该中转节点的距离，更新图中的距离值。
3. 输出结果

这里的思路是从每个点开始，枚举它和其它点之间是否有中转点可以缩短距离。依次枚举每个点，最终形成所有点之间最短路径的矩阵。

示例说明

以本文中给出的代码为例，初始化的图如下：

-	0	1	2	3	4
0	0	2	6	4	INF
1	2	0	INF	3	5
2	6	INF	0	1	2
3	4	3	1	0	5
4	INF	5	2	5	0

运行Floyd算法后，得到的结果为：

-	0	1	2	3	4
0	0	2	4	4	6
1	2	0	6	3	5
2	4	6	0	1	2
3	4	3	1	0	5
4	6	5	2	5	0

对于任意两个节点之间的最短路径，可以通过矩阵中对应的位置获得，比如节点0到节点3的最短路径为4。

总结：本文介绍了如何使用C++实现多源最短路径中的经典算法Floyd，运用了二维数组和三层循环的思想，详细讲解了实现流程，并通过实例进行了说明。