LeetCode Bellman-Ford 算法题解

LeetCode Bellman-Ford 算法题解

题目描述

Bellman-Ford 算法是一种用于解决单源最短路径问题的算法。与 Dijkstra 算法不同，Bellman-Ford 算法可以处理带有负权边的图，并且可以检测是否存在负权环。

示例：

对于以下加权图：

A --(2)-- B --(4)-- C | | | (1) (-3) (1) | | | D --(5)-- E --(2)-- F

从 A 出发到各节点的最短路径长度为：

• A → D: 1
• A → B: 2
• A → E: 2 + (-3) = -1
• A → C: 2 + 4 = 6
• A → F: 2 + (-3) + 2 = 1

解题思路

方法：Bellman-Ford 算法

思路：

• Bellman-Ford 算法的核心思想是通过松弛操作来逐步逼近最短路径。它通过最多 V-1 次松弛操作（其中 V 是顶点数）来确保找到从源节点到所有其他节点的最短路径。
• 具体步骤：
  1. 初始化一个距离数组，源节点的距离为 0，其他节点的距离为无穷大。
  2. 对所有边进行 V-1 次松弛操作：对于每条边 (u, v)，如果通过 u 到达 v 的距离比已知的距离小，则更新距离。
  3. 检查是否存在负权环：对所有边进行一次松弛操作，如果还能更新距离，则存在负权环。

复杂度分析：

• 时间复杂度：O(V * E)，其中 V 是顶点数，E 是边数。需要进行 V-1 次松弛操作，每次操作遍历所有边。
• 空间复杂度：O(V)，需要存储距离数组。

代码实现

方法：Bellman-Ford 算法

# Bellman-Ford 算法 def bellman_ford(graph, start): # 获取所有节点 nodes = set() for u in graph: nodes.add(u) for v in graph[u]: nodes.add(v) nodes = list(nodes) V = len(nodes) # 初始化距离字典，源节点的距离为 0，其他节点的距离为无穷大 distances = {node: float('infinity') for node in nodes} distances[start] = 0 # 进行 V-1 次松弛操作 for _ in range(V - 1): updated = False # 遍历所有边 for u in graph: for v, weight in graph[u].items(): # 松弛操作：如果通过 u 到达 v 的距离比已知的距离小，则更新距离 if distances[u] + weight < distances[v]: distances[v] = distances[u] + weight updated = True # 如果没有更新，提前结束 if not updated: break # 检查是否存在负权环 has_negative_cycle = False for u in graph: for v, weight in graph[u].items(): if distances[u] + weight < distances[v]: has_negative_cycle = True break if has_negative_cycle: break return distances, has_negative_cycle # 测试 def test_bellman_ford(): # 构建图结构（邻接表） graph = { 'A': {'B': 2, 'D': 1}, 'B': {'A': 2, 'C': 4, 'E': -3}, 'C': {'B': 4, 'F': 1}, 'D': {'A': 1, 'E': 5}, 'E': {'B': -3, 'D': 5, 'F': 2}, 'F': {'C': 1, 'E': 2} } # 测试从 A 出发的最短路径 print("Shortest distances from A:") distances, has_negative_cycle = bellman_ford(graph, 'A') for node, distance in distances.items(): print(f"{node}: {distance}") print(f"Has negative cycle: {has_negative_cycle}") # 输出： # A: 0 # B: 2 # D: 1 # E: -1 # C: 6 # F: 1 # Has negative cycle: False if __name__ == "__main__": test_bellman_ford()

测试用例

测试用例：从 A 出发的最短路径

输入：

A --(2)-- B --(4)-- C | | | (1) (-3) (1) | | | D --(5)-- E --(2)-- F

输出：

Shortest distances from A: A: 0 B: 2 D: 1 E: -1 C: 6 F: 1 Has negative cycle: False

总结

Bellman-Ford 算法是一种重要的图论算法，它可以用于解决单源最短路径问题，并且可以处理带有负权边的图。通过松弛操作，Bellman-Ford 算法可以逐步逼近最短路径，并检测是否存在负权环。

Bellman-Ford 算法的核心思想是：通过最多 V-1 次松弛操作来确保找到从源节点到所有其他节点的最短路径，然后检查是否存在负权环。

掌握 Bellman-Ford 算法的原理和实现，对于理解和解决图论相关问题非常重要。