SPFA算法python
时间: 2024-05-17 10:09:55 浏览: 18
SPFA算法,全称是Shortest Path Faster Algorithm,即最短路径快速算法。它是一种单源最短路径算法,用于解决带权有向图中单个源点到其他所有点的最短路径问题。与Dijkstra算法相比,SPFA算法可以处理负权边,但是可能会出现负环的情况。
以下是SPFA算法的实现步骤:
1. 初始化:设置起点s的距离为0,其他点的距离为正无穷大;将起点s加入队列中。
2. 松弛操作:从队列中取出一个点u,对于u的所有出边(u, v),如果从起点s到v的距离可以通过从u到v的边缩短,则更新v的距离,并将v加入队列中。
3. 重复执行第2步,直到队列为空。
4. 若存在负环,则算法无法计算出最短路径;否则,最终得到起点s到各个点的最短路径长度。
以下是SPFA算法的Python实现:
```
def SPFA(graph, start):
queue = [start] # 初始化队列
dist = {node: float('inf') for node in graph} # 初始化距离
dist[start] = 0
while queue:
u = queue.pop(0)
for v in graph[u]:
if dist[v] > dist[u] + graph[u][v]:
dist[v] = dist[u] + graph[u][v]
if v not in queue:
queue.append(v)
return dist
```
其中graph是一个字典,表示有向图中每个点的出边和对应的权值。例如,`graph = {1: {2: 1, 3: 2}, 2: {3: 3, 4: 4}, 3: {4: -5}, 4: {}}`表示有向图中1号节点有两个出边分别指向2号节点和3号节点,权值分别为1和2。