ダイクストラ法による最短経路問題の解法

  • 作成: 日大生産工 MA 大前
  • 注意: 暫定版なので、正確さは保証しません。

最短経路問題

スタート位置とゴール位置があり、そこに向かうルートが複数あるものとします。この中で、一番短い距離でゴールに到達する道のりを見つけ出す問題を、最短経路問題と呼びます。ダイクストラ法とは、それを見つけ出す手法の一つです。ルート検索アプリなどを作成する場合に必要となる、大変重要な手法です。

用語の定義

  • 丸記号をノードと呼び、場所を表すものとする。
  • ノードとノードに結ばれた線(辺)をエッジと呼び、移動可能であることを意味する。
  • エッジの上に記載された数字は、移動距離である。
  • 最初にいるノードを始点と呼び、目的地となるノードを終点と呼ぶ。
  • 暫定距離とは、始点からそのノードへの、最短距離であることが保証されていない距離である。
  • 最短距離とは、始点からそのノードへの、最短距離であることが保証された距離である。
  • ここでいう距離とは、単なる「長さ」というよりも、 「その経路を移動したくない度合い」である。なので、長さでも、移動に必要となる金額でも、時間でも良い。
  • 隣接行列とは、2つのノード間の距離を格納した行列です。0行2列目が5であった場合、ノード$s_0$からノード$s_2$までの距離が5であることを意味します。この際、ノード$s_2$からノード$s_0$の距離も5になるので、2行0列目は5でなければなりません。したがって、隣接行列は対称行列となります。なお、経路を考えないノード同士の距離はすべて0とします。例えば、ノード$s_0$からノード$s_0$のように、同じ場所同士の経路は考えないので、対角成分はすべて0でなければなりません。また、$s_0$から$s_5$が通れないと考える場合、0行5列目と5行0列目は0なります。

準備

おまじないを書いておきます。

In [15]:
import numpy as np
import itertools as it
from graphviz import Graph
import random as rn
import time as ti

隣接行列の定義

まずは、どのような問題を扱うのかを明確にするため、隣接行列を定義します。対角成分を0にすること、対称行列になることを間違えないようにしましょう。

In [16]:
# 隣接行列の定義
g_matrix = np.array([
    [0, 1, 9, 2, 0, 0, 0, 12], # 0行目
    [1, 0, 0, 0, 5, 8, 0, 0], # 1行目
    [9, 0, 0, 0, 0, 2, 3, 10], # 2行目
    [2, 0, 0, 0, 0, 0, 5, 0], # 3行目
    [0, 5, 0, 0, 0, 1, 0, 0], # 4行目
    [0, 8, 2, 0, 1, 0, 0, 6], # 5行目
    [0, 0, 3, 5, 0, 0, 0, 2], # 6行目
    [12, 0, 10, 0, 0, 6, 2, 0]  # 7行目
])
er_flag = 0

# 対角成分チェック
for i in range(len(g_matrix)):
    if g_matrix[i, i] != 0:
        print("対角成分がすべて0になっていません。")
        er_flag = 1
        
# 対称性チェック
if np.sum(g_matrix == g_matrix.T) != len(g_matrix)**2:
    print("対称行列ではありません。")
    er_flag = 1

# 最終評価
if er_flag == 0:
    print("適切な隣接行列です。")
else:
    print("不適切な隣接行列です。作り直してください。")
適切な隣接行列です。

ノード名が数字だとわかりにくいので、下記のようにします。

  • 0 行 or 列目: ノード$s_0$
  • 1 行 or 列目: ノード$s_1$
  • ...
  • n 行 or 列目: ノード$s_n$

ここで、$n+1$はノードの最大数です(0スタートなので、1を足します)。また、

  • $s_0$: 始点(スタート位置)青実線のサークル
  • $s_n$: 終点(ゴール位置)赤破線のサークル

とします。一番最初のノードからスタートし、最後のノードに到達することを目的とすることを意味します。この条件のもと、隣接行列をグラフで表現します。可視化を行う関数は以下の通りです。

In [17]:
def graph_view(matrix):
    # ノード名生成
    node_name = []
    size = len(matrix)
    for i in range(size):
        node_name.append("s"+str(i))

    # エッジを生成するノードの組み合わせ
    comb_seed = np.arange(0, size)
    comb = list(it.combinations(comb_seed, 2))
    #print("エッジ生成ノードのリスト:", comb)

    # グラフ作成
    nG = Graph(format="pdf", engine="dot") # レイアウト: dot, fdp, osage, sfdp など
    nG.attr("node", shape="circle", color="black", size="100")
    for i in range(len(comb)):
        if matrix[comb[i][0], comb[i][1]] > 0: # 距離が0以上のエッジのみ描画
            nG.edge(node_name[comb[i][0]], node_name[comb[i][1]], label=str(int(g_matrix[comb[i][0], comb[i][1]])))
    nG.node(node_name[0], shape="circle", color="blue", penwidth="2") # 始点
    nG.node(node_name[-1], shape="circle", style="dashed", color="red", penwidth="2") # 終点

    # 描画
    nG.render("ngraphs")
    display(nG)

関数を使用するには、隣接行列を与えればokです。

In [18]:
graph_view(g_matrix)
s0 s0 s1 s1 s0--s1 1 s2 s2 s0--s2 9 s3 s3 s0--s3 2 s7 s7 s0--s7 12 s4 s4 s1--s4 5 s5 s5 s1--s5 8 s2--s7 10 s2--s5 2 s6 s6 s2--s6 3 s3--s6 5 s4--s5 1 s5--s7 6 s6--s7 2

