第4章 空間解析 2.ネットワーク分析 (1) 最短経路検索

Presentation on theme: "第4章 空間解析 2.ネットワーク分析 (1) 最短経路検索"— Presentation transcript:

1 第4章 空間解析 2.ネットワーク分析 (1) 最短経路検索
第4章　空間解析 2.ネットワーク分析 (1) 最短経路検索 久保田光一

2 最短経路探索 池袋 御茶ノ水 秋葉原 新宿 東京 ・この図はJR山手線と，総武線，東京メトロ丸ノ内線の図である．
・この図で池袋駅から東京駅へ行く経路を考える． ・緑は山手線，赤は丸の内線，黄は総武線を表す．（簡単のため，中央線は除いてある．） 秋葉原 新宿 東京

3 最短経路探索 出発地の駅から，目的地の駅まで移動する． 自動車で目的地まで移動する． 所要時間が一番短い経路 料金が一番安い経路
距離が一番短い経路 高速料金などの料金が一番安い経路 ・最短経路探索は，鉄道網や道路網を利用して，ある地点から別の地点に移動するのに複数の選択肢がある場合，ある種の基準で一番良いものを見出すことである．探索の基準としては，距離の短さ，所要時間の短さ，料金の安さなどがある． ・自動車による経路探索は，カーナビなどで広く実用されており，探索時の道路の込み具合など探索の基準は時間的に変化するものもありうる． ・最近では，携帯電話での乗り換え案内などで経路探索は広く知られている．既に利用している人も多いはずである． ・ここでは経路探索の解法の原理について概観する． ・駅や地点などを頂点，鉄道や道路などを枝としてグラフを構成することにより，グラフの最短経路探索問題として一般化することができる． ・この場合，探索の基準は経路の上の枝の長さの総和（これを経路長という）や重みの総和として表すことが普通である． ・最短経路探索は，グラフの上で，ある頂点から別の頂点に至る経路のうち，経路長が一番短いもの，あるいは重みの総和が一番小さいものを計算する方法として与えられる． ・最短経路探索問題の解き方にはいろいろなものが知られているが，地理空間情報の分野では，グラフの枝の長さは非負の数値であることが多いので，ダイクストラ法と呼ばれるアルゴリズムがよく用いられる．

4 最短経路探索 19分 出発地：池袋 11分 6分 御茶ノ水 2分 15分 秋葉原 新宿 2分 5分 目的地：東京 29分
・この図はJR山手線（緑）と，中央線・総武線（黄色），東京メトロ丸ノ内線（赤）の図． ・枝に付随された数値は，枝の重みであり，ここでは，枝で直接結ばれた2駅の間を移動するときの乗車時間とする． ・この図で池袋駅から東京駅へ行く経路を考える． ・実際には時刻表や乗り換え時間を考慮しなければならないが，まずはそれを無視する． ・すなわち，路線の乗り換え時間は0分として，乗車時間の総和が一番小さい経路を考える． ・この場合，池袋から丸ノ内線（赤線）で御茶ノ水に行き，そこから総武線（黄線）で秋葉原に行き，山手線（緑線）で東京に行くと 　11分＋2分＋2分で合計15分となり，乗車時間の総和は最小となる． ・実際には，乗り換えに時間がかかるので，池袋から東京駅まで丸の内線で行くのがよさそうである． ・このように，実際の状況を反映させるには，乗換時間を含めてグラフを構成すればよい． ・つまり，乗り換え時間を考慮する場合には，ひとつの駅名をひとつの頂点にするのではなく，同じ駅名であるが路線ごとに別の頂点を作成したり，さらに，行き先別プラットホームごとに別々に頂点を設けるなどの変更をすればよい． 　→練習問題．各駅の路線ごとに駅を作成せよ．例：池袋駅は，山手線池袋駅と丸ノ内線池袋駅に分ける．両者を結ぶ枝には， 　　乗り換え時間を重みとして与える． ・ 秋葉原 新宿 2分 5分 目的地：東京 29分

