최단 경로 문제는 다이크스트라법을 사용하여 해결합니다.

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

Dijkstra 방법은 "노드 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