ノード(円)が場所で、エッジ(線)が移動可能であること、エッジに付与された数字が移動距離を表します。

ダイクストラ法

続いて、上のグラフにおいて、ダイクストラ法により最短距離を求める方法を説明します。ダイクストラ法とは、始点に近いノードから最短距離を逐次求めていくアルゴリズムとなります。これは以下の手続きにより構成されます。用語がわからない場合は、本ページの冒頭を見直してください。

まずは、以下の表を用意します。$s_n$は終点ですから、ノードの数だけ列数があることになります。

ノード $s_0$ $s_1$ ... $s_n$
最短距離 xxx xxx ... xxx
暫定距離 xxx xxx ... xxx
経路情報 xxx xxx ... xxx

はじめに行う処理:

  • すべてのノードの暫定距離と最短距離を、無限大(大きな値)とする。
  • 次に、始点($s_0$)のノードの暫定距離を0とする。

その後の処理:

  • [手続き1] 暫定距離が最も小さいノードを $s'$ とし、$s'$ の暫定距離を $s'$ の最短距離として記入する。
  • [手続き2] $s'$ が終点 $s_n$ であれば、処理を終了する。そうでなければ手続き3に進む。
  • [手続き3] $s'$ と「直接的に接続されている、かつ、最短距離が無限大のノード」への暫定距離をすべて計算する(暫定距離とは、始点$s_0$ → $s'$ → 該当ノードへの距離)。
  • [手続き4] 計算された暫定距離が、すでに記入されている暫定距離よりも小さかった場合、そのノードの暫定距離を更新する。また、暫定距離が更新されたノードの経路情報に $s'$ と記入する。
  • [手続き5] $s'$ の暫定距離を無限大にし、手続き1に戻る。

経路を得る方法:

  • 経路情報より、$s_n$から$s_0$までの連なりを確認する。

これを関数化したものが以下となります。

In [19]:
# 隣接行列、printフラグを入力 → 最短経路を出力
def dijkstra(matrix, print_flag):
    t1 = ti.time()
    
    # ノード数とノード名取得
    node_name = []
    size = len(g_matrix)
    for i in range(size):
        node_name.append("s"+str(i))
    
    # はじめの処理
    m = 1000 # 無限大的な数字
    dist_temp = np.zeros(size) + m # 暫定距離
    dist_opt = np.zeros(size) + m # 最短距離
    dist_temp[0] = 0 # 始点のノードの暫定距離を0とする
    pre_node_info = np.zeros(size) - 1
    
    for t in range(size):
        if print_flag == 1:
            print("step: ", t)

        # 手続き1
        best_node = np.argmin(dist_temp) # 暫定距離が最も小さいものを s' に
        dist_opt[best_node] = dist_temp[best_node] # s' の暫定距離を s' の最短距離に
        if print_flag == 1:
            print("・", node_name[best_node], "が暫定距離の中で最も小さいノードでしたので、この値を最短距離として採択しました。")
            print("・(変更後)最短距離", dist_opt)

        # 手続き2
        if node_name[best_node] == node_name[-1]: # s' が 終点ならば終了
            if print_flag == 1:
                print("\n ### 最短経路が求まったので、処理を終了します ### ")
                print("・最短距離", dist_opt)
                print("・経路情報", pre_node_info)

            ### 出力 ###
            route =["s"+str(size-1)]
            pre_node_id = -1
            while(pre_node_id != 0): # 終点から始点まで逆順に辿る
                pre_node_id = int(pre_node_info[pre_node_id])
                route.append("s" + str(pre_node_id))
            tx = route[-1]
            for i in range(2, len(route)+1):
                tx = tx + " → " + route[-(i)]            
            print("・最短経路", tx, ",(距離 =", dist_opt[-1], ")")
            t2 = ti.time()
            elaps = t2-t1
            print("・所要時間", np.round(elaps, 5), "秒")
            break

        if t == size - 1: # 反復が最大の場合も終了(何かのミスにより、無限ループを回避するため)
            if print_flag == 1:
                print("\n ### 最大反復回数になったので、処理を終了します ###")
            break

        # 手続き3
        for i in range(size):
            if matrix[best_node][i] > 0: # 直接接続されているノードであり、
                if dist_opt[i] == m: # かつ、最短距離が無限大ならば、
                    # 手続き4
                    dist_check = dist_opt[best_node] + matrix[best_node, i] # 始点からs' への最短距離 + s'からs'と直接接続にあるノードへの距離
                    if dist_check < dist_temp[i]:
                        if print_flag == 1:
                            print("・", node_name[best_node], 
                                  "と直接接続されており、最短距離が記入されておらず、書き換え対象になったノードは",
                                  node_name[i], "でした。")
                        dist_temp[i] = dist_check # 暫定距離を更新
                        pre_node_info[i] = best_node # 経路情報に s' を記載
        if print_flag == 1:
            print("・(変更後)暫定距離", dist_temp)
            print("・(変更後)経路情報", pre_node_info, "\n")
        dist_temp[best_node] = m
        
    return [tx, elaps]

続いて、この関数を利用します。隣接行列とprint_flagを入力して使用します。計算過程を見たい場合はprint_flagを1に、見たくない場合は0にしてください。

