グラフ理論とダイクストラ法

グラフ理論とダイクストラ法 ○折井 悟 Graph theory and Dijkstra's algorithm Satoru Orii EPS corp. SA1-1

要旨：グラフ理論の基本的な知識,プログラム上での グラフの取り扱い,グラフを利用する典型問題である 最短経路問題とその解法を紹介する キーワード：Graph theory Dijkstra's algorithm 2

グラフとは • グラフ理論で扱う「グラフ」は,「頂点(Node)」と、2つの頂点を結ぶ「辺 (Edge)」の集合 • 頂点の集合をV,辺の集合をEとしてG=(V,E)と表記される 1 3 0 5 2 4 6

重み付きグラフ • 各辺に重み（≒長さ,コスト）の情報があるグラフ • 重みは0や負の数を考えることもできる 2 1 1 0 3 3 5 0 3 2 2 4 1 -1 6

有向グラフ • 各辺が向きを持つグラフ • 無向グラフでは辺e(u,v)と辺e(v,u)に区別はないが,有向グラフでは区 別する 1 3 0 5 2 4 6

その他用語 • • • • 多重辺：2頂点を結ぶ同一の辺が複数ある場合 ループ：ある頂点から出て同じ頂点に帰ってくる辺 単純グラフ：多重辺,ループがないグラフ path（道、路、経路）：グラフ上のある2頂点について,順に辿っていくと その2頂点を結ぶような辺と頂点の集合 • 連結：グラフ上の任意の2頂点についてpathが存在する状態 今回は単純連結グラフについて扱う

グラフのプログラム上での表現 • 隣接行列 頂点数をVとして,サイズV×Vの2次元配列でグラフを表現する graph[i][j]には辺e(i,j)の有無,重みなどの情報を格納する O(1)で辺の有無や重みを取得できるが,Vが大きくなるとメモリ消費が激しい • 隣接リスト 各頂点について,隣接する頂点（および辺の重み）をリストで管理する 隣接行列に比べメモリ消費が小さいが,辺の有無や重みの取得に最悪O(V) かかる

グラフのプログラム上での表現 • 先程のグラフを隣接行列,隣接リストで表現してみる ・隣接行列 [[0,1,1,0,0,0,0], [1,0,0,1,0,0,0], [1,0,0,0,1,0,0], [0,1,0,0,1,1,0], [0,0,1,1,0,1,0], [0,0,0,1,1,0,1], [0,0,0,0,0,1,0]] ・隣接リスト [[1,2], [0,3], [0,4], [1,4,5], [2,3,5], [3,4,6], [5]] 1 3 0 5 2 4 6

最短経路問題 • 重み付きグラフの2つの頂点を結ぶ経路(path)のうち,重みの合計が最 小になるものを求める問題 • 単一始点最短経路問題：ある1つの頂点から他のすべての頂点への 最短経路を求める • 全点対最短経路問題：グラフ内の2頂点の組み合わせすべてについて 最短経路を求める • 今回は単一始点最短経路問題を解くアルゴリズムの1つであるダイク ストラ法について紹介する

ダイクストラ法 0 5 ∞ 2 4 ∞ 6 10 ∞ ∞ 3 0.始点から他の頂点への距離を∞, 1 2 始点から始点への距離を0とする 1.始点からの距離が最も小さく,まだその点までの 最短距離が確定していない頂点（=「使用済み」でない点）を1つ選び(頂点vとする)、 頂点vまでの距離を最短距離として確定させる.頂点vを使用済みとする 2.頂点vと隣接していて,使用済みでない頂点すべてについて, （vと隣接する頂点をu0,u1…ui…u nとする） 「uiまでの距離」=min(「uiまでの距離」,「vまでの最短距離+辺e(v,ui)の重み」) で更新する 3.すべての頂点が使用済みなら終了.でなければ1へ戻る ∞ 5 ∞ 9