5 グラフ グラフは道路網や鉄道網などのネットワークを表すための基本的な構造． 頂点： 駅，地点，建物などを表す.
頂点：　駅，地点，建物などを表す. 枝（辺ともいう）：　鉄道，道路などを表す. 有向枝 (u,v) : 始点u, 終点v 無向枝 {u,v} : 端点u, 端点v 枝の長さ L(u,v), L{u,v} 枝の重み w(u,v), w{u,v} ・一言で経路と言っても，いろいろな可能性がある．たとえば，同じ駅に2度以上立ち寄るような経路を考慮するのかしないのか． ・そのような状況を整理するためにも，グラフを用いて表現することが望ましい． ・グラフは，とても簡潔にネットワーク構造を表現することができる．頂点と，頂点を結ぶ枝（または辺）という2種の構成要素から成る． ・頂点は，駅，地点，建物などを表すことが多い． ・枝は，駅と駅の間の線路や時刻表上の列車の移動，地点と地点を結ぶ道路などを表す． ・枝は一方通行の道路のように向きがある場合や，ふつうの路地のように向きの無いものと2種類ある． ・向きのある枝を有向枝（ゆうこうえだ），向きの無い枝を無向枝（むこうえだ）という． ・枝の重みは，列車の移動の所要時間や，地理的な距離などを表す． ・頂点や枝の取り方は状況に応じて自由に設定できる． ・片側一車線以上の幹線道路などは，上り方向と下り方向を別々の有向枝で表したり，まとめて1本の無効枝で表したりする． ・あるグラフGの枝を新たなグラフHの頂点として，Gの枝と枝のつながりをHの枝とするようなグラフも考えられる．

6 グラフ 池袋 秋葉原 １９ 御茶ノ水 １１ ６ ２ １５ ２ ・例として挙げた鉄道網をグラフとして表現すると，このようになる． ５ 新宿 ２９ 東京

7 単純グラフ セルフループ loop, self loop 平行枝 parallel edge グラフが単純 頂点から出て同じ頂点に戻る枝
同じ頂点を結ぶ枝 有向なら向きも同じ グラフが単純 セルフループも平行枝も無いグラフのこと ・ここで考えるものは， （１）セルフループ（ひとつの頂点だけを環状に結ぶ枝）が無い． （２）多重辺or平行枝（同じ頂点同志を結ぶ２本以上の枝）は無い． 　　　有向グラフ（枝に向きがある）ときは，始点と終点が同じ枝が2本以上無い． という（１），（２）の制約を満たすものだけを考える．このようなグラフを単純グラフ（simple graph)という．

8 ダイクストラ法 枝の重みが0以上（非負）であることが大事！ 考え方 実際の多くのネットワークは非負の重み．
出発地からの経路が短い順に，各頂点までの最短経路を定める．目的地までの最短経路が見つかれば終了．あるいは，すべての点までの最短経路を計算して終了． ・ダイクストラ法は最短経路を計算する方法として重要． ・ただし，ダイクストラ法が成立するには，枝の重みが非負であることが必要． ・枝の重みに負のものがある場合には，別の方法（ベルマン・フォード法など）を用いる． ・枝の重みに負のものがある場合の例： 　距離に比例して料金を支払うような状況を考える．ある区間を乗車すると，料金の払い戻しが受けられるようにする．そして，料金の一番安い経路を求める．

9 グラフ 出発地：池袋 秋葉原 １９ １１ 御茶ノ水 ６ ２ １５ ２ ５ 新宿 ２９ 目的地：東京
・例として挙げた鉄道網をグラフとして表現すると，このようになる． ・池袋駅を出発地として，鉄道網を用いて，目的地の東京駅に至る経路のうち，最短時間のものを考える． ・グラフの枝に記されているのは，その枝で結ばれた２頂点間の乗車時間（分単位）である． ５ 新宿 ２９ 目的地：東京