In [20]:
res = dijkstra(g_matrix, print_flag = 1)
step:  0
・ s0 が暫定距離の中で最も小さいノードでしたので、この値を最短距離として採択しました。
・(変更後)最短距離 [   0. 1000. 1000. 1000. 1000. 1000. 1000. 1000.]
・ s0 と直接接続されており、最短距離が記入されておらず、書き換え対象になったノードは s1 でした。
・ s0 と直接接続されており、最短距離が記入されておらず、書き換え対象になったノードは s2 でした。
・ s0 と直接接続されており、最短距離が記入されておらず、書き換え対象になったノードは s3 でした。
・ s0 と直接接続されており、最短距離が記入されておらず、書き換え対象になったノードは s7 でした。
・(変更後)暫定距離 [   0.    1.    9.    2. 1000. 1000. 1000.   12.]
・(変更後)経路情報 [-1.  0.  0.  0. -1. -1. -1.  0.] 

step:  1
・ s1 が暫定距離の中で最も小さいノードでしたので、この値を最短距離として採択しました。
・(変更後)最短距離 [   0.    1. 1000. 1000. 1000. 1000. 1000. 1000.]
・ s1 と直接接続されており、最短距離が記入されておらず、書き換え対象になったノードは s4 でした。
・ s1 と直接接続されており、最短距離が記入されておらず、書き換え対象になったノードは s5 でした。
・(変更後)暫定距離 [1000.    1.    9.    2.    6.    9. 1000.   12.]
・(変更後)経路情報 [-1.  0.  0.  0.  1.  1. -1.  0.] 

step:  2
・ s3 が暫定距離の中で最も小さいノードでしたので、この値を最短距離として採択しました。
・(変更後)最短距離 [   0.    1. 1000.    2. 1000. 1000. 1000. 1000.]
・ s3 と直接接続されており、最短距離が記入されておらず、書き換え対象になったノードは s6 でした。
・(変更後)暫定距離 [1000. 1000.    9.    2.    6.    9.    7.   12.]
・(変更後)経路情報 [-1.  0.  0.  0.  1.  1.  3.  0.] 

step:  3
・ s4 が暫定距離の中で最も小さいノードでしたので、この値を最短距離として採択しました。
・(変更後)最短距離 [   0.    1. 1000.    2.    6. 1000. 1000. 1000.]
・ s4 と直接接続されており、最短距離が記入されておらず、書き換え対象になったノードは s5 でした。
・(変更後)暫定距離 [1000. 1000.    9. 1000.    6.    7.    7.   12.]
・(変更後)経路情報 [-1.  0.  0.  0.  1.  4.  3.  0.] 

step:  4
・ s5 が暫定距離の中で最も小さいノードでしたので、この値を最短距離として採択しました。
・(変更後)最短距離 [   0.    1. 1000.    2.    6.    7. 1000. 1000.]
・(変更後)暫定距離 [1000. 1000.    9. 1000. 1000.    7.    7.   12.]
・(変更後)経路情報 [-1.  0.  0.  0.  1.  4.  3.  0.] 

step:  5
・ s6 が暫定距離の中で最も小さいノードでしたので、この値を最短距離として採択しました。
・(変更後)最短距離 [   0.    1. 1000.    2.    6.    7.    7. 1000.]
・ s6 と直接接続されており、最短距離が記入されておらず、書き換え対象になったノードは s7 でした。
・(変更後)暫定距離 [1000. 1000.    9. 1000. 1000. 1000.    7.    9.]
・(変更後)経路情報 [-1.  0.  0.  0.  1.  4.  3.  6.] 

step:  6
・ s2 が暫定距離の中で最も小さいノードでしたので、この値を最短距離として採択しました。
・(変更後)最短距離 [   0.    1.    9.    2.    6.    7.    7. 1000.]
・(変更後)暫定距離 [1000. 1000.    9. 1000. 1000. 1000. 1000.    9.]
・(変更後)経路情報 [-1.  0.  0.  0.  1.  4.  3.  6.] 

step:  7
・ s7 が暫定距離の中で最も小さいノードでしたので、この値を最短距離として採択しました。
・(変更後)最短距離 [0. 1. 9. 2. 6. 7. 7. 9.]

 ### 最短経路が求まったので、処理を終了します ### 
・最短距離 [0. 1. 9. 2. 6. 7. 7. 9.]
・経路情報 [-1.  0.  0.  0.  1.  4.  3.  6.]
・最短経路 s0 → s3 → s6 → s7 ,(距離 = 9.0 )
・所要時間 0.02076 秒

最短距離は、始点から$s_0$〜$s_7$までの最短経路の距離を意味します。最短距離となる経路は、「最短経路」に記載しています。 また、とても高速に解けることも確認できます。

いくつかの事例(中規模: ノード数5〜20)

ランダムにひたすら隣接行列を作って、最短経路を出すプログラムです。いくつか単純すぎる問題もありますが、自動生成しているためですので、気にしないでください。

In [21]:
for i in range(10):
    print("\n ### Graph: ", i ," ###")
    rn.seed(i)
    # 隣接行列のランダム生成
    size = rn.randint(10, 20)
    g_matrix = np.zeros([size, size])
    comb_seed = np.arange(0, size)
    comb = list(it.combinations(comb_seed, 2))
    for i in range(len(comb)):
        sic = rn.random()
        if sic < 0.20: # 20%の確率で経路生成
            val = rn.randint(1, 10)
            g_matrix[comb[i][0], comb[i][1]] = val # 対称行列に
            g_matrix[comb[i][1], comb[i][0]] = val
        else:
            g_matrix[comb[i][0], comb[i][1]] = 0 # 対称行列に
            g_matrix[comb[i][1], comb[i][0]] = 0

    g_matrix[0, size-1], g_matrix[size-1, 0] = 10**2, 10**2 # 解なしを回避(無限大m=1000よりも小さく)

    graph_view(g_matrix)
    res = dijkstra(g_matrix, print_flag = 0)
 ### Graph:  0  ###
