ダイクストラ法

発明者： , , , , ,
出願人/特許権者：
公報種別：公開公報
出願番号（国際出願番号）：特願平11-308232
公開番号（公開出願番号）：特開2001-125882
出願日： 1999年10月29日
公開日（公表日）： 2001年05月11日
要約：

【要約】【目的】単一始点単一終点、単一始点複数終点又は複数始点単一終点間での最短経路を求める効率的な方法を提供する。【構成】地図上の交差点に対応した各ノードと、それに繋がるリンクコスト(距離)を分離独立させ、それぞれを隣接行列或いは隣接リストで管理しながらダイクストラ法を用いて経路探索を行う。このとき、リンクコストを隣接行列或いは隣接リストに格納する際には、対応するノードを昇順にソーティングして格納する。そして、最短経路を確定する候補リンクコスト和を格納する連結リストR1又は配列D1と新ノードを見つけた時それに繋がるリンクコスト和を格納する連結リストR2又は配列D2を別に用意しておく。リンクコストを確定する際には連結リストR1又は配列D1と新ノードに繋がるリンクコスト和の連結リストR2又は配列D2を比較し、最小値となる要素を切り離した後に連結リストR1又は配列D1へ連結リストR2を挿入ソートする。

請求項（抜粋）：

重みつきグラフの単一始点最短路(最適路)或いは単一終点最短路を求める方法に於いて、各交点情報をノードとし交点間の重み情報をリンクコストとしたとき、各交点が接続するノード番号とリンクコストをそれぞれ分離独立させて予め連結先ノード番号の昇順又は降順に格納した隣接行列或いは隣接リストと、最短経路を確定する際、候補になるノードまでの最小リンクコスト和が昇順或いは降順になるよう該当ノード番号を格納した連結リストR1又は配列D1と、ノードに接続する接続先の新ノード番号を格納した前記隣接行列或いは前記隣接リストから取り出したリンクコストと、接続前のノードのリンクコスト和を加算したリンクコスト和が昇順或いは降順になるよう前記新ノード番号を格納する連結リストR2又は配列D2と、前記連結リストR2又は前記配列D2を前記連結リストR1又は前記配列D2に挿入ソートした連結リストR1或いは配列D2とからなるダイクストラ法。

IPC (3件)：

G06F 17/00 , G01C 21/00 , G09B 29/10

FI (3件)：

G01C 21/00 G , G09B 29/10 Z , G06F 15/20 Z

Fターム (7件)：

2C032HD21 , 2F029AB13 , 2F029AC08 , 2F029AC14 , 5B049AA04 , 5B049CC00 , 5B049EE31

前のページに戻る