网路最短路——Floyd算法Python实现

Floyd算法（Floyd-Warshall算法）是一种用于求解图中所有顶点对之间最短路径的算法,该算法名称以创始人之一、1978年图灵奖获得者、斯坦福大学计算机科学系教授罗伯特·弗洛伊德命名。Floyd算法可以应用于许多方面，特别是在交通、物流和通信网络的优化中，譬如城市交通规划：Floyd算法可以帮助规划城市交通网络，确定最短路径和最优路线，以减少交通拥堵和行程时间。物流管理：在物流领域，Floyd算法可以用于确定不同地点之间的最短路径，帮助优化货物运输和配送的路线，降低成本并提高效率。电信网络规划：Floyd算法可应用于电信网络中的路由优化，帮助确定数据包传输的最短路径，提高网络连接的速度和质量。航班路径规划：航空公司可以使用Floyd算法确定不同机场之间的最短路径，优化航班计划和航线，提高飞行效率和旅客体验。金融交易网络：在金融领域，Floyd算法可以用于分析银行间的交易网络，确定最短路径和关键参与者，以便监测风险和进行迅速的资金清算，等等。

一、最短路问题

若网络中的每条边都有一个数值（长度、成本、时间等），则找出两节点（通常是源节点和阱节点）之间总权和最小的路径就是最短路问题。最通用的最短路问题（认为是标准型）可以如此描述：希望在网络中找到一条从源节点（source node）到接收节点（target node）的最小成本路径，这里的最小成本可定义为路径长度、旅行时间、旅行费用等。
设\(G\)是由节点集合\(V\)（元素个数为n）和弧集合\(A\)（元素个数为m）组成的网络,定义节点\(s ∈ V\)为源节点（source），其他节点为非源节点（non-source），路径长度为该路径所包含弧的长度之和。求解单源最短路径问题就是找出源节点\(s\)到每一个非源节点\(t\)的有向最短路径。最短路径问题的数学模型如下：

二十世纪六十年代，在最短路问题的研究上已经颇有成效，该问题在计算机科学、运筹学等学科的研究中一直是一个热点问题。最短路问题在现实应用中也相应的代表了最低成本、最短时间问题等。该问题作为网络流学科中的经典问题，以其丰富的适用性，具有广泛的应用领域。单就交通运输而言，最短路问题就已经有如下重要应用:

二、最短路的Floyd算法

Floyd算法的基本思想如下：从任意节点A到任意节点B的最短路径不外乎2种可能，1是直接从A到B，2是从A经过若干个节点X到B。所以，我们假设Dis(AB)为节点A到节点B的最短路径的距离，对于每一个节点X，我们检查Dis(AX) + Dis(XB) < Dis(AB)是否成立，如果成立，证明从A到X再到B的路径比A直接到B的路径短，我们便设置Dis(AB) = Dis(AX) + Dis(XB)，这样一来，当我们遍历完所有节点X，Dis(AB)中记录的便是A到B的最短路径的距离。
Floyd计算图G=(V,E)中各个顶点的最短路径时，需要引⼊两个矩阵，矩阵S中的元素a[i][j]表⽰顶点i(第i个顶点)到顶点j(第j个顶点)的距离。矩阵P中的元素b[i][j]，表⽰顶点i到顶点j经过了b[i][j]记录的值所表⽰的顶点。
假设图G中顶点个数为n，则需要对矩阵D和矩阵P进⾏n次更新。初始时，矩阵D中顶点a[i][j]的距离为顶点i到顶点j的权值；如果i和j不相邻，则a[i][j]=∞，矩阵P的值为顶点b[i][j]的j的值。 接下来开始，对矩阵D进⾏n次更新。第1次更新时，如果”a[i][j]的距离” > “a[i]
[0]+a[0][j]”(a[i][0]+a[0][j]表⽰”i与j之间经过第1个顶点的距离”)，则更新a[i][j]为”a[i][0]+a[0][j]”,更新b[i][j]=b[i][0]。 同理，第k次更新时，如果”a[i][j]的距离” > “a[i][k-1]+a[k-1][j]”，则更新a[i][j]为”a[i][k-1]+a[k-1][j]”,b[i][j]=b[i][k-1]。更新N次之后，操作完成！

三、Python求解

实例：设

f = float('inf')  # float('inf')表示无穷大

# 准备数据
data = [
    [0, 7, f, 5, f, f, f],
    [7, 0, 8, 9, 7, f, f],
    [f, 8, 0, f, 5, f, f],
    [5, 9, f, 0, 15, 6, f],
    [f, 7, 5, 15, 0, 8, 9],
    [f, f, f, 6, 8, 0, 11],
    [f, f, f, f, 9, 11, 0],
]
path = [[i] * 7 for i in range(7)]

for k in range(7):
    for i in range(7):
        for j in range(7):
            if data[i][j] > data[i][k] + data[k][j]:  # 比较距离的大小
                data[i][j] = data[i][k] + data[k][j]  # 每次都存最小的值
                path[i][j] = k  # 记录中间点


# 定义函数找出x到y的具体路径
def show_trace(x,y):
    trace = []
    def add_trace(x, y):
        global mm
        if x != y:
            add_trace(x, path[x][y])
        return trace.append(y)
    add_trace(x,y)
    trace_str = str(trace)
    trace_str = trace_str.replace(',','-->')
    print(f"从 {x} 到 {y} 的最短路径为: {trace_str}")

for i in data:
    print(i)

show_trace(0,4)  # 求A到E的最短路径
show_trace(0,6)	 # 求A到G的最短路径

[0, 7, 15, 5, 14, 11, 22]
[7, 0, 8, 9, 7, 15, 16]
[15, 8, 0, 17, 5, 13, 14]
[5, 9, 17, 0, 14, 6, 17]
[14, 7, 5, 14, 0, 8, 9]
[11, 15, 13, 6, 8, 0, 11]
[22, 16, 14, 17, 9, 11, 0]
从 0 到 4 的最短路径为: [0--> 1--> 4]
从 0 到 6 的最短路径为: [0--> 3--> 5--> 6]

参考文献

1. 最短路问题与标号算法(label correcting algorithm)研究(2)

本栏目推荐文章
• 2024/1/13 算法笔记
• Python学习笔记
• python字典的使用
• python字符串方法
• python列表和元组使用介绍
• python | 小游戏 开局托儿所 自动化脚本 pyautogui
• python中的Map和Filter
• python-爬元气桌面壁纸
• python中的*args**和**kwargs
• Python教程(23)——Python类中常用的特殊成员

算法 网路 Python Floyd算法 网路python floyd 算法floyd 二进制 算法floyd 119 算法floyd java 算法floyd spfa 11 算法 模板b3647 floyd 算法 笔记floyd 算法floyd 2.2 算法 注意事项 事项floyd 网路