s0 s0 s15 s15 s0--s15 100 s1 s1 s11 s11 s1--s11 7 s11--s15 3 s14 s14 s11--s14 1 s2 s2 s5 s5 s2--s5 9 s7 s7 s2--s7 7 s6 s6 s5--s6 5 s8 s8 s5--s8 3 s12 s12 s7--s12 10 s13 s13 s7--s13 10 s3 s3 s3--s15 6 s3--s7 9 s4 s4 s3--s4 10 s9 s9 s3--s9 6 s4--s15 3 s8--s15 3 s8--s11 4 s8--s13 7 s13--s14 1 s10 s10 s10--s11 2
・最短経路 s0 → s15 ,(距離 = 100.0 )
・所要時間 0.00021 秒

 ### Graph:  1  ###
s0 s0 s3 s3 s0--s3 2 s8 s8 s0--s8 1 s11 s11 s0--s11 100 s10 s10 s3--s10 6 s9 s9 s3--s9 5 s8--s11 1 s1 s1 s1--s8 1 s7 s7 s1--s7 6 s1--s10 7 s7--s10 3 s7--s9 9 s4 s4 s4--s10 5 s5 s5 s5--s10 4
・最短経路 s0 → s8 → s11 ,(距離 = 2.0 )
・所要時間 0.00033 秒

 ### Graph:  2  ###
s0 s0 s1 s1 s0--s1 6 s9 s9 s0--s9 100 s2 s2 s2--s9 3 s3 s3 s5 s5 s3--s5 6 s6 s6 s3--s6 9 s7 s7 s6--s7 7 s4 s4 s4--s5 8
・最短経路 s0 → s9 ,(距離 = 100.0 )
・所要時間 0.00062 秒

 ### Graph:  3  ###
s0 s0 s2 s2 s0--s2 10 s9 s9 s0--s9 8 s12 s12 s0--s12 100 s2--s9 6 s10 s10 s2--s10 3 s1 s1 s4 s4 s1--s4 9 s6 s6 s1--s6 2 s7 s7 s1--s7 10 s8 s8 s1--s8 1 s4--s7 5 s4--s10 6 s6--s9 5 s6--s12 10 s6--s7 2 s7--s9 10 s8--s12 10 s5 s5 s5--s12 8
・最短経路 s0 → s9 → s6 → s12 ,(距離 = 23.0 )
・所要時間 0.00071 秒

 ### Graph:  4  ###
s0 s0 s4 s4 s0--s4 1 s12 s12 s0--s12 100 s6 s6 s4--s6 8 s1 s1 s1--s4 5 s1--s6 5 s9 s9 s6--s9 1 s2 s2 s2--s12 5 s3 s3 s11 s11 s3--s11 5 s5 s5 s5--s6 7 s10 s10 s5--s10 7 s9--s12 7 s9--s10 5 s7 s7 s7--s11 6 s7--s9 3
・最短経路 s0 → s4 → s6 → s9 → s12 ,(距離 = 17.0 )
・所要時間 0.00045 秒

 ### Graph:  5  ###
s0 s0 s10 s10 s0--s10 3 s11 s11 s0--s11 8 s14 s14 s0--s14 4 s15 s15 s0--s15 4 s17 s17 s0--s17 7 s18 s18 s0--s18 100 s10--s15 9 s14--s17 10 s1 s1 s2 s2 s1--s2 10 s4 s4 s1--s4 1 s2--s11 6 s2--s17 1 s2--s4 3 s4--s18 2 s7 s7 s4--s7 6 s9 s9 s4--s9 2 s13 s13 s4--s13 5 s3 s3 s3--s14 4 s7--s17 7 s13--s15 6 s5 s5 s5--s11 10 s6 s6 s6--s14 7 s6--s7 1 s6--s13 7 s16 s16 s6--s16 7 s8 s8 s8--s10 8 s12 s12 s8--s12 8 s12--s15 8
・最短経路 s0 → s17 → s2 → s4 → s18 ,(距離 = 13.0 )
・所要時間 0.00078 秒

 ### Graph:  6  ###
s0 s0 s4 s4 s0--s4 10 s15 s15 s0--s15 9 s18 s18 s0--s18 100 s1 s1 s3 s3 s1--s3 7 s5 s5 s1--s5 7 s8 s8 s1--s8 4 s11 s11 s1--s11 1 s3--s8 6 s7 s7 s3--s7 3 s17 s17 s3--s17 10 s5--s11 10 s6 s6 s5--s6 5 s10 s10 s5--s10 9 s13 s13 s5--s13 9 s8--s13 5 s12 s12 s8--s12 4 s11--s15 4 s2 s2 s2--s11 9 s2--s7 6 s14 s14 s2--s14 5 s16 s16 s2--s16 8 s7--s18 6 s7--s14 8 s7--s16 10 s14--s16 2 s16--s18 4 s6--s11 7 s6--s16 10 s10--s15 2 s10--s16 5 s13--s15 5 s12--s16 5 s9 s9 s9--s18 8 s9--s11 6 s9--s16 2
・最短経路 s0 → s15 → s10 → s16 → s18 ,(距離 = 20.0 )
・所要時間 0.0007 秒

 ### Graph:  7  ###
