A*アルゴリズムを用いた最短経路探索

shortest_path_astar関数には次の宣言文が必要です:

CREATE OR REPLACE FUNCTION shortest_path_astar(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, x1, y1, x2, y2 FROM edge_table

• id: エッジの識別子[int4]
• source: 始点ノードの識別子[int4]
• target: 終点ノードの識別子[int4]
• cost: エッジにかかる重み(負の重みはエッジがグラフに挿入されることを防ぎます)
• x1: エッジの始点のx座標
• y1: エッジの始点のy座標
• x2: エッジの終点のx座標
• y2: エッジの終点のy座標
• 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_astar('SELECT gid AS id, source::int4, 
         target::int4, length::double precision AS cost, x1, y1, x2, y2 
    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_astar('SELECT gid AS id, source::int4, 
         target::int4, length::double precision AS cost,length::double precision 
    AS reverse_cost, x1, y1, x2, y2 FROM dourol', 3, 7, true, true);

---

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