# 最短路径算法
# 概述
最短路径算法是图论中的经典算法，用于在加权图中找到从一个顶点到另一个顶点的最短路径。本文将介绍两种常用的最短路径算法：Dijkstra算法和Floyd算法。
# Dijkstra算法
# 算法原理
Dijkstra算法用于解决单源最短路径问题，即从一个源点到其他所有顶点的最短路径。算法的核心思想是贪心策略，每次选择当前未访问的距离最小的顶点。
# 算法步骤
- 初始化：将源点距离设为0，其他顶点距离设为无穷大
- 选择：从未访问的顶点中选择距离最小的顶点
- 更新：更新所选顶点的邻接顶点的距离
- 重复步骤2-3直到所有顶点都被访问
# 复杂度分析
- 时间复杂度：O(V^2)，其中V是顶点数
- 空间复杂度：O(V)
# 代码实现
def dijkstra(graph, start):
n = len(graph)
dist = [float('inf')] * n
dist[start] = 0
visited = [False] * n
for _ in range(n):
# 找到未访问的最小距离顶点
min_dist = float('inf')
u = -1
for v in range(n):
if not visited[v] and dist[v] < min_dist:
min_dist = dist[v]
u = v
if u == -1:
break
visited[u] = True
# 更新邻接顶点的距离
for v in range(n):
if not visited[v] and graph[u][v] != 0:
dist[v] = min(dist[v], dist[u] + graph[u][v])
return dist
# 可视化演示
比较次数: 0
已访问节点:
# Floyd算法
# 算法原理
Floyd算法用于解决多源最短路径问题，即求解图中任意两个顶点之间的最短路径。算法基于动态规划思想。
# 算法步骤
- 初始化：将邻接矩阵作为初始距离矩阵
- 对每个顶点k，更新任意两点i和j之间的距离：
- 如果经过顶点k的路径比直接路径更短，则更新距离
# 复杂度分析
- 时间复杂度：O(V^3)，其中V是顶点数
- 空间复杂度：O(V^2)
# 代码实现
def floyd(graph):
n = len(graph)
dist = [[float('inf')] * n for _ in range(n)]
# 初始化距离矩阵
for i in range(n):
for j in range(n):
if i == j:
dist[i][j] = 0
elif graph[i][j] != 0:
dist[i][j] = graph[i][j]
# Floyd算法核心部分
for k in range(n):
for i in range(n):
for j in range(n):
if dist[i][k] != float('inf') and dist[k][j] != float('inf'):
dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])
return dist
# 可视化演示
比较次数: 0
已访问节点:
# 应用场景
- 导航系统中的路径规划
- 网络路由算法
- 社交网络中的最短关系链
- 物流配送路线优化
# 算法比较
| 算法 | 适用场景 | 时间复杂度 | 空间复杂度 |
|---|---|---|---|
| Dijkstra | 单源最短路径，无负权边 | O(V^2) | O(V) |
| Floyd | 多源最短路径，可处理负权边 | O(V^3) | O(V^2) |