ダイクストラ法 0 5 ∞ 2 4 ∞ 6 10 ∞ ∞ 3 0.始点から他の頂点への距離を∞, 1 2 始点から始点への距離を0とする 1.始点からの距離が最も小さく,まだその点までの 最短距離が確定していない頂点（=「使用済み」でない点）を1つ選び(頂点vとする)、 頂点vまでの距離を最短距離として確定させる.頂点vを使用済みとする 2.頂点vと隣接していて,使用済みでない頂点すべてについて, （vと隣接する頂点をu0,u1…ui…u nとする） 「uiまでの距離」=min(「uiまでの距離」,「vまでの最短距離+辺e(v,ui)の重み」) で更新する 3.すべての頂点が使用済みなら終了.でなければ1へ戻る ∞ 5 ∞ 9

ダイクストラ法 0 5 5 2 4 2 6 10 ∞ ∞ 3 0.始点から他の頂点への距離を∞, 1 2 始点から始点への距離を0とする 1.始点からの距離が最も小さく,まだその点までの 最短距離が確定していない頂点（=「使用済み」でない点）を1つ選び(頂点vとする)、 頂点vまでの距離を最短距離として確定させる.頂点vを使用済みとする 2.頂点vと隣接していて,使用済みでない頂点すべてについて, （vと隣接する頂点をu0,u1…ui…u nとする） 「uiまでの距離」=min(「uiまでの距離」,「vまでの最短距離+辺e(v,ui)の重み」) で更新する 3.すべての頂点が使用済みなら終了.でなければ1へ戻る ∞ 5 ∞ 9

ダイクストラ法 0 5 5 2 4 2 6 10 ∞ ∞ 3 0.始点から他の頂点への距離を∞, 1 2 始点から始点への距離を0とする 1.始点からの距離が最も小さく,まだその点までの 最短距離が確定していない頂点（=「使用済み」でない点）を1つ選び(頂点vとする)、 頂点vまでの距離を最短距離として確定させる.頂点vを使用済みとする 2.頂点vと隣接していて,使用済みでない頂点すべてについて, （vと隣接する頂点をu0,u1…ui…u nとする） 「uiまでの距離」=min(「uiまでの距離」,「vまでの最短距離+辺e(v,ui)の重み」) で更新する 3.すべての頂点が使用済みなら終了.でなければ1へ戻る ∞ 5 ∞ 9

ダイクストラ法 0 5 2 4 5<2+4 2 6 10 12 ∞ 3 0.始点から他の頂点への距離を∞, 1 2 始点から始点への距離を0とする 1.始点からの距離が最も小さく,まだその点までの 最短距離が確定していない頂点（=「使用済み」でない点）を1つ選び(頂点vとする)、 頂点vまでの距離を最短距離として確定させる.頂点vを使用済みとする 2.頂点vと隣接していて,使用済みでない頂点すべてについて, （vと隣接する頂点をu0,u1…ui…u nとする） 「uiまでの距離」=min(「uiまでの距離」,「vまでの最短距離+辺e(v,ui)の重み」) で更新する 3.すべての頂点が使用済みなら終了.でなければ1へ戻る 8 5 ∞ 9

ダイクストラ法 0 5 5 2 4 2 6 10 12 ∞ 3 0.始点から他の頂点への距離を∞, 1 2 始点から始点への距離を0とする 1.始点からの距離が最も小さく,まだその点までの 最短距離が確定していない頂点（=「使用済み」でない点）を1つ選び(頂点vとする)、 頂点vまでの距離を最短距離として確定させる.頂点vを使用済みとする 2.頂点vと隣接していて,使用済みでない頂点すべてについて, （vと隣接する頂点をu0,u1…ui…u nとする） 「uiまでの距離」=min(「uiまでの距離」,「vまでの最短距離+辺e(v,ui)の重み」) で更新する 3.すべての頂点が使用済みなら終了.でなければ1へ戻る 8 5 ∞ 9