10 グラフ ∞ ∞ ∞ ∞ 出発地：池袋 秋葉原 １９ 御茶ノ水 １１ ６ ２ １５ ２ ５ 新宿 ２９ 目的地：東京
秋葉原 １９ ∞ 御茶ノ水 １１ ∞ ６ ２ ∞ １５ ２ ・各頂点には，出発点からの最短距離が計算される作業変数を割り当てる．頂点ｖに対応する作業変数を d(v) と記す． ・初期状態では，出発地の値は零（０），その他すべての作業変数の値は無限大（∞）である． ５ 新宿 ２９ 目的地：東京 ∞

11 グラフ 19 11 6 ∞ 池袋 秋葉原 １９ 御茶ノ水 １１ ６ ２ １５ ２ ５ 新宿 ２９ 東京 ・作業変数の値の中で最小値を探す．
秋葉原 １９ 19 御茶ノ水 １１ 11 ６ ２ 6 １５ ２ ・作業変数の値の中で最小値を探す． ・初期状態では，出発地の 0 が最小．この最小値を，最短距離として確定し，赤で記す． ・最短距離が確定した頂点と直接枝で接続している頂点に，その時点での仮の最短距離を与える．その仮の最短距離は，今確定した頂点を経由する経路の経路長が，作業変数の値より小さければ，その値に更新し，大きければ何もしない． ・ここでは，新宿が６，御茶ノ水が１１，秋葉原が１９となる． ５ 新宿 ２９ 東京 ∞

12 グラフ 池袋 秋葉原 １９ 19 御茶ノ水 １１ 11 ６ ２ 6 １５ ２ ・仮に与えた最短距離の中で最小値を探す．新宿６，御茶ノ水１１，秋葉原１９，東京∞． ・ここでは，新宿の６が最小なので，この値を池袋新宿間の最短距離の確定値として採用する． ・これで，池袋から新宿までの最短経路長が６であることが分かる． ・池袋新宿間の枝を太くして確定経路を表現する． ・新宿が確定したので，新宿と直接接続する頂点の仮の距離を更新する． ・ここでは，御茶ノ水は新宿経由で到達すると，６＋１５＝２１で，１１より大きいので，更新しない． ・東京は新宿経由で到達すると，６＋２９＝３５で，作業変数の現在値が∞なのでそれよりも小さい．そこで，作業変数の値を更新し，仮の距離を３５とする． ・この状態で，仮に定めた距離は御茶ノ水が１１，秋葉原が１９，東京が３５である． ・この中から最小値を探す． ５ 新宿 ２９ 東京 35

13 グラフ 池袋 秋葉原 １９ 19 →13 御茶ノ水 １１ 11 ６ ２ 6 １５ ２ ・御茶ノ水の１１が最小値なので，これを確定値として定め，この１１を与える枝を太く表現する． ・御茶ノ水から直接枝で接続する頂点のうち，最短距離が確定していない頂点（太い枝に接続していない頂点）について，仮の距離を更新する． ・秋葉原は，御茶ノ水経由で到達すると，１１＋２＝１３であり，与えられている仮の距離１９より小さいので，作業変数の値を１３に更新する． ・東京は，御茶ノ水経由で到達すると，１１＋５＝１６であり，現仮の距離３５より小さいので，１６に更新する． ・秋葉原１３，東京１６の中から最小値を探す． ５ 新宿 ２９ 東京 35→16

14 グラフ 池袋 秋葉原 １９ 19 →13 御茶ノ水 １１ 11 ６ ２ 6 １５ ２ ・秋葉原の１３が最小なので，これを最短距離として確定する． ・最短距離１３を与える経路は，御茶ノ水と接続する枝経由で与えられるので， 　御茶ノ水と秋葉原の枝を太表示する． ・秋葉原の最短距離が１３と確定したので，秋葉原と直接枝で接続する頂点の 　うち，最小距離が確定していない頂点の仮の距離を更新する． ・東京の仮の距離は１６であるが，秋葉原経由で東京に到達すると，１３＋２＝１５ 　となるので，１５に更新する． ５ 新宿 ２９ 東京 35→16→15

