数据结构与算法之Floyd弗洛伊德算法求最短路径

前言

Floyd弗洛伊德算法

定义

步骤

一、初始化

二、添加中间点

三、迭代

四、得出结果

时间复杂度

代码实现

结束语

前言

今天是坚持写博客的第18天，希望可以继续坚持在写博客的路上走下去。我们今天来看看数据结构与算法当中的弗洛伊德算法。

Floyd弗洛伊德算法

定义

Floyd弗洛伊德算法是一种用于在加权图中找到所有顶点对之间的最短路径的算法。这个算法可以处理带有正权、负权甚至零权（但不存在负权环路）的图。

对于了解Floyd弗洛伊德算法，我们需要先了解几个前置概念：

加权图：图中的每条边都有一个与之关联的权值
最短路径：从一个顶点到另一个顶点的总权值最小的路径
负权环路：一个环路（即一条起点和终点相同的路径），其所有边的权值之和为负。如果存在负权环路，则最短路径问题可能没有解，因为可以通过无限次地遍历这个环路来不断减小路径的总权值。

步骤

假设我们有如下的图：

其中A到B的权值为2，A到C的权值为6，A到D的权值为5，B到C的权值为1，B到D的权值为4，C到D的权值为3。我们可以先得出他的邻接矩阵：

为什么对角线上的值都是零？因为对角线上的路径都是一个环路，图上没有自己指向自己的环路，因此都是0。

下面进入正题，如何使用弗洛伊德算法呢？

一、初始化

首先，为图中所有顶点对(i, j)之间设置一个距离矩阵D，其中D[i][j]表示从顶点i到顶点j的当前已知最短距离。如果两个顶点之间没有直接相连的边，则设置D[i][j]为一个很大的数（通常是一个无穷大的值，表示为∞）。如果两个顶点之间有直接相连的边，则设置D[i][j]为该边的权值。另外，设置一个中间矩阵P，用于记录最短路径的信息。

二、添加中间点

对于图中的每一个顶点k（作为中间点），遍历所有顶点对(i, j)（其中i和j是图中的顶点且i ≠ j，i ≠ k，j ≠ k）。
如果从i到k再到j的路径比已知的i到j的路径更短（即dist[i][k] + dist[k][j] < dist[i][j]），则更新dist[i][j]为dist[i][k] + dist[k][j]。

三、迭代

重复步骤二，对于图中的每一个顶点k都执行一次。由于图中总共有n个顶点，因此这个步骤需要执行n次迭代。

四、得出结果

在完成所有迭代后，dist矩阵将包含图中所有顶点对之间的最短路径长度。如果dist[i][j]的值仍然是无穷大，则表示从顶点i到顶点j没有路径。

时间复杂度

Floyd算法的时间复杂度为O(n^3)，其中n是图中顶点的数量。这是因为算法需要进行n次迭代，每次迭代都需要检查所有n^2个顶点对。

代码实现

下面是大家期待的代码实现，今天我们用python实现

import numpy as np  
  
def floyd_warshall(graph):  
  
    n = len(graph)  
    # 复制邻接矩阵作为距离矩阵  
    dist = np.copy(graph)  
  
    # 遍历所有顶点作为中间点  
    for k in range(n):  
        # 遍历所有顶点对 (i, j)  
        for i in range(n):  
            for j in range(n):  
                # 如果通过顶点 k 可以找到更短的路径  
                if dist[i][k] + dist[k][j] < dist[i][j]:  
                    dist[i][j] = dist[i][k] + dist[k][j]  
  
    return dist  
  
# 示例图（邻接矩阵）  
graph = np.array([  
    [0, 5, float('inf'), 10],  
    [float('inf'), 0, 3, float('inf')],  
    [float('inf'), float('inf'), 0, 1],  
    [float('inf'), float('inf'), float('inf'), 0]  
])  
  
# 调用 Floyd-Warshall 算法  
distances = floyd_warshall(graph)  
  
# 打印结果  
print("Shortest distances between all pairs of vertices:")  
print(distances)