s0 s0 s3 s3 s0--s3 9 s4 s4 s0--s4 10 s5 s5 s0--s5 9 s7 s7 s0--s7 7 s8 s8 s0--s8 2 s10 s10 s0--s10 10 s11 s11 s0--s11 4 s14 s14 s0--s14 100 s3--s7 7 s3--s8 6 s12 s12 s3--s12 9 s9 s9 s3--s9 8 s4--s14 5 s5--s12 8 s8--s11 3 s8--s14 5 s8--s12 4 s13 s13 s8--s13 10 s1 s1 s1--s4 3 s1--s10 10 s1--s14 1 s6 s6 s1--s6 2 s6--s14 7 s2 s2 s2--s11 4 s2--s12 5 s9--s10 7 s9--s14 9
・最短経路 s0 → s8 → s14 ,(距離 = 7.0 )
・所要時間 0.00038 秒

 ### Graph:  8  ###
s0 s0 s3 s3 s0--s3 1 s4 s4 s0--s4 4 s8 s8 s0--s8 8 s11 s11 s0--s11 7 s12 s12 s0--s12 100 s3--s11 6 s10 s10 s3--s10 10 s4--s8 3 s8--s11 10 s9 s9 s8--s9 7 s1 s1 s1--s12 1 s1--s9 2 s2 s2 s2--s11 4 s2--s12 10 s2--s9 2 s10--s11 2 s6 s6 s6--s11 7 s6--s12 1 s7 s7 s6--s7 5 s7--s11 7
・最短経路 s0 → s11 → s6 → s12 ,(距離 = 15.0 )
・所要時間 0.00066 秒

 ### Graph:  9  ###
s0 s0 s3 s3 s0--s3 1 s11 s11 s0--s11 8 s14 s14 s0--s14 1 s15 s15 s0--s15 9 s16 s16 s0--s16 100 s3--s16 7 s8 s8 s3--s8 10 s10 s10 s3--s10 5 s13 s13 s3--s13 5 s4 s4 s3--s4 2 s7 s7 s3--s7 10 s11--s14 4 s11--s13 2 s14--s16 10 s1 s1 s1--s3 7 s1--s15 1 s2 s2 s2--s3 7 s5 s5 s2--s5 4 s2--s8 10 s9 s9 s2--s9 10 s2--s10 4 s2--s13 1 s5--s14 5 s5--s15 1 s5--s16 9 s5--s10 2 s6 s6 s5--s6 10 s12 s12 s8--s12 6 s9--s12 7 s10--s16 1 s10--s12 5 s4--s14 10 s4--s8 6 s7--s11 5 s7--s14 2 s7--s16 1 s7--s12 3 s12--s16 9
・最短経路 s0 → s14 → s7 → s16 ,(距離 = 4.0 )
・所要時間 0.00049 秒

いくつかの事例(大規模: ノード数30〜40)

ランダムにひたすら隣接行列を作って、最短経路を出すプログラムです。こちらも単純すぎる問題がいくつか含まれますが、気にせずお願いします。

In [23]:
for i in range(10):
    print("\n ### Graph: ", i ," ###")
    rn.seed(i)
    # 隣接行列のランダム生成
    size = rn.randint(30, 40)
    g_matrix = np.zeros([size, size])
    comb_seed = np.arange(0, size)
    comb = list(it.combinations(comb_seed, 2))
    for i in range(len(comb)):
        sic = rn.random()
        if sic < 0.10: # 10%の確率で経路生成
            val = rn.randint(1, 10)
            g_matrix[comb[i][0], comb[i][1]] = val # 対称行列に
            g_matrix[comb[i][1], comb[i][0]] = val
        else:
            g_matrix[comb[i][0], comb[i][1]] = 0 # 対称行列に
            g_matrix[comb[i][1], comb[i][0]] = 0

    g_matrix[0, size-1], g_matrix[size-1, 0] = 10**2, 10**2 # 解なしを回避(無限大m=1000よりも小さく)

    graph_view(g_matrix)
    res = dijkstra(g_matrix, print_flag = 0)
 ### Graph:  0  ###
s0 s0 s35 s35 s0--s35 100 s1 s1 s1--s35 3 s10 s10 s1--s10 10 s15 s15 s1--s15 6 s28 s28 s1--s28 7 s33 s33 s1--s33 5 s10--s33 3 s31 s31 s10--s31 6 s23 s23 s15--s23 1 s15--s31 9 s25 s25 s15--s25 5 s28--s33 7 s34 s34 s28--s34 1 s2 s2 s2--s28 5 s2--s23 10 s32 s32 s23--s32 2 s3 s3 s5 s5 s3--s5 10 s9 s9 s3--s9 2 s16 s16 s3--s16 1 s22 s22 s3--s22 1 s26 s26 s3--s26 2 s3--s31 2 s5--s26 3 s5--s31 1 s12 s12 s5--s12 10 s5--s25 8 s9--s35 4 s9--s15 9 s9--s28 1 s11 s11 s9--s11 2 s16--s22 3 s24 s24 s16--s24 8 s22--s26 8 s22--s34 5 s4 s4 s4--s28 1 s18 s18 s4--s18 7 s12--s26 3 s6 s6 s6--s12 3 s19 s19 s6--s19 9 s30 s30 s6--s30 8 s21 s21 s19--s21 3 s7 s7 s7--s31 10 s7--s18 10 s7--s12 4 s27 s27 s7--s27 3 s7--s32 5 s29 s29 s27--s29 5 s8 s8 s14 s14 s8--s14 3 s8--s29 6 s29--s30 5 s11--s31 2 s20 s20 s11--s20 3 s11--s21 1 s20--s22 6 s20--s26 3 s21--s30 8 s21--s32 5 s13 s13 s13--s31 10 s13--s27 8 s13--s29 8 s13--s24 3 s17 s17 s17--s23 2 s17--s34 4
・最短経路 s0 → s35 ,(距離 = 100.0 )
・所要時間 0.00024 秒

 ### Graph:  1  ###
