弗洛伊德算法(求最短路径)

这篇具有很好参考价值的文章主要介绍了弗洛伊德算法(求最短路径)。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

弗洛伊德算法(求最短路径)

在一个加权图中,如果想找到各个顶点之间的最短路径,可以考虑使用弗洛伊德算法。

弗洛伊德算法既适用于无向加权图,也适用于有向加权图。使用弗洛伊德算法查找最短路径时,只允许环路的权值为负数,其它路径的权值必须为非负数,否则算法执行过程会出错。

弗洛伊德算法的实现思路

弗洛伊德算法是基于动态规划算法实现的,接下来我们以在图 1 所示的有向加权图中查找各个顶点之间的最短路径为例,讲解弗洛伊德算法的实现思路。

弗洛伊德算法(求最短路径)

图 1 有向加权图

图 1 中不存在环路,且所有路径(边)的权值都为正数,因此可以使用弗洛伊德算法。

弗洛伊德算法查找图 1 中各个顶点之间的最短路径,实现过程如下:

  1. 建立一张表格,记录每个顶点直达其它所有顶点的权值:

表 1 各个顶点直达路径的权值

目标顶点

1 2 3 4
起始顶点 1 0 3 ∞ 5
2 2 0 ∞ 4
3 ∞ 1 0 ∞
4 ∞ ∞ 2 0

起始顶点指的是从哪个顶点出发,目标顶点指的是要达到的顶点,例如 2->1 路径的权值是 2,顶点 2 是起始顶点,顶点 1 是目标顶点。此外,∞ 表示无穷大的数,即顶点之间不存在直达的路径。

  1. 在表 1 的基础上,将顶点 1 作为 “中间顶点”,计算从各个顶点出发途径顶点 1 再到达其它顶点的权值,如果比表 1 中记录的权值更小,证明两个顶点之间存在更短的路径,对表 1 进行更新。

从各个顶点出发,途径顶点 1 再到达其它顶点的路径以及对应的权值分别是:

2-1-3:权值为 2 + ∞ = ∞,表 1 中记录的 2-3 的权值也是 ∞;
2-1-4:权值为 2 + 5 = 7,表 1 中记录的 2-4 的权值是 4;
3-1-2:权值为 ∞ + 3,表 1 中记录的 3-2 的权值是 1;
3-1-4:权值为 ∞ + 5,表 1 中记录的 3-4 的权值是 ∞;
4-1-2:权值为 ∞ + 3,表 1 中记录的 4-2 的权值是 ∞;
4-1-3:权值为 ∞ + ∞,表 1 中记录的 4-3 的权值是 2。

以上所有的路径中,没有比表 1 中记录的权值最小的路径,所以不需要对表 1 进行更新。

  1. 在表 1 的基础上,以顶点 2 作为 “中间顶点”,计算从各个顶点出发途径顶点 2 再到达其它顶点的权值:

1-2-3:权值为 3 + ∞,表 1 中记录的 1-3 的权值为 ∞;
1-2-4:权值为 3 + 4 = 7,表 1 中 1-4 的权值为 5;
3-2-1:权值为 1 + 2 = 3,表 1 中 3-1 的权值为 ∞,3 < ∞;
3-2-4:权值为 1 + 4 = 5,表 1 中 3-4 的权值为 ∞,5 < ∞;
4-2-1:权值为 ∞ + 2,表 1 中 4-1 的权值为 ∞;
4-2-3:权值为 ∞ + ∞,表 1 中 4-3 的权值为 2。

以顶点 2 作为 “中间顶点”,我们找到了比 3-1、3-4 更短的路径,对表 1 进行更新:

表 2 更新后的 “表 1”

目标顶点

1 2 3 4
起始顶点 1 0 3 ∞ 5
2 2 0 ∞ 4
3 3(3-2-1) 1 0 5(3-2-4)
4 ∞ ∞ 2 0

  1. 在表 2 的基础上,将顶点 3 作为 “中间顶点”,计算从各个顶点出发途径顶点 3 再到达其它顶点的权值:

1-3-2 权值为 ∞ + 1,表 2 中 1-2 的权值为 3;
1-3-4 权值为 ∞ + 5,表 2 中 1-4 的权值为 5;
2-3-1 权值为 ∞ + 3,表 2 中 2-1 的权值为 2;
2-3-4 权值为 ∞ + 5,表 2 中 2-4 的权值为 4;
4-3-1 权值为 2 + 3 = 5,表 2 中 4-1 的权值为 ∞,5 < ∞;
4-3-2 权值为 2 + 1 = 3,表 2 中 4-2 的权值为 ∞,3 < ∞;

以顶点 3 作为 “中间顶点”,我们找到了比 4-1、4-2 更短的路径,对表 2 进行更新:

表 3 更新后的 “表 2”

