图 - 最短路径算法 - Dijkstra、Floyd 算法

图 - 最短路径算法 - Dijkstra、Floyd 算法

一、引言

在图论中，最短路径问题是一个经典且具有广泛应用的问题。例如在地图导航中，我们需要找到从一个地点到另一个地点的最短路线；在通信网络中，要寻找数据传输的最短路径以减少延迟。Dijkstra 算法和 Floyd 算法就是解决最短路径问题的两种重要算法，下面我们将深入探讨这两种算法。

二、图的基本概念

在介绍算法之前，我们先明确一些图的基本概念。图（Graph）是由顶点（Vertex）和边（Edge）组成的一种数据结构。边可以带有权重（Weight），表示从一个顶点到另一个顶点的代价，比如距离、时间等。我们用邻接矩阵（Adjacency Matrix）来表示图，邻接矩阵是一个二维数组，其中 matrix[i][j] 表示顶点 i 到顶点 j 的边的权重，如果没有边相连，则通常用无穷大（在代码中可以用一个很大的数表示）表示。

三、Dijkstra 算法

3.1 算法思想

Dijkstra 算法是一种贪心算法，用于计算单源最短路径问题，即从一个特定的源顶点到图中其他所有顶点的最短路径。其基本思想是：从源顶点开始，每次选择距离源顶点最近且未确定最短路径的顶点，然后以该顶点为中间点，更新其他顶点到源顶点的距离，直到所有顶点的最短路径都被确定。

3.2 算法步骤

1. 初始化：设置一个距离数组 dist，用于记录每个顶点到源顶点的距离，初始时，源顶点的距离为 0，其他顶点的距离为无穷大。同时，设置一个标记数组 visited，用于标记顶点是否已经确定最短路径，初始时所有顶点都未被标记。
2. 选择顶点：从未被标记的顶点中选择距离源顶点最近的顶点 u，标记 u 为已确定最短路径。
3. 更新距离：以 u 为中间点，更新其他未被标记的顶点到源顶点的距离。如果通过 u 到达某个顶点 v 的距离比当前记录的距离更短，则更新 dist[v] 的值。
4. 重复步骤 2 和 3：直到所有顶点都被标记。

3.3 代码示例（Python）

import sys
def dijkstra(graph, start):
    num_vertices = len(graph)
    dist = [sys.maxsize] * num_vertices
    dist[start] = 0
    visited = [False] * num_vertices
    for _ in range(num_vertices):
        # 选择距离源顶点最近且未被标记的顶点
        min_dist = sys.maxsize
        min_index = -1
        for v in range(num_vertices):
            if not visited[v] and dist[v] < min_dist:
                min_dist = dist[v]
                min_index = v
        # 标记该顶点
        visited[min_index] = True
        # 更新其他顶点的距离
        for v in range(num_vertices):
            if not visited[v] and graph[min_index][v]!= 0 and dist[min_index] + graph[min_index][v] < dist[v]:
                dist[v] = dist[min_index] + graph[min_index][v]
    return dist
# 示例图的邻接矩阵
graph = [
    [0, 4, 0, 0, 0, 0, 0, 8, 0],
    [4, 0, 8, 0, 0, 0, 0, 11, 0],
    [0, 8, 0, 7, 0, 4, 0, 0, 2],
    [0, 0, 7, 0, 9, 14, 0, 0, 0],
    [0, 0, 0, 9, 0, 10, 0, 0, 0],
    [0, 0, 4, 14, 10, 0, 2, 0, 0],
    [0, 0, 0, 0, 0, 2, 0, 1, 6],
    [8, 11, 0, 0, 0, 0, 1, 0, 7],
    [0, 0, 2, 0, 0, 0, 6, 7, 0]
]
start_vertex = 0
distances = dijkstra(graph, start_vertex)
print(f"从顶点 {start_vertex} 到其他顶点的最短距离: {distances}")

3.4 复杂度分析

• 时间复杂度：$O(V^2)$，其中 $V$ 是图的顶点数。如果使用优先队列（堆）来优化选择顶点的过程，时间复杂度可以降低到 $O((V + E) \log V)$，其中 $E$ 是图的边数。
• 空间复杂度：$O(V)$，主要用于存储距离数组和标记数组。

四、Floyd 算法

4.1 算法思想

Floyd 算法是一种动态规划算法，用于计算图中所有顶点对之间的最短路径。其基本思想是：通过不断引入中间顶点，更新任意两个顶点之间的最短路径。具体来说，对于每一对顶点 (i, j)，考虑所有可能的中间顶点 k，如果通过 k 从 i 到 j 的路径比当前记录的路径更短，则更新 i 到 j 的最短路径。

4.2 算法步骤

1. 初始化：使用邻接矩阵 dist 来存储任意两个顶点之间的初始距离。如果两个顶点之间有边相连，则 dist[i][j] 为边的权重；否则，dist[i][j] 为无穷大。同时，dist[i][i] 初始化为 0。
2. 动态规划更新：对于每一个中间顶点 k，对于每一对顶点 (i, j)，如果 dist[i][k] + dist[k][j] < dist[i][j]，则更新 dist[i][j] 的值。
3. 重复步骤 2：直到所有中间顶点都被考虑过。

4.3 代码示例（Python）

import sys
def floyd(graph):
    num_vertices = len(graph)
    dist = [row[:] for row in graph]
    for k in range(num_vertices):
        for i in range(num_vertices):
            for j in range(num_vertices):
                if dist[i][k]!= sys.maxsize and dist[k][j]!= sys.maxsize and dist[i][k] + dist[k][j] < dist[i][j]:
                    dist[i][j] = dist[i][k] + dist[k][j]
    return dist
# 示例图的邻接矩阵
graph = [
    [0, 4, sys.maxsize, sys.maxsize, sys.maxsize, sys.maxsize, sys.maxsize, 8, sys.maxsize],
    [4, 0, 8, sys.maxsize, sys.maxsize, sys.maxsize, sys.maxsize, 11, sys.maxsize],
    [sys.maxsize, 8, 0, 7, sys.maxsize, 4, sys.maxsize, sys.maxsize, 2],
    [sys.maxsize, sys.maxsize, 7, 0, 9, 14, sys.maxsize, sys.maxsize, sys.maxsize],
    [sys.maxsize, sys.maxsize, sys.maxsize, 9, 0, 10, sys.maxsize, sys.maxsize, sys.maxsize],
    [sys.maxsize, sys.maxsize, 4, 14, 10, 0, 2, sys.maxsize, sys.maxsize],
    [sys.maxsize, sys.maxsize, sys.maxsize, sys.maxsize, sys.maxsize, 2, 0, 1, 6],
    [8, 11, sys.maxsize, sys.maxsize, sys.maxsize, sys.maxsize, 1, 0, 7],
    [sys.maxsize, sys.maxsize, 2, sys.maxsize, sys.maxsize, sys.maxsize, 6, 7, 0]
]
distances = floyd(graph)
print("所有顶点对之间的最短距离:")
for row in distances:
    print(row)

4.4 复杂度分析

• 时间复杂度：$O(V^3)$，其中 $V$ 是图的顶点数。因为有三层嵌套循环。
• 空间复杂度：$O(V^2)$，主要用于存储距离矩阵。

五、总结

Dijkstra 算法适用于单源最短路径问题，尤其是图中边的权重为非负的情况。而 Floyd 算法则可以一次性计算出所有顶点对之间的最短路径，适用于需要频繁查询任意两个顶点之间最短路径的场景。通过对这两种算法的学习和应用，我们可以更好地解决图中的最短路径问题。