图论算法面试高频：最短路径变形问题解析与代码实现
在图论中，最短路径问题是一个经典且重要的课题。它广泛应用于网络设计、路径规划、物流运输等领域。在面试中，最短路径问题及其变形往往是考察算法和数据结构能力的重点。本文将围绕最短路径变形问题，探讨几种常见的算法，并给出相应的代码实现。
1. Dijkstra算法
Dijkstra算法是一种用于在加权图中找到单源最短路径的算法。它适用于非负权重的图。
1.1 算法原理
Dijkstra算法的基本思想是维护一个集合S，其中包含已确定最短路径的顶点。算法开始时，S为空，然后逐步扩大S，直到包含所有顶点。
1. 初始化：将源点加入S，其余顶点的距离设为无穷大，记录源点到其余顶点的最短路径。
2. 循环：从集合S中选取距离最小的顶点u，将其加入S。
3. 更新：对于集合S中的每个顶点v，如果存在从u到v的边，并且通过u到v的距离小于当前记录的距离，则更新v的距离和最短路径。
1.2 代码实现
python
import heapq
def dijkstra(graph, start):
distances = {vertex: float('infinity') for vertex in graph}
distances[start] = 0
priority_queue = [(0, start)]
while priority_queue:
current_distance, current_vertex = heapq.heappop(priority_queue)
if current_distance > distances[current_vertex]:
continue
for neighbor, weight in graph[current_vertex].items():
distance = current_distance + weight
if distance < distances[neighbor]:
distances[neighbor] = distance
heapq.heappush(priority_queue, (distance, neighbor))
return distances
示例图
graph = {
'A': {'B': 1, 'C': 4},
'B': {'A': 1, 'C': 2, 'D': 5},
'C': {'A': 4, 'B': 2, 'D': 1},
'D': {'B': 5, 'C': 1}
}
测试
print(dijkstra(graph, 'A'))
2. Bellman-Ford算法
Bellman-Ford算法是一种用于在加权图中找到单源最短路径的算法。它适用于有负权边的图。
2.1 算法原理
Bellman-Ford算法的基本思想是逐步放松边，即对于每一条边(u, v)，如果存在从源点到u的路径，并且通过(u, v)的距离小于当前记录的距离，则更新v的距离。
1. 初始化：将源点的距离设为0，其余顶点的距离设为无穷大。
2. 循环：对于图中的每一条边，执行放松操作。
3. 检查负权重循环：如果存在从源点到某个顶点的路径，并且该路径的权重小于0，则图中存在负权重循环。
2.2 代码实现
python
def bellman_ford(graph, start):
distances = {vertex: float('infinity') for vertex in graph}
distances[start] = 0
for _ in range(len(graph) - 1):
for u in graph:
for v, weight in graph[u].items():
if distances[u] + weight < distances[v]:
distances[v] = distances[u] + weight
检查负权重循环
for u in graph:
for v, weight in graph[u].items():
if distances[u] + weight < distances[v]:
raise ValueError("Graph contains a negative weight cycle")
return distances
测试
print(bellman_ford(graph, 'A'))
3. Floyd-Warshall算法
Floyd-Warshall算法是一种用于在加权图中找到所有顶点对之间的最短路径的算法。
3.1 算法原理
Floyd-Warshall算法的基本思想是逐步更新路径，即对于每一条边(u, v)，如果存在从源点到u的路径，并且通过(u, v)的距离小于当前记录的距离，则更新v的距离。
1. 初始化：将所有顶点的距离设为无穷大，对角线上的距离设为0。
2. 循环：对于每个顶点k，执行以下操作：
- 对于每个顶点i，如果存在从源点到i的路径，并且通过(i, k)的距离小于当前记录的距离，则更新i到k的距离。
- 对于每个顶点j，如果存在从源点到k的路径，并且通过(k, j)的距离小于当前记录的距离，则更新i到j的距离。
3.2 代码实现
python
def floyd_warshall(graph):
distances = [[float('infinity')] len(graph) for _ in range(len(graph))]
for i in range(len(graph)):
distances[i][i] = 0
for u in range(len(graph)):
for v, weight in graph[u].items():
distances[u][v] = weight
for k in range(len(graph)):
for i in range(len(graph)):
for j in range(len(graph)):
if distances[i][k] + distances[k][j] < distances[i][j]:
distances[i][j] = distances[i][k] + distances[k][j]
return distances
测试
print(floyd_warshall(graph))
4. 总结
本文介绍了三种最短路径变形问题的算法：Dijkstra算法、Bellman-Ford算法和Floyd-Warshall算法。这些算法在面试中经常出现，掌握它们对于提高算法和数据结构能力具有重要意义。在实际应用中，根据具体问题选择合适的算法，可以有效地解决最短路径问题。
Comments NOTHING