目标顶点

1 2 3 4
起始顶点 1 0 3 ∞ 5
2 2 0 ∞ 4
3 3(3-2-1) 1 0 5(3-2-4)
4 5(4-3-2-1) 3(4-3-2) 2 0

  1. 在表 3 的基础上,将顶点 4 作为 “中间顶点”,计算从各个顶点出发途径顶点 4 再到达其它顶点的权值:

1-4-2 权值为 5 + 3 = 8,表 3 中 1-2 的权值为 3;
1-4-3 权值为 5 + 2 = 7,表 3 中 1-3 的权值为 ∞,7 < ∞;
2-4-1 权值为 4 + 5 = 9,表 3 中 2-1 的权值为 2;
2-4-3 权值为 4 + 2 = 6,表 3 中 2-3 的权值为 ∞,6 < ∞;
3-4-1 权值为 4 + 5 = 9,表 3 中 3-1 的权值为 3;
3-4-2 权值为 5 + 5 = 10 ,表 3 中 3-2 的权值为 1。

以顶点 4 作为 “中间顶点”,我们找到了比 1-3、2-3 更短的路径,对表 3 进行更新:

表 4 更新后的 “表 3”

目标顶点

1 2 3 4
起始顶点 1 0 3 7(1-4-3) 5
2 2 0 6(2-4-3) 4
3 3(3-2-1) 1 0 5(3-2-4)
4 5(4-3-2-1) 3(4-3-2) 2 0
通过将所有的顶点分别作为“中间顶点”,最终得到的表 4 就记录了各个顶点之间的最短路径。例如,4-1 的最短路径为 4-3-2-1。

弗洛伊德算法的具体实现

了解了弗洛伊德算法查找最短路径的实现思路后,接下来仍以图 1 为例,分别编写 C、Java、Python 程序实现弗洛伊德算法。

如下是用弗洛伊德算法查找图 1 中各顶点之间最短路径的 C 语言程序:

#include <stdio.h>
#define V 4    //设定图中的顶点数
#define INF 65535   // 设置一个最大值
int P[V][V] = { 0 }; //记录各个顶点之间的最短路径
void printMatrix(int matrix[][V]);  //输出各个顶点之间的最短路径
void printPath(int i, int j); // 递归输出各个顶点之间最短路径的具体线路
void floydWarshall(int graph[][V]); // 实现弗洛伊德算法
int main() {
    // 有向加权图中各个顶点之间的路径信息
    int graph[V][V] = { {0, 3, INF, 5},
                          {2, 0, INF, 4},
                          {INF, 1, 0, INF},
                          {INF, INF, 2, 0} };
    floydWarshall(graph);
}
// 中序递归输出各个顶点之间最短路径的具体线路
void printPath(int i, int j)
{
    int k = P[i][j];
    if (k == 0)
        return;
    printPath(i, k);
    printf("%d-", k + 1);
    printPath(k, j);
}
// 输出各个顶点之间的最短路径
void printMatrix(int graph[][V]) {
    int i, j;
    for (i = 0; i < V; i++) {
        for (j = 0; j < V; j++) {
            if (j == i) {
                continue;
            }
            printf("%d - %d: 最短路径为:", i + 1, j + 1);
            if (graph[i][j] == INF)
                printf("%s\n", "INF");
            else {
                printf("%d", graph[i][j]);
                printf(",依次经过:%d-", i + 1);
                //调用递归函数
                printPath(i, j);
                printf("%d\n", j + 1);
            }
        }
    }
}
// 实现弗洛伊德算法,graph[][V] 为有向加权图
void floydWarshall(int graph[][V]) {
    int  i, j, k;
    //遍历每个顶点,将其作为其它顶点之间的中间顶点,更新 graph 数组
    for (k = 0; k < V; k++) {
        for (i = 0; i < V; i++) {
            for (j = 0; j < V; j++) {
                //如果新的路径比之前记录的更短,则更新 graph 数组
                if (graph[i][k] + graph[k][j] < graph[i][j]) {
                    graph[i][j] = graph[i][k] + graph[k][j];
                    //记录此路径
                    P[i][j] = k;
                }
            }
        }
    }
    // 输出各个顶点之间的最短路径
    printMatrix(graph);
}

如下是用弗洛伊德算法查找图 1 中各顶点之间最短路径的 Java 程序:

