Python ダイクストラ法 ( Dijkstra's algorithm ) で最短経路を求める

最短経路問題をダイクストラ法を用いて解きます。

(ダイクストラ法についてWikipediaより)
ダイクストラ法（だいくすとらほう、英: Dijkstra's algorithm）はグラフ理論における
辺の重みが非負数の場合の単一始点最短経路問題を解くための最良優先探索によるアルゴリズムである。
辺の重みに負数を含む場合はベルマン-フォード法などが使える。辺の重みが全て同一の非負数の場合は
幅優先探索が速く、線形時間で最短路を計算可能である。
また、無向グラフで辺の重みが正整数の場合は、Thorupのアルゴリズムによって
線形時間での計算が可能であるが、実用性はあまり高くない。

ダイクストラ法は「ノード1」からの距離が短い順に各ノードを探索していき、特定のノードの最短距離を探索します。
感覚的に、候補を絞るという点でPython ナップザック問題を分枝限定法( branch and bound )で解くで使った分枝限定法と似た感覚もありました。

コードに関して不備や改良案等があればご教示頂けますと幸いです。

問題

以下のような経路があります。ノードが1~5まで5点あり、経路上の数字は必要時間です。
「ノード1」から「ノード5」に到達するための最短経路を求めよ。

解答

import math

route_list = [[0, 50, 80, 0, 0], [0, 0, 20, 15, 0 ], [0, 0, 0, 10, 15], [0, 0, 0, 0, 30], [0, 0, 0, 0, 0]] # 初期のノード間の距離のリスト

node_num = len(route_list) #ノードの数

unsearched_nodes = list(range(node_num)) # 未探索ノード
distance = [math.inf] * node_num # ノードごとの距離のリスト
previous_nodes = [-1] * node_num # 最短経路でそのノードのひとつ前に到達するノードのリスト
distance[0] = 0 # 初期のノードの距離は0とする

# @GDaigo さんのコメントより関数の追加 2017/03/18
def get_target_min_index(min_index, distance, unsearched_nodes):
    start = 0
    while True:
        index = distance.index(min_index, start)
        found = index in unsearched_nodes
        if found:
            return index
        else:
            start = index + 1

while(len(unsearched_nodes) != 0): #未探索ノードがなくなるまで繰り返す
    # まず未探索ノードのうちdistanceが最小のものを選択する
    posible_min_distance = math.inf # 最小のdistanceを見つけるための一時的なdistance。初期値は inf に設定。
    for node_index in unsearched_nodes: # 未探索のノードのループ
        if posible_min_distance > distance[node_index]: 
            posible_min_distance = distance[node_index] # より小さい値が見つかれば更新
    target_min_index = get_target_min_index(posible_min_distance, distance, unsearched_nodes) # 未探索ノードのうちで最小のindex番号を取得
    unsearched_nodes.remove(target_min_index) # ここで探索するので未探索リストから除去

    target_edge = route_list[target_min_index] # ターゲットになるノードからのびるエッジのリスト
    for index, route_dis in enumerate(target_edge):
        if route_dis != 0:
            if distance[index] > (distance[ target_min_index] + route_dis):
                distance[index] = distance[ target_min_index] + route_dis # 過去に設定されたdistanceよりも小さい場合はdistanceを更新
                previous_nodes[index] =  target_min_index #　ひとつ前に到達するノードのリストも更新

# 以下で結果の表示

print("-----経路-----")
previous_node = node_num - 1
while previous_node != -1:
    if previous_node !=0:
        print(str(previous_node + 1) + " <- ", end='')
    else:
        print(str(previous_node + 1))
    previous_node = previous_nodes[previous_node]

print("-----距離-----")
print(distance[node_num - 1])

結果

-----経路-----
5 <- 3 <- 2 <- 1
-----距離-----
85