ダイクストラのアルゴリズムを用いた最短経路探索

最短経路探索機能には次の宣言文が必要です:

CREATE OR REPLACE FUNCTION shortest_path(sql text, source_id integer, 
		target_id integer, directed boolean, has_reverse_cost boolean) 
	RETURNS SETOF path_result

引数:

sql: SQLのクエリーです。以下に続くカラムからなる行セットを返します。

SELECT id, source, target, cost FROM edge_table

• id: エッジの識別子[int4]
• source: 始点ノードの識別子[int4]
• target: 終点ノードの識別子[int4]
• cost: エッジにかかる重み(負の重みはエッジがグラフに挿入されることを防ぎます)
• reverse_cost (オプション): エッジの反対方向のコスト。この値はdirectedおよびhas_reverse_costパラメータがtrueの場合のみ使用されます。(負のコストについては前述の通りです)

source_id: 始点のノードID[int4]

directed: ネットワークが有向グラフの場合はtrue

has_reverse_cost: trueの場合、SQLで生成される行セットのreverse_costカラムは、エッジの逆方向にかかる重みとして使用されます。各行のカラム構成は:

関数は行のセットを返します。それぞれの交差しているエッジあたり1行、また終点を含む追加行が1行あります。

• vertex_id: 各エッジの始点ノードIDです。経路探索の終点ノードIDを含む最後のエッジの後に、もう一行あります。(最後のエッジの終点ノードから続くエッジがないことを示すため)
• edge_id: 交差したエッジのID
• cost: 現在のエッジに関連付けられたコスト。最後のエッジの場合は0となります。したがって、経路の合計コストはcostカラムの合計となります。

例:

SELECT * FROM shortest_path('SELECT gid AS id, source::int4, 
         target::int4, length::double precision AS cost,
    FROM dourol',3, 7, false, false);

 vertex_id | edge_id | cost 
-----------+---------+------------------------
         3 |       2 |    0.000763954363701041
         4 |      21 |    0.00150254971056274
         6 |       5 |    0.000417442425988342
         7 |      -1 |    0
(4 rows)

SELECT * FROM shortest_path('SELECT gid AS id, source::int4, 
         target::int4, length::double precision AS cost,length::double precision 
    AS reverse_cost FROM dourol', 3, 7, true, true);

---

この日本語訳の著作権は、日本ユニシス株式会社に帰属しています。また、この日本語訳は、GNU FDLのもとで提供されています。