public class Floyd {
    static int V = 4; // 顶点的个数
    static int[][] P = new int[V][V]; // 记录各个顶点之间的最短路径
    static int INF = 65535; // 设置一个最大值
    // 中序递归输出各个顶点之间最短路径的具体线路
    public static void printPath(int i, int j) {
        int k = P[i][j];
        if (k == 0)
            return;
        printPath(i, k);
        System.out.print((k + 1) + "-");
        printPath(k, j);
    }
    // 输出各个顶点之间的最短路径
    public static void printMatrix(int[][] graph) {
        for (int i = 0; i < V; i++) {
            for (int j = 0; j < V; j++) {
                if (j == i) {
                    continue;
                }
                System.out.print((i + 1) + " - " + (j + 1) + ":最短路径为:");
                if (graph[i][j] == INF)
                    System.out.println("INF");
                else {
                    System.out.print(graph[i][j]);
                    System.out.print(",依次经过:" + (i + 1) + "-");
                    // 调用递归函数
                    printPath(i, j);
                    System.out.println((j + 1));
                }
            }
        }
    }
    // 实现弗洛伊德算法,graph[][V] 为有向加权图
    public static void floydWarshall(int[][] graph) {
        int i, j, k;
        // 遍历每个顶点,将其作为其它顶点之间的中间顶点,更新 graph 数组
        for (k = 0; k < V; k++) {
            for (i = 0; i < V; i++) {
                for (j = 0; j < V; j++) {
                    // 如果新的路径比之前记录的更短,则更新 graph 数组
                    if (graph[i][k] + graph[k][j] < graph[i][j]) {
                        graph[i][j] = graph[i][k] + graph[k][j];
                        // 记录此路径
                        P[i][j] = k;
                    }
                }
            }
        }
        // 输出各个顶点之间的最短路径
        printMatrix(graph);
    }
    public static void main(String[] args) {
        // 有向加权图中各个顶点之间的路径信息
        int[][] graph = new int[][] { { 0, 3, INF, 5 }, { 2, 0, INF, 4 }, { INF, 1, 0, INF }, { INF, INF, 2, 0 } };
        floydWarshall(graph);
    }
}

如下是用弗洛伊德算法查找图 1 中各顶点之间最短路径的 Python 程序:

V = 4   # 顶点的个数
INF = 65535    # 设定一个最大值
P = [[0]*V for i in range(V)] # 记录各个顶点之间的最短路径
# 有向加权图中各个顶点之间的路径信息
graph = [[0, 3, INF, 5],
         [2, 0, INF, 4],
         [INF, 1, 0, INF],
         [INF, INF, 2, 0]]
# 中序递归输出各个顶点之间最短路径的具体线路
def printPath(i,j):
    k = P[i][j]
    if k == 0:
        return;
    printPath(i , k)
    print("%d-" % (k + 1) , end='')
    printPath(k , j)
# 输出各个顶点之间的最短路径
def printMatrix(graph):
    for i in range(V):
        for j in range(V):
            if j == i:
                continue
            print("%d - %d: 最短路径为:"%(i + 1, j + 1) , end='')
            if graph[i][j] == INF:
                print("INF")
            else:
                print(graph[i][j] , end='')
                print(",依次经过:%d-"%(i+1) , end='')
                # 调用递归函数
                printPath(i , j)
                print(j + 1)
# 实现弗洛伊德算法,graph[][V] 为有向加权图
def floydWarshall(graph):
    # 遍历每个顶点,将其作为其它顶点之间的中间顶点,更新 graph 数组
    for k in range(V):
        for i in range(V):
            for j in range(V):
                # 如果新的路径比之前记录的更短,则更新 graph 数组
                if graph[i][k] + graph[k][j] < graph[i][j]:
                    graph[i][j] = graph[i][k] + graph[k][j]
                    # 记录此路径
                    P[i][j] = k
    # 输出各个顶点之间的最短路径
    printMatrix(graph)
floydWarshall(graph)

以上程序的输出结果均为:
1 - 2: 最短路径为:3,依次经过:1-2
1 - 3: 最短路径为:7,依次经过:1-4-3
1 - 4: 最短路径为:5,依次经过:1-4
2 - 1: 最短路径为:2,依次经过:2-1
2 - 3: 最短路径为:6,依次经过:2-4-3
2 - 4: 最短路径为:4,依次经过:2-4
3 - 1: 最短路径为:3,依次经过:3-2-1
3 - 2: 最短路径为:1,依次经过:3-2
3 - 4: 最短路径为:5,依次经过:3-2-4
4 - 1: 最短路径为:5,依次经过:4-3-2-1
4 - 2: 最短路径为:3,依次经过:4-3-2
4 - 3: 最短路径为:2,依次经过:4-3文章来源地址https://www.toymoban.com/news/detail-456034.html

