最近グラフ理論的なことを見てる中で久々にダイクストラ法に出会ったので、思い出しがてら書いた。隣接リスト方式のほうは初めて書いた。
-------------------------------------------------------
import numpy as np
inf=np.float('inf')
def dykstra_neighborlist(link, start):
end=np.zeros(np.max(link[:, 0:2])+1)+inf
end[start]=0
while np.sum(end)==inf:
candidate=np.zeros(end.shape[0])+inf
for i in range(candidate.shape[0]):
if end[i]!=inf:
neighbor_link=link[link[:, 0]==i]
for j in range(neighbor_link.shape[0]):
if end[neighbor_link[j, 1]]==inf:
length=end[i]+neighbor_link[j, 2]
if candidate[neighbor_link[j, 1]]>length:
candidate[neighbor_link[j, 1]]=length
candidate[end!=inf]=inf
end[np.argmin(candidate)]=np.min(candidate)
return end
def dykstra_linkmatrix(link, start):
end=np.zeros(link.shape[0])+inf
end[start]=0
while np.sum(end)==inf:
length=link+end.reshape(link.shape[0], 1)
length[:, end!=inf]=inf
end[np.argmin(length)%link.shape[0]]=np.min(length)
return end
--------------------------------------------------------