15 グラフ 池袋 秋葉原 １９ 19 →13 御茶ノ水 １１ 11 ６ ２ 6 １５ ２ ・仮の距離が与えられている頂点は東京のみであり，最小値は１５であるので，新宿～東京の最短距離は１５ であることがわかる． ・この状態で，太い枝で表示されるグラフは頂点を結ぶ「木」構造を成す． ・この木は，池袋を出発点として，池袋以外のすべての頂点までの最短経路を表す． ５ 新宿 ２９ 東京 35→16→15

16 ダイクストラ(Dijkstra)法 記号： s: 出発頂点（始点） u, v:頂点 (u,v):頂点uから頂点v への有向枝
記号：　 s: 出発頂点（始点） u, v:頂点 (u,v):頂点uから頂点v への有向枝 w(u,v): 枝(u,v)の重み d(v): 頂点vにおける作業場所（仮の距離distanceを格納） p(v): 頂点v における最短経路上でuの直前（親 parent） の頂点（太い枝を表現） ・以上を形式的に記述する． ・ダイクストラ法は最短経路を計算する方法として重要． ・ただし，ダイクストラ法が成立するには，枝の重みが非負であることが必要． 前述したが， 　　・枝の重みに負のものがある場合には，ベルマン・フォード法などを用いる． 　　・枝の重みに負のものがある場合の例： 　　　　距離に比例して料金を支払うような状況を考え，ある区間を乗車すると，特別に報奨金がもらえるようにする．

