? ? ? ? 增加對最短路徑的優化算法、負權回路、單源有限最短的講解
Bellman_ford 隊列優化算法
--------------------------------------------------------------------------------
? ? ? ? 8.24更新：該算法是針對帶負值的最短路徑的優化算法，核心通過隊列來實現，代碼中visit數組來標記在隊列中的元素，以防重復入隊，每次循環一個節點的出度，即自該節點出發的邊，模擬過程中隊列判斷n次（均由隊列實現，具體次數無循環語句要求）
--------------------------------------------------------------------------------
????????我們之前的松弛算法，是對所有邊進行松弛，真正有效的松弛，只有松弛 邊（節點1->節點2） 和 邊（節點1->節點3）。而松弛 邊（節點4->節點6），邊（節點5->節點3）等等 都是無效的操作，因為 節點4 和 節點 5 都是沒有被計算過的節點。所以 Bellman_ford 算法 每次都是對所有邊進行松弛，其實是多做了一些無用功。
????????只需要對 上一次松弛的時候更新過的節點作為出發節點所連接的邊 進行松弛就夠了。
????????基于以上思路，如何記錄 上次松弛的時候更新過的節點呢？用隊列來記錄。簡單理解就是每次mindist數組中被更新過的位置就是需要入棧的元素，然后棧頂元素進行松弛操作出棧，同時被修改的元素入棧，最后完成所有的循環（其實用棧也行，對元素順序沒有要求）
效率分析
????????如果圖越稠密，則 SPFA的效率越接近與 Bellman_ford。反之，圖越稀疏，SPFA的效率就越高。一般來說，SPFA 的時間復雜度為 O(K * N) K 為不定值，因為 節點需要計入幾次隊列取決于 圖的稠密度。
????????SPFA（隊列優化版Bellman_ford） 在理論上 時間復雜度更勝一籌，但實際上，也要看圖的稠密程度，如果 圖很大且非常稠密的情況下，雖然 SPFA的時間復雜度接近Bellman_ford，但實際時間消耗 可能是 SPFA耗時更多。
代碼實現
????????最根本的理解，我們這個代碼是以邊為主的，注意本題沒有 負權回路 。
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)minDist[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"):return "unconnected"return minDist[-1]if __name__ == "__main__":print(main())Bellman_ford 判斷負權回路
--------------------------------------------------------------------------------
? ? ? ? 8.24更新：核心思路就是多松弛一次，看mindist數組有沒有變化（負權回路會導致mindist數組變化)，優化算法中的判斷負權回路：如果節點加入隊列的次數 超過了 n-1次 ，那么該圖就一定有負權回路。
? ? ? ? 怎么判斷數組有沒有變化？還是一樣的邏輯，看有沒有變小即可
? ? ? ? 最后一點，普通方法把邊都遍歷一遍這種，沒有什么特別的說法，直接多松弛一次即可，但是優化算法中的負權回路，因為引入了隊列，所以一定記得對于隊列內已經進入的元素不要重復進入，（這個是上一題目中的基本內容了），這里的拓展我認為有一些主動寫錯來糾偏的部分了，反而可能更加容易引起誤導
--------------------------------------------------------------------------------
????????本題是要我們判斷 負權回路，也就是圖中出現環且環上的邊總權值為負數。如果在這樣的圖中求最短路的話， 就會在這個環里無限循環 （也是負數+負數 只會越來越小），無法求出最短路徑。
????????在上期博客中，bellman_ford 算法的核心就是一句話：對 所有邊 進行 n-1 次松弛。?在沒有負權回路的圖中，松弛 n 次以上 ，結果不會有變化。但本題有 負權回路，如果松弛 n 次，結果就會有變化了，因為 有負權回路 就是可以無限最短路徑（一直繞圈，就可以一直得到無限小的最短距離）。
????????那么解決本題的 核心思路，就是在?n-1 次松弛?的基礎上，再多松弛一次，看minDist數組 是否發生變化。
Bellman-Ford方法
import sysdef main():input = sys.stdin.readdata = input().split()index = 0n = int(data[index])index += 1m = int(data[index])index += 1grid = []for i in range(m):p1 = int(data[index])index += 1p2 = int(data[index])index += 1val = int(data[index])index += 1# p1 指向 p2，權值為 valgrid.append([p1, p2, val])start = 1 # 起點end = n # 終點minDist = [float('inf')] * (n + 1)minDist[start] = 0flag = Falsefor i in range(1, n + 1): # 這里我們松弛n次，最后一次判斷負權回路for side in grid:from_node = side[0]to = side[1]price = side[2]if i < n:if minDist[from_node] != float('inf') and minDist[to] > minDist[from_node] + price:minDist[to] = minDist[from_node] + priceelse: # 多加一次松弛判斷負權回路if minDist[from_node] != float('inf') and minDist[to] > minDist[from_node] + price:flag = Trueif flag:print("circle")elif minDist[end] == float('inf'):print("unconnected")else:print(minDist[end])if __name__ == "__main__":main()
SPFA方法
? ? ? ? 這里涉及的問題是節點重復入隊，導致本應n-1次結束的過程，沒有按時結束，我們需要記錄哪些節點已經出隊列了，哪些節點在隊列里面，對于還在隊列內部的節點不要重復入隊
from collections import deque
from math import infdef main():n, m = [int(i) for i in input().split()]graph = [[] for _ in range(n+1)]min_dist = [inf for _ in range(n+1)]count = [0 for _ in range(n+1)] # 記錄節點加入隊列的次數for _ in range(m):s, t, v = [int(i) for i in input().split()]graph[s].append([t, v])min_dist[1] = 0 # 初始化count[1] = 1d = deque([1])flag = Falsewhile d: # 主循環cur_node = d.popleft()for next_node, val in graph[cur_node]:if min_dist[next_node] > min_dist[cur_node] + val:min_dist[next_node] = min_dist[cur_node] + valcount[next_node] += 1if next_node not in d: # 二刷的時候再好好理解d.append(next_node)if count[next_node] == n: # 如果某個點松弛了n次，說明有負回路flag = Trueif flag:breakif flag:print("circle")else:if min_dist[-1] == inf:print("unconnected")else:print(min_dist[-1])if __name__ == "__main__":main()Bellman_ford 單源有限最短路
--------------------------------------------------------------------------------
? ? ? ? 8.24更新：節點數量為n，起點到終點，最多是 n-1 條邊相連。 那么對所有邊松弛 n-1 次 就一定能得到 起點到達 終點的最短距離。這個n - 1要理解，這也是松弛的最基本邏輯，就不多講了。（如果對以上講解看不懂，建議詳看?kama94.城市間貨物運輸I?）
? ? ? ? 但是僅有這個理解是不夠的，這里我還是要吐槽一下，可能是我沒看視頻，我認為這道題目的文字版解析說的不好，可能是我沒有理解到位，我認為出現問題的本質是：在修改過程中修改了已經遍歷過的節點的值，地基變了，自然下一輪中所有的值都會修改，引起這個問題的本質是：路徑中存在負權回路，而不是文字版講解中說的：基于了本次松弛的 minDist數值，而不是上一次 松弛時候minDist的數值。這個講解歪曲了這個問題的本質，反而讓全文顯得很啰嗦并且具有誤導性。
? ? ? ? 解決這個問題的方法是：解決負權環路的判斷，如何解決？環路最少有兩條邊，隔開這兩條邊，也就是文字版解析中給出的解決方法，但是這個是后驗的，不可以在開始就把問題歸結到這一點上
? ? ? ? 最后dijkstra顯然是不能用的
--------------------------------------------------------------------------------
????????注意題目中描述是?最多經過 k 個城市的條件下，而不是一定經過k個城市，也可以經過的城市數量比k小，但要最短的路徑。對于部分路徑節點多但是距離短的結果增加了要求
????????在?這個系列的第一個題目 中我們講了：對所有邊松弛一次，相當于計算 起點到達 與起點一條邊相連的節點 的最短距離。節點數量為n，起點到終點，最多是 n-1 條邊相連。 那么對所有邊松弛 n-1 次 就一定能得到 起點到達 終點的最短距離。本題是最多經過 k 個城市， 那么是 k + 1條邊相連的節點。?
Bellman-Ford方法求解單源有限最短路
def main():# 輸入n, m = map(int, input().split())edges = list()for _ in range(m):edges.append(list(map(int, input().split() )))start, end, k = map(int, input().split())min_dist = [float('inf') for _ in range(n + 1)]min_dist[start] = 0# 只能經過k個城市，所以從起始點到中間有(k + 1)個邊連接# 需要鬆弛(k + 1)次for _ in range(k + 1):update = Falsemin_dist_copy = min_dist.copy()for src, desc, w in edges:if (min_dist_copy[src] != float('inf') and min_dist_copy[src] + w < min_dist[desc]):min_dist[desc] = min_dist_copy[src] + wupdate = Trueif not update:break# 輸出if min_dist[end] == float('inf'):print('unreachable')else:print(min_dist[end])if __name__ == "__main__":main()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()
 經典面試筆試50題（包括詳細答案）)
