ワーシャル-フロイド法による最短経路の導出 - SQLによる解法
本文は後で書こう.
次に示すSQL文は,有向グラフおよび辺に対する重みを与える写像について,最短経路のコストを導く.これをそのまま実行すると,次のについて,すべての2頂点間の最短経路のコストを導く.
WITH edges(source, sink, cost) AS ( VALUES (1, 2, 2), (2, 3, 3), (2, 4, 5), (3, 4, 1), (3, 5, 1), (4, 3, 2), (4, 5, 4), (5, 2, 3) ), v(id) AS ( SELECT DISTINCT source FROM edges UNION SELECT DISTINCT sink FROM edges ), v2(source, sink) AS ( SELECT DISTINCT a.id, b.id FROM v AS a, v AS b ) SELECT * FROM ( WITH RECURSIVE wf(phase, start, goal, cost) AS ( SELECT * FROM ( SELECT phase, v2_init.source, v2_init.sink, cost FROM ( SELECT (SELECT MIN(id) FROM v) AS phase, source, sink FROM v2 ) AS v2_init LEFT OUTER JOIN ( SELECT * FROM edges UNION SELECT id, id, 0 FROM v ) AS edges_init ON v2_init.source = edges_init.source AND v2_init.sink = edges_init.sink ) AS wf_init UNION SELECT * FROM ( WITH wf_cpy(phase, start, goal, cost) AS ( SELECT * FROM wf ), cost_via(start, goal, cost) AS ( SELECT wf_1.start, wf_2.goal, wf_1.cost + wf_2.cost FROM wf_cpy AS wf_1, wf_cpy AS wf_2 WHERE wf_1.goal = wf_1.phase AND wf_2.start = wf_2.phase ) SELECT (SELECT MIN(id) FROM v WHERE phase < id), wf_cpy.start, wf_cpy.goal, CASE WHEN cost_via.cost < wf_cpy.cost OR wf_cpy.cost IS NULL THEN cost_via.cost ELSE wf_cpy.cost END FROM wf_cpy, cost_via WHERE wf_cpy.start = cost_via.start AND wf_cpy.goal = cost_via.goal ) AS wf_rec ) SELECT start, goal, cost FROM wf WHERE phase IS NULL ORDER BY start, goal ) AS result ;
このSQL文を実行すると,次の結果を得る.
start | goal | cost -------+------+------ 1 | 1 | 0 1 | 2 | 2 1 | 3 | 5 1 | 4 | 6 1 | 5 | 6 2 | 1 | 2 | 2 | 0 2 | 3 | 3 2 | 4 | 4 2 | 5 | 4 3 | 1 | 3 | 2 | 4 3 | 3 | 0 3 | 4 | 1 3 | 5 | 1 4 | 1 | 4 | 2 | 6 4 | 3 | 2 4 | 4 | 0 4 | 5 | 3 5 | 1 | 5 | 2 | 3 5 | 3 | 6 5 | 4 | 7 5 | 5 | 0 (25 rows)
この実行結果からグラフのすべての2頂点間に存在する最短経路のコストを知ることができる.結果がNULL(空)となっているところは,2点間に有向道が存在せず,到達不可能であることを表す.
また,コストの和が負となる有向閉路を部分グラフとして持つときは,ある頂点について,自分自身へのコストは負であると計算される.すなわち,と計算される.