到了这里,关于弗洛伊德算法(求最短路径)的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 【数据结构】最短路径算法实现(Dijkstra(迪克斯特拉),FloydWarshall(弗洛伊德) )

    最短路径问题 :从在带权有向图G中的某一顶点出发,找出一条通往另一顶点的最短路径,最短也就是沿路径各边的权值总和达到最小。 单源最短路径问题:给定一个图G = ( V , E ) G=(V,E)G=(V,E),求源结点s ∈ V s∈Vs∈V到图 中每个结点v ∈ V v∈Vv∈V的最短路径 针对一个带权

    2024年02月04日
    浏览(50)
  • 弗洛伊德循环查找算法-原理

    本文灵感来自哔哩哔哩视频  视频链接: 弗洛伊德循环查找算法 算法代码(java) 弗洛伊德循环查找算法中第二次相遇的地方就是循环的起始点,这个性质的证明是基于数学的原理。这是因为在第一次相遇时,慢指针 `slow` 和快指针 `fast` 已经处于同一个循环内。设链表起点到环

    2024年01月19日
    浏览(46)
  • 40.弗洛伊德(Floyd)算法

    我们此前拆解过迪杰斯特拉(Dijkstra)算法,与它一样,弗洛伊德(Floyd)算法也是用于寻找给定的加权图中顶点间最短路径的算法。该算法是1978年图灵奖获得者、斯坦福大学计算机科学系教授 罗伯特·弗洛伊德 及其团队发现的,以主要创始人 弗洛伊德 命名。 迪杰斯特拉算

    2024年02月06日
    浏览(36)
  • Floyd - Warshall (弗洛伊德算法)

    图中任意两点之间的最短路径问题 Dijkstra和Bellman-Ford也可以以所有点为源点,求出任意两点之间的最短距离,但是Dijstra不能解决带负权的的边,Bellman-Ford 效率慢点 Floyd算法考虑的是一条最短路径的中间节点,即简单路径p={v1 , v2,  ...  ,vn}上除v1和vn的任意节点 设K是p的一个

    2024年02月06日
    浏览(40)
  • 今天学习了弗洛伊德算法(floyed)

    我自己写的模板 嘿嘿 Dijkstra算法SPFA算法但是我知道还有这些,但是今天是周末哎,我有点不想学了,我今天学的是比较差劲的一个算法(但是它好像比较好记啊),改天再学其他比较好一点的算法加强自己 输入 输出 后言:提醒自己加权值是分题目来不同权值,不是像示例

    2024年02月11日
    浏览(37)
  • 【数据结构】图—弗洛伊德(Floyd)算法

    上文介绍了迪杰斯特拉(Dijkstra)算法,计算网图的某个源点到其余各个顶点的最短路径问题(边权值为非负值),本文介绍另一个求最短路径的算法——弗洛伊德算法,它是计算所有顶点到所有顶点的最短路径,其时间复杂度为 O ( n 3 ) O(n^3) O ( n 3 ) ,其算法相比Dijkstra算法更加

    2024年02月12日
    浏览(51)
  • 力扣-202. 快乐数解析-弗洛伊德循环查找算法

    题目链接   使用代码测试一下每一代数字  可以发现 归纳一下这些简单数字就可以发现,对于任意一个非快乐数,最终会进入重复循环, ···不难发现,4即之后的结果就是新一轮循环。 那么我的第一个做法是检测4出现的次数 如果4出现次数超过两次, 那么就不是快乐数 感

    2024年01月20日
    浏览(39)
  • 算法——弗洛伊德算法(Floyd-Warshall)(图论)(c++)

    (蒟蒻的第四篇文章,希望dalao勿喷) (希望没问题) 声明: 1.本人变量定义的名称很low 2.本人用的方法也很low 3.但我觉得文章应该不low  (盲目自信) 第四篇文章讲讲Floyd算法 Floyd算法是一种寻找最短路径的常见算法,其特点是: 短,好理解(虽然其他算法也挺好理解的

    2023年04月09日
    浏览(34)
  • 大话数据结构-迪杰斯特拉算法(Dijkstra)和弗洛伊德算法(Floyd)

      最短路径,对于图来说,是两顶点之间经过的边数最少的路径;对于网来说,是指两顶点之间经过的边上权值之和最小的路径。路径上第一个顶点为源点,最后一个顶点是终点。   以如下无向图为例:   我们来计算下标为0的顶点,到其他顶点的最短路径,首先定义

    2024年02月06日
    浏览(42)
  • 12.25~12.27并查集(查找与合并),全排列,约瑟夫问题(队列,数组)upper/lower_bound,重构二叉树,最优矩阵,线段树(构建),淘汰赛(构建树,队列),医院问题(最短路,弗洛伊德

    题目背景 若某个家族人员过于庞大,要判断两个是否是亲戚,确实还很不容易,现在给出某个亲戚关系图,求任意给出的两个人是否具有亲戚关系。 题目描述 规定:�x 和 �y 是亲戚,�y 和 �z 是亲戚,那么 �x 和 �z 也是亲戚。如果 �x,�y 是亲戚,那么 �

    2024年01月23日
    浏览(50)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包