迪杰斯特拉算法用来解决在有向有权图中某一个点到任意一点的最短路径问题。
注意：只能用来解决权为非零的情况，不能够解决权为负数的情况
思想：我是一个搬运工
思想就不讲了，主要是代码：
def dijstra(adjacent,stc,dst,n): visited=[] #是否已经检查过 dic=[Inf]*n #每一个节点的到初始节点的距离 dic[stc]=0 #初始节点的距离为0 current=stc #当前的节点 for _ in range(n-1): #因为除了初始节点都需要操作 visited.append(current) #节点已经被选择 #每一次选择的路径最小的节点为下一个目标，每一次都要初始化 next_curret,current_value=None,Inf for i in range(n): #迪杰斯特拉思想：当i节点的路径长度比初始节点到当前节点到current的长度+当前节点到i的路径长度大时，更换路径长度 if i not in visited and dic[i] > adjacent[current][i]+dic[current]: dic[i] = adjacent[current][i]+dic[current] if dic[i] < current_value : #选出路径最小的节点为下一个current next_curret ,current_value= i,dic[i] current,current_dict=next_curret,current_value print(dic) return dic[dst]数据：
Inf = float('inf') Adjacent = [[0, 1, 12, Inf, Inf, Inf], [Inf, 0, 9, 3, Inf, Inf], [Inf, Inf, 0, Inf, 5, Inf], [Inf, Inf, 4, 0, 13, 15], [Inf, Inf, Inf, Inf, 0, 4], [Inf, Inf, Inf, Inf, Inf, 0]] Src, Dst, N = 0, 5, 6结果：
[0, 1, 8, 4, 13, 17] 17佛洛依德算法能够在邮有向加权图中解决随意两个节点间的最短距离
思想： 把每一个节点作为每一条路的中心节点比较，以k为中点的路径，dist[i][j]与dist[i][k]+dist[k][j]的区别
代码：（动态规划，太粗暴了）
def floyd(adjacent,n,stc,dst): for k in range(n): for i in range(n): for j in range(n): if adjacent[i][j] > adjacent[i][k] + adjacent[k][j]: # 两个顶点直接较小的间接路径替换较大的直接路径 adjacent[i][j] = adjacent[i][k] + adjacent[k][j] for i in range(n): print(adjacent[i]) return adjacent[stc][dst] [0, 1, 8, 4, 13, 17] [inf, 0, 7, 3, 12, 16] [inf, inf, 0, inf, 5, 9] [inf, inf, 4, 0, 9, 13] [inf, inf, inf, inf, 0, 4] [inf, inf, inf, inf, inf, 0] 16结果呢和迪杰斯特拉算法是一样的，虽然粗暴，但是很满意呀嘿嘿，后面遇到题会回来加上的。毕竟我是菜鸟，我不是大神。我不会停止想飞的梦想。
