弗洛伊德(Floyd)算法

弗洛伊德(Floyd)算法求图中两点的最短路径

佛罗依德(Floyd )算法的基本思想: 设图g用邻接矩阵法表示,求图g中任意一对顶点vi与vj间的的最短路径。 (-1)将vi到vj的最短的路径长度初始化为g.arcs[i][j].adj,进行如下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的最短路径。

typedef Seqlist VertexSet;
ShortestPath_Floyd(AdjMartrix g, 
                   WeightType dist[MAX_VERTEX_NUM][MAX_VERTEX_NUM]),
                   VertexSet path[MAX_VERTEX_NUM][MAX_VERTEX_NUM]) {
/*g为带权有向图的邻接矩阵表示发,path[i]vi到vj的当前最短路径,
dist[i][j]为vi到vj的最短路径长度*/
    for(i = 0; i < g.vexnum; i++) {     //初始化dist[i][j]和path[i][j]
        for(j = 0; j < g.vexnum; j++) {
            InitList(&p[i][j]);
            dist[i][j] = g.arcs[i][j].adj;
            if(dist[i][j] < INFINITY) {
                AddTail(&path[i][j], g.vertex[i]);
                AddTail(&path[i][j], g.vertex[j]);
            }
        }
    }
    for(k = 0; k < g.vexnum; k++) {
        for(i = 0; i < g.vexnum; i++) {
            for(j = 0; j <g.vexnum; j++) {
                if(dist[i][k] + dist[k][j] < dist[i][j]) {
                    dist = dist[i][k] + dist[k][j];
                    path = JoinList(path[k][i], path[i][j]);
                }//End if JoinList合并顺序表操作
            } //End for(j) 
        } //End for(i) 
    } //End for(k) 
}

知乎:Solo | 微博@从流域到海域

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏xingoo, 一个梦想做发明家的程序员

剑指OFFER之跳台阶(九度OJ1388)

题目描述: 一只青蛙一次可以跳上1级台阶,也可以跳上2级。求该青蛙跳上一个n级的台阶总共有多少种跳法。 输入: 输入可能包含多个测试样例,对于每个测试案例, 输...

20290
来自专栏数据结构与算法

1405 奶牛的旅行

题目描述 Description 农民John的农场里有很多牧区。有的路径连接一些特定的牧区。一片所有连通的牧区称为一个牧场。但是就目前而言,你能看到至少有两个...

29980
来自专栏软件开发 -- 分享 互助 成长

图的遍历算法

前言:学习图的遍历算法之前,需要先了解一下图的存储方式(这里只以无向图作为讨论了)。 (1)邻接矩阵 ? (2)邻接表 ? 一、DFS(深度优先遍历)  设置一...

21670
来自专栏聊聊技术

原 初学图论-Bellman-Ford单源

475130
来自专栏图像识别与深度学习

2018-06-30 详解 MNIST 数据集

16420
来自专栏Java帮帮-微信公众号-技术文章全总结

【Java案例】余弦函数

案例描述 在屏幕上画出余弦函数cos(x)曲线,如图1.6所示。 ? 图1.6 余弦函数cos(x)曲线 案例分析 连续的曲线是由点组成的,点与点之间距离比较...

58760
来自专栏小文博客

蓝桥杯 C语言省赛 习题2 格子中输出

18140
来自专栏聊聊技术

原 初学图论-Kahn拓扑排序算法(Kah

36980
来自专栏从流域到海域

迪杰斯特拉(Dijkstra)算法求图中最短路径

迪杰斯特拉(Dijkstra )算法: 对于图G=(V,E),将图的顶点分为两组: 顶点集S:已求出的最短路径的顶点集合(初始为{v0}); 顶...

26470
来自专栏数值分析与有限元编程

可视化 | 一个三角形常应变单元后处理例子

昨天提到了应力云图,其实质是用不同的颜色填充等值线。有了结点的应力值,单元内任意一点的应力值是通过插值实现的。下面来看一个悬臂梁的综合后处理。 如图所示,一个悬...

29570

扫码关注云+社区

领取腾讯云代金券