s0 s0 s3 s3 s0--s3 2 s8 s8 s0--s8 1 s19 s19 s0--s19 9 s20 s20 s0--s20 7 s31 s31 s0--s31 100 s3--s20 9 s5 s5 s3--s5 6 s16 s16 s3--s16 4 s26 s26 s3--s26 1 s8--s19 5 s17 s17 s8--s17 9 s28 s28 s8--s28 2 s8--s26 5 s27 s27 s8--s27 1 s30 s30 s19--s30 4 s22 s22 s20--s22 10 s2 s2 s2--s3 9 s2--s17 4 s2--s28 9 s17--s20 7 s17--s26 2 s5--s19 2 s5--s26 1 s12 s12 s5--s12 10 s25 s25 s16--s25 2 s4 s4 s4--s28 3 s12--s16 3 s6 s6 s10 s10 s6--s10 4 s23 s23 s6--s23 4 s6--s30 7 s10--s26 8 s10--s27 10 s11 s11 s10--s11 6 s10--s25 5 s29 s29 s23--s29 8 s7 s7 s15 s15 s7--s15 3 s9 s9 s9--s27 5 s11--s27 1 s11--s22 4 s24 s24 s22--s24 10 s13 s13 s13--s23 8 s21 s21 s13--s21 4 s14 s14 s14--s17 6 s14--s26 9 s14--s15 7 s14--s25 8
・最短経路 s0 → s31 ,(距離 = 100.0 )
・所要時間 0.00129 秒

 ### Graph:  2  ###
s0 s0 s1 s1 s0--s1 6 s18 s18 s0--s18 1 s29 s29 s0--s29 100 s18--s29 8 s2 s2 s26 s26 s2--s26 4 s27 s27 s26--s27 6 s3 s3 s3--s18 2 s3--s29 6 s3--s26 10 s4 s4 s3--s4 10 s15 s15 s3--s15 6 s20 s20 s3--s20 1 s3--s27 4 s13 s13 s4--s13 5 s15--s29 9 s25 s25 s15--s25 8 s5 s5 s9 s9 s5--s9 9 s19 s19 s5--s19 4 s22 s22 s9--s22 6 s6 s6 s6--s15 8 s7 s7 s6--s7 1 s11 s11 s6--s11 2 s12 s12 s6--s12 3 s24 s24 s6--s24 10 s6--s25 7 s7--s20 8 s7--s27 8 s7--s9 2 s7--s19 8 s7--s24 1 s14 s14 s7--s14 7 s11--s22 5 s23 s23 s12--s23 8 s28 s28 s12--s28 7 s25--s29 7 s25--s27 6 s14--s29 2 s14--s19 1 s14--s23 10 s8 s8 s8--s15 6 s8--s19 8 s10 s10 s10--s12 5 s23--s26 5 s16 s16 s16--s18 1 s16--s28 6 s17 s17 s17--s23 4
・最短経路 s0 → s18 → s29 ,(距離 = 9.0 )
・所要時間 0.00045 秒

 ### Graph:  3  ###
s0 s0 s20 s20 s0--s20 2 s23 s23 s0--s23 1 s32 s32 s0--s32 100 s22 s22 s20--s22 9 s30 s30 s20--s30 8 s1 s1 s1--s32 8 s5 s5 s1--s5 8 s31 s31 s5--s31 10 s2 s2 s3 s3 s2--s3 2 s9 s9 s2--s9 10 s17 s17 s2--s17 1 s18 s18 s2--s18 10 s3--s32 6 s9--s20 7 s9--s23 6 s17--s18 6 s19 s19 s18--s19 5 s4 s4 s16 s16 s4--s16 10 s25 s25 s4--s25 10 s16--s20 6 s16--s23 10 s16--s17 8 s29 s29 s16--s29 7 s28 s28 s25--s28 9 s6 s6 s6--s18 10 s6--s22 9 s27 s27 s6--s27 2 s27--s29 6 s27--s28 9 s7 s7 s7--s32 1 s24 s24 s7--s24 10 s26 s26 s7--s26 5 s7--s30 6 s24--s27 4 s24--s29 4 s26--s31 10 s26--s30 1 s8 s8 s8--s16 7 s8--s27 8 s8--s26 3 s10 s10 s8--s10 1 s11 s11 s8--s11 1 s13 s13 s8--s13 9 s10--s17 3 s10--s27 2 s11--s18 6 s12 s12 s11--s12 10 s21 s21 s11--s21 3 s21--s23 2 s14 s14 s14--s23 2 s15 s15 s15--s30 2 s19--s26 3
・最短経路 s0 → s23 → s21 → s11 → s8 → s26 → s7 → s32 ,(距離 = 16.0 )
・所要時間 0.00112 秒

 ### Graph:  4  ###
