图与网络优化–dijkstra算法

给定赋权有向图D=(V, A)，求V1-V8的最短路径。
 开始(i=0)给 Vs 以 P标号， 即P(Vs)=0， λ(Vs)=0；其余各点均给T标号，即对每一 个V≠Vs，T(V)=+∞，λ(V)=M。令S0={Vs}
 ① 如果Si=V，算法终止，这时，对每个 V∈Si，d(Vs,V)=P(V)；否则转入②。
 ② 若Vk为刚获得P标号的点，考查每个使 (Vk,Vj)∈A且Vj不属于Si的点Vj。如果T(Vj) > P(Vk)+wkj ，则将T(Vj)修改 为 P(Vk)+wkj，令λ(Vj )=k 。
 ③ 令T(Vj)=min{T(Vj)}(Vj不属于Si)。 如果T(Vj)<+∞，则把的T标号变为P标号， 令Si+1=Si U {Vj}，把i换成i+1，转入①； 否 则 终 止 ， 这 时 对 每 一 个 v∈Si ， d(Vs,v)=P(V)， 而 对 每 一 个V不属于Si， d(Vs,V)=T(V)。

import numpy as npdismat = np.array([[0,6,3,1,0,0,0,0,0],[0,0,0,0,1,0,0,0,0],[0,2,0,2,0,0,0,0,0],[0,0,0,0,0,10,0,0,0],[0,0,0,6,0,4,3,6,0],[0,0,0,0,10,0,2,0,0],[0,0,0,0,0,0,0,4,0],[0,0,0,0,0,0,0,0,0],[0,0,0,0,2,0,0,3,0]])p = [-1 for i in range(dismat.shape[0])]     #起始点到各点的最短距离PT = [\'T\' for i in range(dismat.shape[0])]   #各点的标号λ = [-1 for i in range(dismat.shape[0])]     #最短路中各点至前一个点的最短路T = [float(\"inf\") for i in range(dismat.shape[0])]    #各点的T标号值s = []                                       #具P标号的点的集合p[0] = 0                                     # 0为第一个获得P标号的点PT[0] = \'P\'λ[0] = 0T[0] = 0s.append(0)while len(s) != 9:for k in s:for i in range(len(dismat[k])):if dismat[k][i] != 0 and i not in s:if T[i] > p[k] + dismat[k][i]:T[i] = p[k] + dismat[k][i]λ[i] = kminVal = float(\"inf\")for i in range(len(T)):if PT[i] != \'P\' and T[i] < minVal:minVal = T[i]PT[T.index(minVal)] = \'P\'p[T.index(minVal)] = minVals.append(T.index(minVal))print(p)print(λ)