17 ダイクストラ法(アルゴリズム） 出発点を s と記す． s から各頂点 v までの距離を d(v) に計算する.
d(s)=0, s 以外のすべての頂点 v について d(v)=∞． Q をすべての頂点からなる集合とする． Qが空集合になるまで以下を繰り返す. 集合 Q に含まれる頂点vの中で d(v) が最小となるvを u と記す． ここで d(u) に計算された値が sからu に至る最短経路長として確定. u を Q から取り除く. uを端点に持つ全ての枝 (u,v) を考える. その枝のu以外のもう一方の端点をv とする. もし d(v)>d(u)+w(u,v)なら　d(v)=d(u)+w(u,v)　とする． そうでないなら何もしない． ・初期化は，出発点sを除いて，すべての頂点vについて　d(v)=∞にすること．d(s)=0 とする． ・すべての頂点からなる集合Qを用意する． ・Ｑに含まれる頂点のうち，d(u)が最小となるものをuとする．複数の候補が存在する場合には最小を与える頂点の中から任意にuを選んでよい． ・一番最初は，uとして，出発地sが選ばれるはずである． ・一般に，ここで選ばれたuについては，sからuに至る経路について最短のものの長さがd(u)になっている． ・ここで，Ｑに含まれる頂点vについて，d(v)はＱから取り除かれた頂点を経由してvにたどり着くことができる経路の中で，一番短いものの長さを表している． ・したがって，d(u)によりsからuに至る経路の最短の長さが確定する． ・すると，sからuを経由してvにたどり着く経路の長さ　d(u)+w(u,v) が，それまでにsからvに至る最短経路長として計算されたd(v)と比べて，さらに短ければ，そのd(v)の値をd(u)+w(u,v)に更新することができる．

18 ダイクストラ法に関する性質 計算量: 頂点の数をn, 枝の数をmとする. 出発地 s からの最短経路は木構造となる． 木構造の計算
単純な実装では O(n^2) ． 集合Qを効率よく扱うと，O(n log n + m) ． グラフが大規模で，出発地から目的地までの最短経路に限る場合，A*アルゴリズムと組み合わせてもっと効率よく計算する方法がある. 出発地 s からの最短経路は木構造となる． 単一頂点sから他のすべての頂点への最短経路を計算する． 木構造の計算 出発点 s から v に至る経路上で，v の直前の頂点を p(v) として示すように，p(v) の値を更新していけばよい． そのためにはd(v)の値を更新するときに，頂点vの親頂点を表すp(v)という作業場所を用意し，その値をuに更新すればよい． 目的地vからp(v)を辿って，出発地に戻る経路が最短経路を与える．

19 ワーシャル・フロイド法 Warshall-Floyd 法，ウォーシャル・フロイド法，フロイド・ウォーシャル法ともいう
全ての2頂点間の最短経路を同時に計算． n + 1 個の 2次元配列 c0, c1, c2, … , cn を用意する． 頂点 v_i から頂点 v_j に至る経路のうち，最短のものの経路長を cn[i][j] という配列要素に最終的に計算する． 考え方：頂点v_i と頂点 v_j を結ぶ経路について，経由してもよい頂点（経由可能頂点）を指定する． c1[i][j] : 経由可能頂点の集合が {v_1} の経路の最短経路長 c2[i][j] : 経由可能頂点の集合が {v_1,v_2} である経路の最短経路長 　（以下経由可能頂点の集合を一つずつ大きくする） cn[i][j] : 任意の点を経由可能な経路の最短経路長 ・全ての2頂点間の最短経路を同時に計算する方法 ・行列積に類似の計算方法よりも効率が良く，頂点数 n に対して　O(n^3) で計算される手法． ・2頂点間の経路のうち，最初は経由頂点が無いもの，すなわち，直接枝で結ばれたものだけを考える． ・次に，n個の頂点のうち，経由してもよい頂点を1個だけ固定する．その頂点を経由する経路か，直接接続する経路のうち最短のものを考える． ・以下同様にして，経由してもよい頂点を一つずつ増やして，最終的には全ての頂点を経由可能な頂点集合に設定し，最短経路を考える．

20 ワーシャル・フロイド法 経由してもよい頂点を直接指定することに注意！ v_2
c1[i][j]=min(c0[i][j], c0[i][1]+c[1][j]) c0[i][j]=w(i,j) v_1 v_1 ・最初は経由頂点なし，すなわち，直接枝で結ばれた2頂点間の距離 c[i][j] はその枝の重みに一致する． ・直接枝の無い2頂点間の距離は無限大（∞）． ・iとjが一致する場合の距離は０とする： c0[i][i]=0. ・次に，v_1 だけを経由可能な経路を考える． 頂点 v_i と v_j とは全ての i, j を動くから，c1[i][j]=min( c0[i][j], c0[i][1]+c0[1][j] ) が成立する． ・次に，v_1 および v_2 のどちらかあるいは両方経由可能，あるいは両方経由しない，ような経路について考える． 　頂点 v_i と v_j とは全てのi,jを動くから，c2[i][j]=min( c1[i][j], c1[i][2]+c1[2][j] が成立する． ・v_i と v_2 を結ぶ経路のうち，直接接続する経路と，v_1を経由するとどちらか小さい方が，c1[i][2] に計算させていること，および，v_2 と v_j を結ぶ経路のうち，直接接続するものとv_1を経由するものと比較して小さい方の距離が　c1[2][j] に計算されてることに注意． v_i v_j v_i v_j v_i v_j 経由頂点なし v_1だけを経由可能 v_1 と v_2 を経由可能 c2[i][j]=min(c1[i][j], c1[i][2]+c1[2][j])

21 ワーシャル・フロイド法 ck[i][j]=min( c(k-1)[i][j], c(k-1)[i][k]+c(k-1)[k][j] )
v_k v_1, v_2, …, v_(k-1) v_j v_i ck[i][j]=min( c(k-1)[i][j], c(k-1)[i][k]+c(k-1)[k][j] ) ・v_i と v_k を結ぶ経路のうち，直接接続する経路と，v_1, v_2, …, v_k-1 を経由するものの最小値が c(k-1)[i][k] に計算させている． ・v_k と v_j を結ぶ経路のうち，直接接続する経路と，v_1, v_2, …, v_k-1 を経由するものの最小値が c(k-1)[k][j] に計算されている． ・したがって，v_i と v_j を結ぶ経路のうち，v_1, v_2, …, v_k-1, v_k を経由するものの最小値はスライドの式で与えられることがわかる． v_1, v_2, …, v_(k-1), v_k v_j v_i

22 グラフ 池袋 秋葉原 １９ 御茶ノ水 １１ ６ ２ １５ ２ ・例として挙げた鉄道網をグラフとして表現すると，このようになる． ５ 新宿 ２９ 東京

23 ウォーシャルフロイド法 枝の重み（距離）を行列（2次元配列）の形にする．
枝1本で接続する２点間の距離w(I,j) :　c0[i][j]=w(i,j) 枝の無い頂点間の距離は∞（無限大） 池 新 御 秋 東 池袋 6 11 19 ∞ 新宿 15 29 御茶ノ水 2 5 秋葉原 東京 c0[i][j]

24 ウォーシャルフロイド法 池袋駅を経由してもよい 池 新 御 秋 東 池袋 6 11 19 ∞ 新宿 15 29 御茶ノ水 2 5 秋葉原
6 11 19 ∞ 新宿 15 29 御茶ノ水 2 5 秋葉原 東京 池 新 御 秋 東 池袋 6 11 19 ∞ 新宿 15 25 29 御茶ノ水 2 5 秋葉原 東京 ・新宿と秋葉原は直結していない 　　しかし， 新宿→池袋，池袋→秋葉原と池袋 経由で経路が存在するので c0 で∞であったところが，6+11=25 に更新される． ・逆方向　秋葉原→池袋，池袋→新宿も同様に 25 に更新される． c0[i][j] c1[i][j]

25 ウォーシャルフロイド法 池袋駅と新宿を経由してもよい 池 新 御 秋 東 池袋 6 11 19 ∞ 新宿 15 25 29 御茶ノ水 2 5
6 11 19 ∞ 新宿 15 25 29 御茶ノ水 2 5 秋葉原 東京 池 新 御 秋 東 池袋 6 11 19 35 新宿 15 25 29 御茶ノ水 2 5 秋葉原 東京 ・c1では，池袋→東京は，先の池袋を経由地にしても直結していないので，∞であった． ・c2では，c1の表で新宿を経由すると，池袋→新宿６，新宿→東京２９であるから，６＋２９＝３５になる． ・そのほかは変わらず． ・逆方向　東京→新宿，新宿→池袋も同様． c1[i][j] c2[i][j]

26 ウォーシャルフロイド法 池袋駅と新宿と御茶ノ水を経由してもよい 池 新 御 秋 東 池袋 6 11 19 35 新宿 15 25 29
6 11 19 35 新宿 15 25 29 御茶ノ水 2 5 秋葉原 東京 池 新 御 秋 東 池袋 6 11 13 16 新宿 15 17 20 御茶ノ水 2 5 秋葉原 東京 ・さらに，池袋，新宿に加えて御茶ノ水を経由可能とすると，池袋→秋葉原，池袋→東京，新宿→秋葉原，新宿→東京が 　更新できる． ・池袋→秋葉原は，池袋→御茶ノ水１１，御茶ノ水→秋葉原２であるから，１１＋２＝１３であり，１９より小さいので，更新． ・池袋→東京は，池袋→御茶ノ水１１，御茶ノ水→東京５であるから，１１＋５＝１６である，３５より小さいので，更新． ・新宿→秋葉原は，新宿→御茶ノ水１５，御茶ノ水→秋葉原２であるから，１５＋２＝１７であり，２５より小さいので，更新． ・新宿→東京は，新宿→御茶ノ水１５，御茶ノ水→東京５であるから，１５＋５＝２０であり，２９より小さいので，更新． ・逆方向も同様 c2[i][j] c3[i][j]

27 ウォーシャルフロイド法 池袋駅と新宿と御茶ノ水と秋葉原を経由してもよい 池 新 御 秋 東 池袋 6 11 13 16 新宿 15 17
6 11 13 16 新宿 15 17 20 御茶ノ水 2 5 秋葉原 東京 池 新 御 秋 東 池袋 6 11 13 15 新宿 17 19 御茶ノ水 2 4 秋葉原 東京 ・さらに，池袋，新宿，御茶ノ水に加えて，秋葉原も経由地として加える． ・池袋→東京は，池袋→秋葉原１３（実は，池袋→御茶ノ水１１＋御茶ノ水→秋葉原２），秋葉原→東京２で，１３＋２＝１５であり，16より小さいので更新． ・新宿→東京は，新宿→秋葉原１７（新宿→御茶ノ水１５＋御茶ノ水→秋葉原２），秋葉原→東京２で，１７＋２＝１９であり，20より小さいので更新． ・御茶ノ水→東京は，御茶ノ水→秋葉原２，秋葉原→東京２で，２＋２＝４であり，５より小さいので更新． ・逆方向も同様． c3[i][j] c4[i][j]

28 ウォーシャルフロイド法 全駅（池袋駅と新宿と御茶ノ水と秋葉原と東京）を経由してもよい 池 新 御 秋 東 池袋 6 11 13 15 新宿
6 11 13 15 新宿 17 19 御茶ノ水 2 4 秋葉原 東京 池 新 御 秋 東 池袋 6 11 13 15 新宿 17 19 御茶ノ水 2 4 秋葉原 東京 ・最終的に全ての駅を経由地として加える． ・この例では特に更新は起きない． c4[i][j] c5[i][j]

29 ウォーシャルフロイド法 ｎ個の頂点をv1,v2,…,vnとする． 2個の2次元配列 c[i][j] と d[i][j] を用意する．
c[i][j]= 頂点viと頂点vjを結ぶ枝の距離 　　　　　枝が無い場合には, 無限大（∞） 　　　　　c[i][i]はゼロ for k=1 to n do begin for i=1 to n do for j=1 to n do d[i][j]=min( c[i][j], c[i][k]+c[k][j] ) for i=1 to n do for j=1 to n do c[i][j]=d[i][j] End (* c と d は同じ配列を用いて一行上を削除可能　*) ・最初は, k=0とし，任意の2頂点間の最短経路は，その2頂点間を結ぶ枝があればその枝の重みに一致し，枝が無ければ，∞とする． ・kの値をひとつ増やす． ・ここでv1,…, vk-1の頂点を経由してもよいとした場合の経路について，任意の2頂点間の最短経路が既知とする． ・任意の2頂点をvi, vj とし，v1,…, vk-1 に加えて，vk も経由してよいとした場合の経路を考えると，新たに考慮すべき経路の重みは　c[i][k]+c[k][j] であるので，これと　c[i][j] のうち小さいほうの値を計算すればよい．

30 2番目に短い最短経路 乗り換え案内など，最短経路だけでなく，2番目，3番目に短い経路に興味がある場合もある．
探索経路の条件：simple な経路（パス） Simpleでない経路の例：同じ頂点を2度通るもの 考え方：最短経路を構成する枝がp本あるとする． その p本の枝のそれぞれ1本だけを除いたグラフにおける最短経路を調べる その p個の最短経路のうち，経路長が最短のものが元のグラフでの2番目に短い経路 これを「頂点数-1」本まで繰り返す． 実は，元のグラフを二つ用意して適宜それらを接続すると，1回ダイクストラ法を用いて計算するだけで済む