s0 s0 s4 s4 s0--s4 1 s25 s25 s0--s25 10 s32 s32 s0--s32 100 s10 s10 s4--s10 6 s19 s19 s4--s19 4 s1 s1 s1--s4 5 s15 s15 s1--s15 1 s23 s23 s1--s23 4 s26 s26 s15--s26 4 s2 s2 s2--s23 10 s2--s10 6 s16 s16 s2--s16 5 s30 s30 s2--s30 1 s28 s28 s16--s28 1 s3 s3 s3--s32 5 s11 s11 s3--s11 3 s18 s18 s3--s18 9 s11--s25 6 s24 s24 s11--s24 9 s11--s28 5 s17 s17 s11--s17 3 s27 s27 s18--s27 9 s22 s22 s19--s22 7 s5 s5 s5--s32 4 s6 s6 s6--s32 10 s6--s19 2 s14 s14 s6--s14 10 s6--s22 6 s6--s24 9 s14--s19 2 s22--s27 3 s24--s25 1 s29 s29 s24--s29 5 s7 s7 s7--s28 3 s7--s29 5 s29--s32 2 s8 s8 s8--s17 1 s17--s30 3 s17--s19 10 s17--s29 1 s17--s26 4 s9 s9 s9--s10 3 s9--s19 3 s9--s27 6 s12 s12 s12--s14 3 s12--s24 1 s12--s27 5 s13 s13 s12--s13 4 s12--s26 5 s13--s32 1 s13--s16 6 s13--s24 3 s26--s30 3 s20 s20 s21 s21 s20--s21 5 s21--s26 10
・最短経路 s0 → s4 → s19 → s14 → s12 → s13 → s32 ,(距離 = 15.0 )
・所要時間 0.00076 秒

 ### Graph:  5  ###
s0 s0 s10 s10 s0--s10 3 s16 s16 s0--s16 4 s22 s22 s0--s22 10 s25 s25 s0--s25 1 s38 s38 s0--s38 100 s13 s13 s10--s13 2 s21 s21 s10--s21 2 s27 s27 s10--s27 5 s17 s17 s16--s17 3 s16--s21 9 s16--s27 5 s29 s29 s22--s29 4 s35 s35 s22--s35 1 s31 s31 s22--s31 9 s34 s34 s25--s34 7 s1 s1 s6 s6 s1--s6 5 s11 s11 s1--s11 6 s1--s17 1 s6--s22 1 s20 s20 s11--s20 2 s19 s19 s11--s19 1 s11--s35 8 s30 s30 s17--s30 6 s33 s33 s17--s33 5 s2 s2 s2--s13 6 s2--s21 10 s2--s29 1 s28 s28 s13--s28 1 s32 s32 s13--s32 1 s13--s20 7 s21--s30 8 s21--s35 3 s37 s37 s29--s37 4 s29--s34 8 s3 s3 s5 s5 s3--s5 7 s24 s24 s3--s24 5 s3--s28 6 s9 s9 s5--s9 3 s5--s27 4 s5--s30 7 s24--s32 2 s24--s31 4 s28--s32 6 s28--s34 2 s4 s4 s8 s8 s4--s8 9 s4--s32 7 s8--s16 5 s8--s37 7 s9--s22 2 s9--s24 7 s9--s28 2 s9--s20 4 s27--s29 7 s27--s28 3 s27--s32 10 s7 s7 s7--s25 8 s7--s11 5 s7--s21 9 s20--s30 1 s23 s23 s20--s23 3 s20--s31 10 s19--s25 10 s19--s21 9 s12 s12 s12--s30 1 s14 s14 s14--s27 8 s14--s19 4 s14--s35 1 s15 s15 s15--s16 9 s15--s22 8 s15--s27 7 s15--s23 4 s23--s38 2 s23--s31 3 s18 s18 s18--s27 3 s18--s31 9 s18--s34 1 s31--s33 3 s36 s36 s36--s37 10
・最短経路 s0 → s10 → s13 → s20 → s23 → s38 ,(距離 = 17.0 )
・所要時間 0.00363 秒

 ### Graph:  6  ###
s0 s0 s4 s4 s0--s4 10 s23 s23 s0--s23 7 s26 s26 s0--s26 4 s29 s29 s0--s29 1 s38 s38 s0--s38 100 s8 s8 s4--s8 10 s14 s14 s4--s14 3 s27 s27 s4--s27 9 s33 s33 s4--s33 2 s34 s34 s23--s34 5 s30 s30 s29--s30 1 s1 s1 s1--s4 6 s35 s35 s1--s35 8 s2 s2 s12 s12 s2--s12 5 s16 s16 s2--s16 9 s24 s24 s16--s24 5 s18 s18 s16--s18 5 s3 s3 s3--s35 8 s11 s11 s3--s11 8 s3--s24 9 s3--s34 2 s11--s35 9 s11--s24 2 s20 s20 s11--s20 1 s19 s19 s11--s19 1 s34--s38 2 s8--s26 8 s9 s9 s8--s9 1 s31 s31 s8--s31 3 s14--s38 2 s14--s16 10 s21 s21 s14--s21 9 s27--s31 7 s27--s30 9 s36 s36 s27--s36 10 s5 s5 s5--s38 9 s5--s33 10 s7 s7 s5--s7 4 s10 s10 s5--s10 2 s7--s26 10 s7--s38 6 s10--s26 2 s10--s18 10 s17 s17 s10--s17 3 s6 s6 s6--s23 9 s6--s29 2 s6--s18 1 s6--s20 9 s37 s37 s6--s37 1 s20--s33 1 s32 s32 s20--s32 4 s9--s23 5 s9--s35 9 s17--s30 4 s19--s34 4 s19--s20 2 s19--s32 10 s13 s13 s13--s29 6 s15 s15 s15--s26 2 s15--s16 7 s15--s20 5 s15--s32 1 s32--s35 6 s30--s31 3 s22 s22 s22--s23 4 s22--s30 2 s25 s25 s25--s33 6 s28 s28 s25--s28 8 s28--s31 9
・最短経路 s0 → s23 → s34 → s38 ,(距離 = 14.0 )
・所要時間 0.00137 秒

 ### Graph:  7  ###
