代码随想录算法训练营第六十天|KM94.城市间货物运输Ⅰ|KM95.城市间货物运输Ⅱ|KM96.城市间货物运输Ⅲ

94. 城市间货物运输 I

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

        SPFA是对Bellman_ford算法的优化，由于Bellman_ford 算法 每次都是对所有边进行松弛，其实是多做了一些无用功。其实只需要对 上一次松弛的时候更新过的节点作为出发节点所连接的边 进行松弛就够了。

import collectionsdef main():n, m = map(int, input().strip().split())edges = [[] for _ in range(n+1)]for _ in range(m):src, dest, weight = map(int, input().strip().split())edges[src].append([dest, weight])# 初始化minDist = [float('inf')] * (n+1)# 第一个节点为0minDist[1] = 0que = collections.deque([1])visited = [False] * (n+1)visited[1] = Truewhile que:cur = que.popleft()visited[cur] = Falsefor dest, weight in edges[cur]:if minDist[cur] != float('inf') and minDist[cur] + weight < minDist[dest]:minDist[dest] = minDist[cur] + weightif visited[dest] == False:que.append(dest)visited[dest] = Trueif minDist[-1] == float('inf'):print('unconnnected')return minDist[-1]if __name__ == '__main__':print(main())

95. 城市间货物运输 II

        本题是要我们判断 负权回路，也就是图中出现环且环上的边总权值为负数。

        如果在这样的图中求最短路的话， 就会在这个环里无限循环 （也是负数+负数 只会越来越小），无法求出最短路径。(有负权回路的情况下，一直都会有更短的最短路，所以 松弛 第n次，minDist数组 也会发生改变。)

import collections
from math import inf
def main():n, m = map(int, input().strip().split())edges = [[] for _ in range(n+1)]# 记录节点接入队列的次数count = [0 for _ in range(n+1)]for _ in range(m):src, dest, weight = map(int, input().strip().split())edges[src].append([dest, weight])# 初始化minDist = [float('inf')] * (n+1)# 第一个节点为0minDist[1] = 0que = collections.deque([1])count[1] = 1flag = False# 主循环while que:cur = que.popleft()for dest, weight in edges[cur]:if minDist[cur] + weight < minDist[dest]:minDist[dest] = minDist[cur] + weightcount[dest] += 1if dest not in que:que.append(dest)if count[dest] == n:flag = Trueif flag:breakif flag:print('circle')else:if minDist[-1] == float('inf'):print('unconnected')else:print(minDist[-1])if __name__ == '__main__':main()

96. 城市间货物运输 III

本题理解起来有点难度，放着等二刷；

使用SPFA方法求解单源有限最短路；

from collections import deque
from math import infdef main():n, m = [int(i) for i in input().split()]graph = [[] for _ in range(n+1)]for _ in range(m):v1, v2, val = [int(i) for i in input().split()]graph[v1].append([v2, val])src, dst, k = [int(i) for i in input().split()]min_dist = [inf for _ in range(n+1)]min_dist[src] = 0  # 初始化起点的距离que = deque([src])while k != -1 and que:visited = [False for _ in range(n+1)]  # 用于保证每次松弛时一个节点最多加入队列一次que_size = len(que)temp_dist = min_dist.copy()  # 用于记录上一次遍历的结果for _ in range(que_size):cur_node = que.popleft()for next_node, val in graph[cur_node]:if min_dist[next_node] > temp_dist[cur_node] + val:min_dist[next_node] = temp_dist[cur_node] + valif not visited[next_node]:que.append(next_node)visited[next_node] = Truek -= 1if min_dist[dst] == inf:print("unreachable")else:print(min_dist[dst])if __name__ == "__main__":main()