最短路径（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