s0 s0 s3 s3 s0--s3 9 s4 s4 s0--s4 10 s5 s5 s0--s5 9 s7 s7 s0--s7 7 s8 s8 s0--s8 2 s10 s10 s0--s10 10 s18 s18 s0--s18 3 s29 s29 s0--s29 1 s34 s34 s0--s34 100 s30 s30 s3--s30 4 s11 s11 s4--s11 2 s25 s25 s4--s25 5 s5--s34 2 s24 s24 s5--s24 2 s7--s29 8 s8--s11 9 s16 s16 s8--s16 4 s27 s27 s10--s27 5 s10--s16 9 s15 s15 s10--s15 6 s28 s28 s10--s28 3 s18--s29 4 s20 s20 s18--s20 3 s29--s34 4 s1 s1 s1--s7 5 s1--s18 2 s31 s31 s1--s31 5 s2 s2 s6 s6 s2--s6 8 s2--s27 3 s33 s33 s2--s33 7 s32 s32 s6--s32 2 s27--s32 7 s11--s24 2 s11--s16 1 s21 s21 s11--s21 2 s23 s23 s11--s23 4 s24--s27 9 s16--s25 1 s16--s20 10 s9 s9 s9--s30 8 s17 s17 s9--s17 4 s17--s18 2 s17--s25 5 s17--s32 5 s17--s23 8 s15--s16 9 s21--s34 7 s21--s32 5 s23--s27 7 s23--s32 7 s12 s12 s12--s23 1 s13 s13 s12--s13 4 s13--s24 5 s13--s23 3 s26 s26 s13--s26 7 s26--s33 6 s14 s14 s14--s24 5 s14--s28 5 s14--s23 7 s20--s31 1 s19 s19 s19--s25 8 s19--s26 9 s22 s22 s22--s29 5 s22--s28 2
・最短経路 s0 → s29 → s34 ,(距離 = 5.0 )
・所要時間 0.00047 秒

 ### Graph:  8  ###
s0 s0 s4 s4 s0--s4 3 s14 s14 s0--s14 4 s22 s22 s0--s22 2 s26 s26 s0--s26 4 s32 s32 s0--s32 100 s10 s10 s4--s10 6 s25 s25 s4--s25 6 s14--s22 4 s24 s24 s14--s24 1 s15 s15 s14--s15 5 s29 s29 s14--s29 4 s28 s28 s22--s28 8 s1 s1 s1--s14 6 s2 s2 s1--s2 1 s23 s23 s1--s23 9 s30 s30 s1--s30 5 s2--s22 2 s12 s12 s2--s12 7 s23--s25 9 s12--s28 8 s21 s21 s12--s21 4 s3 s3 s3--s32 1 s3--s12 10 s13 s13 s3--s13 10 s3--s28 8 s10--s26 6 s10--s32 3 s10--s30 3 s25--s32 7 s6 s6 s6--s30 3 s7 s7 s6--s7 5 s7--s23 3 s7--s13 8 s7--s21 1 s21--s28 6 s8 s8 s19 s19 s8--s19 4 s20 s20 s8--s20 3 s8--s24 3 s9 s9 s17 s17 s9--s17 8 s17--s22 6 s17--s32 9 s15--s26 6 s15--s32 2 s15--s17 2 s15--s29 7 s16 s16 s16--s20 5
・最短経路 s0 → s14 → s15 → s32 ,(距離 = 11.0 )
・所要時間 0.0009 秒

 ### Graph:  9  ###
s0 s0 s17 s17 s0--s17 3 s29 s29 s0--s29 5 s33 s33 s0--s33 1 s35 s35 s0--s35 7 s36 s36 s0--s36 100 s23 s23 s17--s23 7 s31 s31 s29--s31 4 s1 s1 s1--s36 6 s7 s7 s1--s7 10 s18 s18 s1--s18 4 s20 s20 s1--s20 10 s24 s24 s1--s24 5 s21 s21 s7--s21 5 s13 s13 s7--s13 6 s20--s29 3 s20--s23 2 s20--s31 2 s24--s33 7 s2 s2 s2--s17 2 s2--s24 9 s2--s21 5 s21--s36 10 s32 s32 s21--s32 5 s3 s3 s8 s8 s3--s8 3 s3--s13 8 s22 s22 s3--s22 9 s8--s17 9 s25 s25 s8--s25 9 s30 s30 s8--s30 6 s8--s32 7 s13--s29 4 s13--s35 7 s13--s22 7 s13--s30 4 s13--s31 8 s4 s4 s4--s21 10 s16 s16 s4--s16 9 s27 s27 s4--s27 10 s16--s17 8 s27--s29 4 s27--s35 1 s5 s5 s5--s7 4 s5--s18 4 s5--s20 1 s5--s24 2 s5--s27 8 s6 s6 s5--s6 10 s14 s14 s5--s14 10 s15 s15 s5--s15 1 s19 s19 s5--s19 3 s6--s24 2 s34 s34 s6--s34 3 s14--s16 10 s14--s34 6 s15--s33 5 s15--s22 2 s15--s27 5 s15--s19 7 s26 s26 s15--s26 7 s19--s22 6 s19--s25 10 s19--s30 7 s34--s35 4 s30--s36 6 s30--s32 9 s9 s9 s9--s20 1 s9--s26 5 s26--s29 8 s10 s10 s10--s33 3 s10--s35 6 s11 s11 s10--s11 3 s10--s23 9 s28 s28 s10--s28 7 s11--s20 10 s11--s16 9 s11--s27 7 s23--s35 4 s23--s24 10 s28--s33 9 s12 s12 s12--s20 7
・最短経路 s0 → s33 → s24 → s1 → s36 ,(距離 = 19.0 )
・所要時間 0.00157 秒