代码随想录算法训练营第六十五天| 图论10

Bellman_ford 队列优化算法（又名SPFA）

         

代码随想录

     

1. import collections
3. def main():
4.     n, m = map(int, input().strip().split())
5.     edges = [[] for _ in range(n + 1)]
6.     for _ in range(m):
7.         src, dest, weight = map(int, input().strip().split())
8.         edges[src].append([dest, weight])
9.    
10.     minDist = [float("inf")] * (n + 1)
11.     minDist[1] = 0
12.     que = collections.deque([1])
13.     visited = [False] * (n + 1)
14.     visited[1] = True
15.    
16.     while que:
17.         cur = que.popleft()
18.         visited[cur] = False
19.         for dest, weight in edges[cur]:
20.             if minDist[cur] != float("inf") and minDist[cur] + weight < minDist[dest]:
21.                 minDist[dest] = minDist[cur] + weight
22.                 if visited[dest] == False:
23.                     que.append(dest)
24.                     visited[dest] = True
25.    
26.     if minDist[-1] == float("inf"):
27.         return "unconnected"
28.     return minDist[-1]
30. if __name__ == "__main__":
31.     print(main())

复制代码

  bellman_ford之判定负权回路

      

代码随想录

     

1. import sys
3. def main():
4.     input = sys.stdin.read
5.     data = input().split()
6.     index = 0
7.    
8.     n = int(data[index])
9.     index += 1
10.     m = int(data[index])
11.     index += 1
12.    
13.     grid = []
14.     for i in range(m):
15.         p1 = int(data[index])
16.         index += 1
17.         p2 = int(data[index])
18.         index += 1
19.         val = int(data[index])
20.         index += 1
21.         # p1 指向 p2，权值为 val
22.         grid.append([p1, p2, val])
24.     start = 1  # 起点
25.     end = n    # 终点
27.     minDist = [float('inf')] * (n + 1)
28.     minDist[start] = 0
29.     flag = False
31.     for i in range(1, n + 1):  # 这里我们松弛n次，最后一次判断负权回路
32.         for side in grid:
33.             from_node = side[0]
34.             to = side[1]
35.             price = side[2]
36.             if i < n:
37.                 if minDist[from_node] != float('inf') and minDist[to] > minDist[from_node] + price:
38.                     minDist[to] = minDist[from_node] + price
39.             else:  # 多加一次松弛判断负权回路
40.                 if minDist[from_node] != float('inf') and minDist[to] > minDist[from_node] + price:
41.                     flag = True
43.     if flag:
44.         print("circle")
45.     elif minDist[end] == float('inf'):
46.         print("unconnected")
47.     else:
48.         print(minDist[end])
50. if __name__ == "__main__":
51.     main()

复制代码

  bellman_ford之单源有限最短路

      

代码随想录

      

1. def main():
2.     # 輸入
3.     n, m = map(int, input().split())
4.     edges = list()
5.     for _ in range(m):
6.         edges.append(list(map(int, input().split() )))
7.    
8.     start, end, k = map(int, input().split())
9.     min_dist = [float('inf') for _ in range(n + 1)]
10.     min_dist[start] = 0
11.    
12.     # 只能經過k個城市，所以從起始點到中間有(k + 1)個邊連接
13.     # 需要鬆弛(k + 1)次
14.    
15.     for _ in range(k + 1):
16.         update = False
17.         min_dist_copy = min_dist.copy()
18.         for src, desc, w in edges:
19.             if (min_dist_copy[src] != float('inf') and
20.             min_dist_copy[src] + w < min_dist[desc]):
21.                 min_dist[desc] = min_dist_copy[src] + w
22.                 update = True
23.         if not update:
24.             break
25.     # 輸出
26.     if min_dist[end] == float('inf'):
27.         print('unreachable')
28.     else:
29.         print(min_dist[end])
30.             
31.             
33. if __name__ == "__main__":
34.     main()

复制代码

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。