数据结构:弗洛伊德算法(最短路径)图文详解

弗洛伊德算法选取某个节点k作为i到j需要经过的中间节点,通过比较d(i,k)+d(k,j)和现有d(i,j)的大小,将较小值更新为路径长度,对k节点的选取进行遍历,以得到在经过所有节点时i到j的最短路径长度,通过不断加入中间点的方式更新最短路径。

具体过程看下文:

给出一个有向图,并带有权值

数据结构:弗洛伊德算法(最短路径)图文详解_第1张图片

1,先写出图的邻接矩阵

邻接矩阵中的元素就是有向图中两点的权值,不可直接到达的两个点的权值为无穷(∞)

数据结构:弗洛伊德算法(最短路径)图文详解_第2张图片

 2,选源点,求该源点到其他各点的最短路

从源点所在的那一行选出第一个权值最小的点,这里我们选v0为源点,权值最小是10,顶点为v2,

v0->vv2 最短路就是v0->v2 路径长度为10   

为什么权值最小就是到达该店的最短距离? 说明:如果有到2这个点有更短的路径,第一个选择的顶点v2。

 数据结构:弗洛伊德算法(最短路径)图文详解_第3张图片

 3,更新两点距离

选出v2这个顶点后,将其清除。已经选出了v0->v2这条路径,0到其他点的最短路径就可能相对之前会有所变化,这时候就要更新路径距离,用状态转移方程a[0][i]=min(a[0][i],a[0][2]+a[2][i])来更新权值。

数据结构:弗洛伊德算法(最短路径)图文详解_第4张图片

 数据结构:弗洛伊德算法(最短路径)图文详解_第5张图片

更新后,选出顶点v3的最小权值25,并且将a[0][3]清除,并且重复上次更新操作。因为操作相同,在这里不一一画出了(偷懒了giao)

4,最短路径

数据结构:弗洛伊德算法(最短路径)图文详解_第6张图片

 5,求各个点之间的最短路径

上面举出求源点顶点v0的最短路径,要想求各个点的最短路径,只需要将源点更换,重复上述一样过程即可求出各点间的最短路径。

6弗洛伊德算法代码实现

#include 
#include
using namespace std;
#define INF 0x3f3f3f3f
int main()
{
    int a[21][21],m,n,i, j, w;
    for (int i = 1; i <= 20; i++) {
        for (int j = 1; j <= 20; j++) {
            if (i == j) {a[i][j] = 0;}
            else a[i][j] = INF;
        }
    }
    cin>>n>>m;
    for (int k = 1;k<= m;k++) {
        cin>>i>>j>>w;
        a[i][j] = w;
        a[j][i] = w;
    }
    for (int p = 1; p <= n; p++) {
        for (int i = 1; i <= n; i++) {
            if (a[i][p] == INF) continue;
            for (int j = 1; j <= n; j++) {
                if (i==j)continue;
                a[i][j] = min(a[i][j], a[i][p] + a[p][j]);
            }
        }
    }
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            cout << a[i][j] << " ";
        }
        cout << endl;
    }
    return 0;
}

你可能感兴趣的