ダイクストラ法 0 5 5 2 4 2 6 10 12 ∞ 3 0.始点から他の頂点への距離を∞, 1 2 始点から始点への距離を0とする 1.始点からの距離が最も小さく,まだその点までの 最短距離が確定していない頂点（=「使用済み」でない点）を1つ選び(頂点vとする)、 頂点vまでの距離を最短距離として確定させる.頂点vを使用済みとする 2.頂点vと隣接していて,使用済みでない頂点すべてについて, （vと隣接する頂点をu0,u1…ui…u nとする） 「uiまでの距離」=min(「uiまでの距離」,「vまでの最短距離+辺e(v,ui)の重み」) で更新する 3.すべての頂点が使用済みなら終了.でなければ1へ戻る 7 5 ∞ 9

ダイクストラ法 0 5 5 2 4 2 6 10 12 ∞ 3 0.始点から他の頂点への距離を∞, 1 2 始点から始点への距離を0とする 1.始点からの距離が最も小さく,まだその点までの 最短距離が確定していない頂点（=「使用済み」でない点）を1つ選び(頂点vとする)、 頂点vまでの距離を最短距離として確定させる.頂点vを使用済みとする 2.頂点vと隣接していて,使用済みでない頂点すべてについて, （vと隣接する頂点をu0,u1…ui…u nとする） 「uiまでの距離」=min(「uiまでの距離」,「vまでの最短距離+辺e(v,ui)の重み」) で更新する 3.すべての頂点が使用済みなら終了.でなければ1へ戻る 7 5 ∞ 9

ダイクストラ法 0 5 5 2 4 2 6 10 12 ∞ 3 0.始点から他の頂点への距離を∞, 1 2 始点から始点への距離を0とする 1.始点からの距離が最も小さく,まだその点までの 最短距離が確定していない頂点（=「使用済み」でない点）を1つ選び(頂点vとする)、 頂点vまでの距離を最短距離として確定させる.頂点vを使用済みとする 2.頂点vと隣接していて,使用済みでない頂点すべてについて, （vと隣接する頂点をu0,u1…ui…u nとする） 「uiまでの距離」=min(「uiまでの距離」,「vまでの最短距離+辺e(v,ui)の重み」)で更新する 3.すべての頂点が使用済みなら終了.でなければ1へ戻る 7 5 8 9

ダイクストラ法 0 5 5 2 4 2 6 10 12 ∞ 3 0.始点から他の頂点への距離を∞, 1 2 始点から始点への距離を0とする 1.始点からの距離が最も小さく,まだその点までの 最短距離が確定していない頂点（=「使用済み」でない点）を1つ選び(頂点vとする)、 頂点vまでの距離を最短距離として確定させる.頂点vを使用済みとする 2.頂点vと隣接していて,使用済みでない頂点すべてについて, （vと隣接する頂点をu0,u1…ui…u nとする） 「uiまでの距離」=min(「uiまでの距離」,「vまでの最短距離+辺e(v,ui)の重み」) で更新する 3.すべての頂点が使用済みなら終了.でなければ1へ戻る 7 5 8 9

ダイクストラ法 0 5 5 2 4 2 6 10 11 3 0.始点から他の頂点への距離を∞, 1 2 始点から始点への距離を0とする 1.始点からの距離が最も小さく,まだその点までの 最短距離が確定していない頂点（=「使用済み」でない点）を1つ選び(頂点vとする)、 頂点vまでの距離を最短距離として確定させる.頂点vを使用済みとする 2.頂点vと隣接していて,使用済みでない頂点すべてについて, （vと隣接する頂点をu0,u1…ui…u nとする） 「uiまでの距離」=min(「uiまでの距離」,「vまでの最短距離+辺e(v,ui)の重み」) で更新する 3.すべての頂点が使用済みなら終了.でなければ1へ戻る 7 5 8 17 9

