実装メモ
友達にダイクストラ法を教えて貰ったので実装してみた。
inf = float('inf')
TRUE = 1
FALSE = 0
NOT_CHECKED = 0
CHECKED = 1
N = 6
scores = [0,inf,inf,inf,inf,inf]
check = [NOT_CHECKED]*N
graph = [[1,2],[0,2,3],[0,1,3,4],[1,2,4,5],[1,2,3,5],[3,4]]
edg_distance=[
[0,1,6,0,0,0],
[1,0,2,4,4,0],
[6,2,0,1,7,0],
[0,4,1,0,5,2],
[0,4,7,5,0,3],
[0,0,0,2,3,0]
]
def untreated(check):
for flag in check:
if flag == NOT_CHECKED:
return TRUE
return FALSE
def minNode_untreated(scores,check):
min_node = inf
node = 0
N = len(scores)
for i in range(0,N):
if min_node>scores[i] and check[i] == NOT_CHECKED:
min_node = scores[i]
node = i
return node
def dijkdtrs(graph,edg_distance):
while untreated(check):
node_now = minNode_untreated(scores,check)
for node_next in graph[node_now]:
if check[node_next] == 1:
continue
prescore = scores[node_now] + edg_distance[node_now][node_next]
if scores[node_next]>prescore:
scores[node_next] = prescore
check[node_now] = CHECKED
print scores[-1]
dijkdtrs(graph,edg_distance)