ダイクストラ法復習

最近グラフ理論的なことを見てる中で久々にダイクストラ法に出会ったので、思い出しがてら書いた。隣接リスト方式のほうは初めて書いた。

-------------------------------------------------------
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
--------------------------------------------------------