ダイクストラ法 0 5 5 2 4 2 6 10 11 3 0.始点から他の頂点への距離を∞, 1 2 始点から始点への距離を0とする 1.始点からの距離が最も小さく,まだその点までの 最短距離が確定していない頂点（=「使用済み」でない点）を1つ選び(頂点vとする)、 頂点vまでの距離を最短距離として確定させる.頂点vを使用済みとする 2.頂点vと隣接していて,使用済みでない頂点すべてについて, （vと隣接する頂点をu0,u1…ui…u nとする） 「uiまでの距離」=min(「uiまでの距離」,「vまでの最短距離+辺e(v,ui)の重み」) で更新する 3.すべての頂点が使用済みなら終了.でなければ1へ戻る 7 5 8 17 9

ダイクストラ法 0 5 5 2 4 2 6 10 11 3 0.始点から他の頂点への距離を∞, 1 2 始点から始点への距離を0とする 1.始点からの距離が最も小さく,まだその点までの 最短距離が確定していない頂点（=「使用済み」でない点）を1つ選び(頂点vとする)、 頂点vまでの距離を最短距離として確定させる.頂点vを使用済みとする 2.頂点vと隣接していて,使用済みでない頂点すべてについて, （vと隣接する頂点をu0,u1…ui…u nとする） 「uiまでの距離」=min(「uiまでの距離」,「vまでの最短距離+辺e(v,ui)の重み」) で更新する 3.すべての頂点が使用済みなら終了.でなければ1へ戻る 7 5 8 16 9

ダイクストラ法 0 5 5 2 4 2 6 10 11 3 0.始点から他の頂点への距離を∞, 1 2 始点から始点への距離を0とする 1.始点からの距離が最も小さく,まだその点までの 最短距離が確定していない頂点（=「使用済み」でない点）を1つ選び(頂点vとする)、 頂点vまでの距離を最短距離として確定させる.頂点vを使用済みとする 2.頂点vと隣接していて,使用済みでない頂点すべてについて, （vと隣接する頂点をu0,u1…ui…u nとする） 「uiまでの距離」=min(「uiまでの距離」,「vまでの最短距離+辺e(v,ui)の重み」)で更新する 3.すべての頂点が使用済みなら終了.でなければ1へ戻る 7 5 8 16 9

ダイクストラ法 0 5 5 2 4 2 6 10 11 3 0.始点から他の頂点への距離を∞, 1 2 始点から始点への距離を0とする 1.始点からの距離が最も小さく,まだその点までの 最短距離が確定していない頂点（=「使用済み」でない点）を1つ選び(頂点vとする)、 頂点vまでの距離を最短距離として確定させる.頂点vを使用済みとする 2.頂点vと隣接していて,使用済みでない頂点すべてについて, （vと隣接する頂点をu0,u1…ui…u nとする） 「uiまでの距離」=min(「uiまでの距離」,「vまでの最短距離+辺e(v,ui)の重み」) で更新する 3.すべての頂点が使用済みなら終了.でなければ1へ戻る 7 5 8 16 9

ダイクストラ法-Pythonでの実装 #入力は右に示したような形のデータを想定 INF = float('inf') V, E = map(int,input().split()) # Vは頂点数、Eは辺数 cost = [[INF] * V for _ in range(V)] # cost[u][v]は辺e=(u,v)のコスト(存在しない場所はINF) for _ in range(E): s, t, c = map(int,input().split()) cost[s][t] = c cost[t][s] = c d = [INF for _ in range(V)] # 最短距離 used = [False] * V # すでに使われたかのフラグ 入力 7 10 012 025 124 136 1 4 10 232 351 453 465 569

ダイクストラ法-Pythonでの実装 def dijkstra(s): d[s] = 0 while True: v = -1 # まだ使われていない頂点のうち距離が最小のものを探す for u in range(V): if not used[u] and (v == -1 or d[u] < d[v]): v=u if v == -1: break used[v] = True for u in range(V): d[u] = min(d[u], d[v] + cost[v][u]) dijkstra(0) print(d) #[0, 2, 5, 7, 11, 8, 16]