最短路徑（dijkstra 與 Floyd）
1. 如何建圖？
要跑最短路，首先要有圖 ——
魯迅
常用的存儲方法有兩種，分別是鄰接矩陣（用二維數組表示邊）和鄰接表（模擬鏈表表示邊）兩種，他們各有不同的優勢和不足：
| 鄰接矩陣 | 鄰接表 | |
|---|---|---|
| 使用範圍 | 稠密圖 | 主要是稀疏圖 |
| 空間耗費 | n^2（n節點數） | 理論上是 e（ e為邊條數） |
| 實現方式 | 二維數組 | 存儲每個節點相連的節點和邊權值 |
通常來講，在數據範圍足夠小時，我們採用鄰接矩陣，而數據範圍大時採用鄰接表
鄰接矩陣實現：
無權圖：
g[x][y]=1 #g[x][y]=1表示x到y有一條邊連接
#g[y][x]=1 #去掉注釋後是無向圖
帶權圖：
g[x][y]=w #g[x][y]=w表示x到y有一條權值為w的邊
#g[y][x]=w #去掉注釋後是無向圖
2. Floyd
多源最短路演算法，用鄰接矩陣存儲，可以處理負邊權，但不能處理負環
多源最短路就是說只要跑一次，任意兩點的最短路都能求啦(￣︶￣)，而其他單源最短路跑一次只能得出一個點到其他點的最短路
用鄰接矩陣存最短路（ dis[i][j]表示 i到j的最短距離）開一個三重循環（！）
外層枚舉中間點，中間枚舉起點，內層枚舉終點，當三個點互不相同時進行鬆弛操作，如果經過中間點之後的路程和比原路程短，就更新距離，一輪過後，我們得到了一個新的矩陣，然後我們把中間點換成下一個點，再次鬆弛，的到一個新的矩陣，執行 n 次之後，第 n個矩陣就是我們的答案啦
#提前將鄰接矩陣存在dis數組裡，其他不連通的地方初始化成無窮大
for k in range(n): #枚舉中間點
for i in range(n): #枚舉起點
if(i!=k): #節省時間，如果一樣就不往下走
for j in range(n): #枚舉終點
if(i!=j and j!=k): #繼續判斷，如果有一樣的就不往下走
dis[i][j] = min(dis[i][j],dis[i][k]+dis[k][j])
3. Dijkstra
單源最短路徑
將所有節點分成兩類：已確定從起點到當前點的最短路長度的節點，以及未確定從起點到當前點的最短路長度的節點（下面簡稱「未確定節點」和「已確定節點」）。
每次從「未確定節點」中取一個與起點距離最短的點，將它歸類為「已確定節點」，並用它「更新」從起點到其他所有「未確定節點」的距離。直到所有點都被歸類為「已確定節點」。
用節點 A「更新」節點 B 的意思是，用起點到節點 A 的最短路長度加上從節點 A 到節點 B 的邊的長度，去比較起點到節點 B 的最短路長度，如果前者小於後者，就用前者更新後者。這種操作也被叫做「鬆弛」。
這裡暗含的資訊是：每次選擇「未確定節點」時，起點到它的最短路徑的長度可以被確定。
——力扣（LeetCode）
def dijkstra(u):
#初始化起點 u 到每一個點的距離
for k in range(n):
dis[k] = g[u][k]
print("起點到其他節點的初始距離：",dis)
used[u] = 1
for k in range(n):
minv = float('inf')
#在未確定節點中找與起點距離最短的
for i in range(n):
if not used[i] and dis[i] < minv:
minv = dis[i]
temp = i
#中轉位置, 變為已確定節點，更新距離
used[temp] = 1
for i in range(n):
if g[temp][i]+dis[temp] < dis[i]:
dis[i] = g[temp][i]+dis[temp]
print("第 {} 次迭代，起點到其他節點的距離：{}".format(k,dis))
測試下
with open("path.txt",'r') as f:
n = int(f.readline())
weights = f.readlines()
print("頂點數：",n)
dis = [0]*n
used = [0]*n
# 定義鄰接矩陣存儲圖
g = [[0]*n for _ in range(n)]
for u in range(n):
for v in range(n):
g[u][v] = int(weights[u].strip().split()[v])
print("鄰接矩陣：",g)
# g[u][v] = g[v][u] = w # 創建圖，節點間沒有連接賦值為 無窮大
dijkstra(0)
執行結果：
起點到其他節點的初始距離： [65535, 33, 21, 26, 65535, 65535, 65535, 65535]
第 0 次迭代，起點到其他節點的距離：[42, 33, 21, 26, 65535, 42, 65535, 65535]
第 1 次迭代，起點到其他節點的距離：[42, 33, 21, 26, 62, 42, 96, 117]
第 2 次迭代，起點到其他節點的距離：[42, 33, 21, 26, 62, 42, 96, 117]
第 3 次迭代，起點到其他節點的距離：[42, 33, 21, 26, 62, 42, 71, 117]
第 4 次迭代，起點到其他節點的距離：[42, 33, 21, 26, 62, 42, 71, 117]
第 5 次迭代，起點到其他節點的距離：[42, 33, 21, 26, 62, 42, 71, 117]
第 6 次迭代，起點到其他節點的距離：[42, 33, 21, 26, 62, 42, 71, 117]
第 7 次迭代，起點到其他節點的距離：[42, 33, 21, 26, 62, 42, 71, 117]
附上數據
8
65535 33 21 26 65535 65535 65535 65535 65535
33 0 65535 27 30 65535 65535 65535 65535
21 65535 0 22 65535 21 65535 65535 65535
26 27 22 019 36 33 70 91
65535 30 65535 190 65535 41 64 80
65535 65535 21 36 65535 0 29 65535 65535
65535 65535 65535 33 41 290 22 65535
65535 65535 65535 70 64 65535 22 0 42
references:
//www.cnblogs.com/Staceyacm/p/10782094.html
//www.luogu.com.cn/blog/FrozaFerrari/xue-tu-lun-ni-zhen-di-liao-xie-zui-duan-lu-ma-post
//www.bilibili.com/video/BV1q4411M7r9/?spm_id_from=333.788.videocard.1
