nkhrlab~

140字超の記事

ワーシャル-フロイド法による最短経路の導出 - SQLによる解法

本文は後で書こう.

次に示すSQL文は,有向グラフG = (V, A)および辺に対する重みを与える写像f : A \to \mathbb{R}について,最短経路のコストを導く.これをそのまま実行すると,次のV, A, fについて,すべての2頂点間の最短経路のコストc : V^{2} \to \mathbb{R}を導く.
V = \{1, 2, 3, 4, 5\}
A = \{ (1, 2), (2, 3), (2, 4), (3, 4), (3, 5), (4, 3), (4, 5), (5, 2) \}
f( (1, 2) ) = 2, f( (2, 3) ) = 3, f( (2, 4) ) = 5, f( (3, 4) ) = 1,
f( (3, 5) ) = 1, f( (4, 3) ) = 2, f( (4, 5) ) = 4, f( (5, 2) ) = 3

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)

この実行結果からグラフGのすべての2頂点間に存在する最短経路のコストc : V^{2} \to \mathbb{R}を知ることができる.結果がNULL(空)となっているところは,2点間に有向道が存在せず,到達不可能であることを表す.

また,コストの和が負となる有向閉路を部分グラフとして持つときは,ある頂点について,自分自身へのコストは負であると計算される.すなわち,\exists v \in V (c( (v, v) ) < 0)と計算される.