最短経路探索プログラム、最短経路探索プログラムを記憶したコンピュータ読み取り可能な記録媒体、最短経路探索装置、最短経路探索方法

【課題】対象物が転回可能とする場合等も含めて、最短経路を検索することができない。
【解決手段】最短経路探索プログラムであって、複数のノードと、該複数のノード間を接続するとともに、通過する際のコストが関連付けられた複数のエッジとで形成された経路において、該複数のノードに含まれるスタートノードからゴールノードまでの最短経路を探索する最短経路探索プログラムであって、前記各ノードに接続された１または複数のエッジ間の進行の可否を示す進行可否識別情報が、前記各ノードを識別するノード識別情報と、前記各エッジを識別するエッジ識別情報と、に関連付けて記憶された進行可否情報を取得する進行可否情報取得手段、及び、前記進行可否情報及び前記各エッジに関連付けられたコストに基づいて、前記スタートノードから前記ゴールノードまでの最短経路を取得する最短経路取得手段、としてコンピュータを機能させる。

【発明の詳細な説明】
【技術分野】
【０００１】
最短経路探索プログラム、最短経路探索プログラムを記憶したコンピュータ読み取り可能な記録媒体、最短経路探索装置、最短経路探索方法に関する。
【背景技術】
【０００２】
いわゆる最短経路検索アルゴリズムとして、いわゆるＡ＊アルゴリズムが知られている。Ａ＊アルゴリズムとは、複数のノードと、当該複数のノード間を接続するとともに、通過する際のコストが関連付けられた複数のエッジとで形成された経路において、スタートノードからゴールノードまでの最短経路を探索するためのアルゴリズムである。
【０００３】
当該アルゴリズムの概要は、まず初期化処理で、スタートノードの値を０、他のノードの値を未定義または∞に設定する。その後、確定されていないノードのうち、最小の値を持つノードを見つけ確定ノードとし、当該確定ノードから延伸するエッジをそれぞれチェックし、確定ノードまでのコストと、エッジのコストの和を計算する。当該コストの和がそのノードの現在の値よりも小さければ更新する。上記のような初期化処理以降の処理を、確定ノードがピックアップされるまで繰り返すものである。
【発明の概要】
【発明が解決しようとする課題】
【０００４】
しかしながら、上記のようなアルゴリズムにおいては、ノードの複数回の登録を認めると、同じ経路を無限に回り続けてしまう可能性があることから、一度確定されたノードを再度登録（確定）させることはできない。よって、あるノードに相当する場所において、対象物を転回（ターン）させる場合も含めて最短経路を求めることはできない。
【０００５】
また、仮想空間において、ある程度の長さを有する対象物、例えば、電車や胴体の長い動物など、を上記経路に沿って移動させる場合であって、あるノードで接続される一方のエッジと他方のエッジの角度が所定の角度以下である場合には、通常では当該対象物が曲がらないような不自然な角度で対象物が曲がりつつ、当該一方のエッジと他方のエッジを通過してしまう場合もある。
【０００６】
本発明は、上記に鑑みて、あるノードに相当する場所においては、対象物が転回可能とする場合も含めて、最短経路を検索することのできる最短経路探索装置、最短経路探索方法、最短経路探索プログラムを実現することを目的とする。
【０００７】
また、本発明の他の目的は、所定のエッジのペアで構成される経路について通過可能か否かを設定し、当該設定に応じた最短経路を検索することのできる最短経路探索装置、最短経路探索方法、最短経路探索プログラムを実現することである。
【課題を解決するための手段】
【０００８】
本発明の最短経路探索プログラムは、複数のノードと、該複数のノード間を接続するとともに、通過する際のコストが関連付けられた複数のエッジとで形成された経路において、該複数のノードに含まれるスタートノードからゴールノードまでの最短経路を探索する最短経路探索プログラムであって、前記各ノードに接続された１または複数のエッジ間の進行の可否を示す進行可否識別情報が、前記各ノードを識別するノード識別情報と、前記各エッジを識別するエッジ識別情報と、に関連付けて記憶された進行可否情報を取得する進行可否情報取得手段、及び、前記進行可否情報及び前記各エッジに関連付けられたコストに基づいて、前記スタートノードから前記ゴールノードまでの最短経路を取得する最短経路取得手段、としてコンピュータを機能させる。
【０００９】
本発明の最短経路探索装置は、複数のノードと、該複数のノード間を接続するとともに、通過する際のコストが関連付けられた複数のエッジとで形成された経路において、該複数のノードに含まれるスタートノードからゴールノードまでの最短経路を探索する最短経路探索装置であって、前記各ノードに接続された１または複数のエッジ間の進行の可否を示す進行可否情報が、前記各ノードを識別するノード識別情報と、前記各エッジを識別するエッジ識別情報と、に関連付けて記憶された進行可否情報を取得する進行可否情報取得手段と、前記進行可否情報及び前記各エッジに関連付けられたコストに基づいて、前記スタートノードから前記ゴールノードまでの最短経路を取得する最短経路取得手段と、を有する。
【００１０】
本発明の最短経路探索方法は、複数のノードと、該複数のノード間を接続するとともに、通過する際のコストが関連付けられた複数のエッジとで形成された経路において、該複数のノードに含まれるスタートノードからゴールノードまでの最短経路を探索する最短経路探索方法であって、前記各ノードに接続された１または複数のエッジ間の進行の可否を示す進行可否情報が、前記各ノードを識別するノード識別情報と、前記各エッジを識別するエッジ識別情報と、に関連付けて記憶された進行可否情報を取得し、前記進行可否情報及び前記各エッジに関連付けられたコストに基づいて、前記スタートノードから前記ゴールノードまでの最短経路を取得する。
【図面の簡単な説明】
【００１１】
【図１】本発明の実施の形態における最短経路探索装置の構成の概要について説明するための図である。
【図２】本実施の形態における最短経路探索装置の機能的な構成について説明するための図である。
【図３】本実施の形態における経路の一例を示す図である。
【図４Ａ】図３に示した経路が探索されていく様子を順次示す図である。
【図４Ｂ】図３に示した経路が探索されていく様子を順次示す図である。
【図４Ｃ】図３に示した経路が探索されていく様子を順次示す図である。
【図４Ｄ】図３に示した経路が探索されていく様子を順次示す図である。
【図４Ｅ】図３に示した経路が探索されていく様子を順次示す図である。
【図４Ｆ】図３に示した経路が探索されていく様子を順次示す図である。
【図４Ｇ】図３に示した経路が探索されていく様子を順次示す図である。
【図４Ｈ】図３に示した経路が探索されていく様子を順次示す図である。
【図４Ｉ】図３に示した経路が探索されていく様子を順次示す図である。
【図４Ｊ】図３に示した経路が探索されていく様子を順次示す図である。
【図４Ｋ】図３に示した経路が探索されていく様子を順次示す図である。
【図４Ｌ】図３に示した経路が探索されていく様子を順次示す図である。
【図４Ｍ】図３に示した経路が探索されていく様子を順次示す図である。
【図４Ｎ】図３に示した経路が探索されていく様子を順次示す図である。
【図４Ｏ】図３に示した経路が探索されていく様子を順次示す図である。
【図５】本実施の形態におけるパス情報記憶部に記憶される経路に関する情報の形式の一例を示す図である。
【図６】本実施の形態における進行可否情報記憶部に記憶される進行可否情報の形式の一例を示す図である。
【図７】本実施の形態におけるコスト情報記憶部に記憶されるコスト情報の形式の一例を示す図である。
【図８】図２に示した進行可能コース情報取得部の機能的な構成について説明するための図である。
【図９】図２に示した登録コース情報設定部の機能的な構成について説明するための図である。
【図１０】本実施の形態における最短経路探索装置の処理のフローについて説明するための図である。
【図１１】図１０に示したＳ１０５のフローの詳細について説明するための図である。
【図１２】本実施の形態において求められた最短経路の一例を示す図である。
【発明を実施するための形態】
【００１２】
以下、本発明の実施形態について、図面を参照しつつ説明する。なお、図面については、同一又は同等の要素には同一の符号を付し、重複する説明は省略する。
【００１３】
図１は、本発明の実施の形態における最短経路探索装置の構成の概要について説明するための図である。図１に示すように、最短経路探索装置１００は、例えば、ＣＰＵやメモリ等で構成されるコンピュータで構成され、例えば、制御部１０１、記憶部１０２、通信部１０３、操作部１０４、表示部１０５を有する。なお、制御部１０１、記憶部１０２、通信部１０３、操作部１０４、表示部１０５は、内部バス１０６により互いに接続される。
【００１４】
制御部１０１は、例えば、ＣＰＵ、ＭＰＵ等であって、記憶部１０２に格納されたプログラムに従って動作する。記憶部１０２は、例えば、ＲＯＭやＲＡＭ、ハードディスク等の情報記録媒体で構成され、制御部１０１によって実行されるプログラムを保持する情報記録媒体である。また、記憶部１０２は、制御部１０１のワークメモリとしても動作する。なお、当該プログラムは、例えば、ネットワーク（図示なし）を介して、ダウンロードされて提供されてもよいし、または、ＣＤ−ＲＯＭやＤＶＤ−ＲＯＭ等のコンピュータで読み取り可能な各種の情報記録媒体によって提供されてもよい。
【００１５】
通信部１０３は、当該最短経路探索装置１００を、ネットワークを介して、他の情報処理装置（図示なし）やデータベース（図示なし）等と接続する。操作部１０４は、例えば、キーボード、マウス、または、コントローラ等で構成され、ユーザーの指示操作に応じて、当該指示操作の内容を制御部１０１に出力する。表示部１０５は、例えば、液晶ディスプレイ、有機ＥＬディスプレイ等であって、制御部１０１からの指示に従い、情報を表示する。なお、上記最短経路探索装置１００の構成は、一例であってこれに限定されるものではない。
【００１６】
図２は、本実施の形態における最短経路探索装置の機能的な構成について説明するための図である。図２に示すように、最短経路探索装置１００は、パス情報記憶部２０１、進行可否情報記憶部２０２、コスト情報記憶部２０３、初期コース情報設定部２０４、登録コース情報記憶部２０５、最小登録コース情報抽出部２０６、確定コース情報記憶部２０７、進行可能コース情報取得部２０８、登録コース情報設定部２０９を有する。
【００１７】
なお、下記においては、説明の簡略化のため、主に、図３に示した経路において、最短経路が探索される場合を例として説明する。また、図４Ａ乃至図４Ｏは、図３に示したコースにおいて、最短経路が決定されるまでのコース情報が順次、登録コース情報記憶部２０５及び確定コース情報記憶部２０７に記憶されていく様子を図３に示した経路とともに示す。また、図４Ａ乃至図４Ｏにおいては、登録コース情報記憶部２０５及び確定コース情報記憶部２０７をそれぞれ、登録リスト及び確定リストとして示した。なお、コース情報、登録コース情報記憶部２０５及び確定コース情報記憶部２０７の詳細については後述する。
【００１８】
また、図３において、ノードＢについては、エッジＥ１またはＥ２からノードＢを介してエッジＥ２またはＥ１に進行することはできず、また、ノードＤについては、エッジＥ３またはＥ４からノードＢを介してエッジＥ４またはＥ２に進行することはできないものとして設定される場合を想定する。更に、図３において、ノードＥは、転回可能、つまり、エッジＥ５からノードＥを介してエッジＥ５に進行してもよいし、Ｅ６からノードＥを介してＥ６に進行してもよいものとして設定される場合を想定する。図４においては、ノードから進行できる方向を矢印（斜線、ドットはなし）で示し、登録済みのコース（登録コース情報記憶部２０５に記憶されたコース）を矢印（ドットを付加した矢印）、確定済みのコース（確定コース情報記憶部２０７に記憶されたコース）を矢印（ドットを付加した矢印）で示した。
【００１９】
パス情報記憶部２０１は、ノードを示すノード識別情報（ノードＩＤ）と、ノードとノードを接続するエッジを示すエッジ識別情報（エッジ識別情報）とを関連付けて記憶する。具体的には、例えば、図５に示すように、ノードＩＤ毎に、各ノードに接続されるエッジを示すエッジＩＤを表の形式で記憶する。これにより、図３に示すようなノードとエッジで形成される経路（パス）が表される。
【００２０】
例えば、図５において、ノードＩＤ、Ｓのノード（スタートノードに相当する）は、エッジＩＤ、Ｅ０のエッジと関連付けられて記憶されているので、スタートノードはエッジＥ０と接続されることを示す。ノードＩＤ、Ａのノード（ノードＡ）は、エッジＩＤ、Ｅ０（エッジＥ０）のエッジと関連付けられて記憶されているので、ノードＡは、エッジＥ０と接続されていることを示す。つまり、エッジＥ０は、スタートノードとノードＡを接続することを示す。以下同様にして、図５に示すような経路が表される。
【００２１】
進行可否情報記憶部２０２は、ノードＩＤ、エッジＩＤのペア、当該エッジのペアを当該ノードを介して移動可能か否かを示す移動可否識別情報（進行可否ＩＤ）を、関連付けて記憶する。具体的には、例えば、図６に示すように、ノードＩＤ毎に、エッジＩＤのペア、進行可否識別情報（進行可否ＩＤ）としての０または１の値を、表の形式で記憶する。なお、進行可否ＩＤについては、例えば、０の値が移動不可を示し、１の値が進行可能を示す。
【００２２】
また、例えば、図６においては、ノードＩＤ、ＢについてエッジＩＤ、Ｅ１とＥ１のペアが、進行可否ＩＤ、０（進行不可を示す）として記憶されているので、ノードＢについて、Ｅ１から進入してＥ１に進出するような移動、つまり、転回ができないことを表す。また、ノードＩＤ、ＢについてエッジＩＤ、Ｅ１とＥ２のペアが、進行可否ＩＤ、０として記憶されているので、Ｅ１またはＥ２から進入して、ノードＢを通過してＥ２またはＥ１に進出することはできないことを表す。一方、ノードＩＤ、ＢについてエッジＩＤ、Ｅ１とＥ３のペアが、進行可否ＩＤ、１（進行可能を示す）として記憶されているので、Ｅ１またはＥ３から進入して、ノードＢを通過してＥ３またはＥ１に進出することはできないことを表す。
【００２３】
コスト情報記憶部２０３は、エッジＩＤに関連付けて、各エッジを通過する際に要するコストを示すコスト情報を記憶する。ここで、コストとは、例えば、距離や時間等に相当する数値である。具体的には、図７に示すように、エッジＩＤ毎に、コスト情報としての数値を記憶する。例えば、図７においては、エッジＩＤ、Ｅ０（エッジＥ０）についてコスト情報、１が関連付けて記憶されているので、エッジＥ０を通過するには、コスト１（例えば、エッジＥ０の距離が１を示す）を要することを表す。
【００２４】
初期コース情報設定部２０４は、スタート時におけるコース情報（初期コース情報）を設定し、後述する登録コース情報記憶部２０５に記憶する。ここで、コース情報とは、ノードを示すノードＩＤ、当該ノードからの進行方向のエッジを示すエッジＩＤ、当該ノードに到達するまでに要した累積コスト情報、進入元を示すエッジの進入元エッジＩＤを関連付けて構成される。
【００２５】
具体的には、初期コース情報設定部２０４は、上記例の場合、パス情報記憶部２０１を参照し、ノードＩＤ、Ｓに関連付けて記憶されているエッジＩＤ、Ｅ０を取得する。なお、スタート時においては、累積コストは０であり、進入元のエッジは存在しないので、累積コスト情報として０、進入元エッジＩＤはなしとなる。よって、初期コース情報設定部２０４は、初期コース情報として、ノードＩＤ、Ｓ、エッジＩＤ、Ｅ０、累積コスト情報、０、進入元エッジＩＤ、なしとして、登録コース情報記憶部２０５に記憶する。この場合の様子を、図４Ａに示した。
【００２６】
なお、ここで、説明の簡略化のため、各コース情報を、上記説明の順に、Ｓ−Ｅ０、コスト：０、ＩＮ：−のようにして示すものとして説明する。また、各コース情報に含まれるノードを示すノードＩＤと当該ノードからの進行方向のエッジを示すエッジＩＤを用いて、各コース情報をノードＩＤ−エッジＩＤで称する。つまり、例えば、ノードを示すノードＩＤがＡ、当該ノードからの進行方向のエッジを示すエッジＩＤがＥ４のコース情報を、Ａ−Ｅ４のコース情報と称する。
【００２７】
最小登録コース情報抽出部２０６は、登録コース情報記憶部２０５に記憶されているコース情報のうち、最小のコスト情報を有するコース情報を取得する。また、取得した最小のコース情報を登録コース情報記憶部２０５から削除する。具体的には、例えば、図４Ａに示した場合、登録コース情報記憶部２０５には、１のコース情報のみ記憶されているので、この場合は、当該１のコース情報を取得する。また、例えば、図４Ｃに示した場合、コスト情報が最小であるのは、Ａ−Ｅ４のコース情報であることから、当該Ａ−Ｅ４のコース情報を取得するとともに、当該Ａ−Ｅ４のコース情報を登録コース情報記憶部２０５から削除する。なお、後述するように、当該Ａ−Ｅ４のコース情報は、次に、図４Ｄに示すように、確定コース情報記憶部２０７に記憶される。
【００２８】
確定コース情報記憶部２０７は、最小登録コース情報抽出部２０６により抽出されたコース情報を、順次追加して記憶する。例えば、図４Ｂにおいては、上述のように図４Ａにおいて、Ｓ−Ｅ０のコース情報が抽出されるので、当該Ｓ−Ｅ０のコース情報が、確定コース情報記憶部２０７に記憶される。
【００２９】
進行可能コース情報取得部２０８は、確定コース情報記憶部２０７に新たに記憶されたコース情報（確定コース情報）に基づいて、当該確定コース情報で示されるコース（確定コース）の次に進行可能なコースを示す進行可能コース情報を取得する。以下、図８を用いて具体的に説明する。
【００３０】
図８は、進行可能コース情報取得部の機能的な構成を説明するための図である。図８に示すように、進行可能コース情報取得部２０８は、接続先情報取得部３０１、エッジ情報取得部３０２、コスト算出部３０３、進入元エッジ情報取得部３０４、ゴール判定部３０５、進行可能コース情報判定部３０６を有する。
【００３１】
接続先情報取得部３０１は、確定コース情報に基づき、当該確定コースの接続先のノードＩＤを取得する。例えば、確定コース情報が、Ｓ−Ｅ０、コスト：０、ＩＮ：−の場合、図５を参照すると、ノードＳの他にノードＥ０に関連付けてノードＡが記憶されていることがわかることから、接続先情報としてノードＩＤ、Ａを取得する。
【００３２】
エッジ情報取得部３０２は、上記取得された接続先ノードのノードＩＤ、確定コース情報に含まれるエッジＩＤ、進行可否情報記憶部２０２に記憶された進行可否情報に基づいて、進行可能なエッジ情報（コース情報）を取得する。具体的には、例えば、上記例の場合、接続先ノードのノードＩＤとしてＡ、エッジＩＤとしてＥ０が取得される。そして、ノードＩＤ、Ａ、エッジＩＤ、Ｅ０について、進行可否情報が１のエッジＩＤとして、Ｅ１及びＥ４が記憶されていることから、当該エッジＩＤ、Ｅ１及びＥ４を取得する。
【００３３】
コスト算出部３０３は、確定コース情報に含まれる累積コストを取得するとともに、確定コース情報に含まれるエッジＩＤを取得する。そして、当該エッジＩＤに基づいて、コスト情報記憶部２０３を参照し、当該エッジＩＤに関連して記憶されているコスト情報を取得し、当該コスト情報と確定コース情報に含まれる累積コストの和を算出する。例えば、上記例の場合、確定コース情報が、Ｓ−Ｅ０、コスト：０、ＩＮ：−であることから、確定コース情報に含まれる累積コスト０を取得するとともに、エッジＩＤ、Ｅ０を取得する。そして、コスト情報記憶部２０３にはエッジＩＤ、Ｅ０についてコスト１が関連付けて記憶されていることから、累積コスト０とコスト１の和である１を算出する。
【００３４】
進入元エッジ情報取得部３０４は、確定コース情報に含まれるエッジＩＤを進入元エッジ情報として取得する。上記例の場合、確定コース情報が、Ｓ−Ｅ０、コスト、０、ＩＮ：−であることから、エッジＩＤ、Ｅ０を進入元エッジＩＤとして取得する。
【００３５】
ゴール判定部３０５は、接続先情報取得部３０１で取得される接続先のノードがゴールノードであるか否かを、パス情報記憶部２０１を参照して、判定する。ゴールノード（ノードＩＤ、Ｇ）であると判定した場合には、処理を終了する。一方、ゴールノードでないと判定した場合には、後述するように処理を継続する。
【００３６】
進行可能コース情報判定部３０６は、取得された進行可能コース情報と同一のノードＩＤ、及び、エッジＩＤを含む確定コース情報が既に確定コース情報記憶部２０７に記憶されているか否かを判定する。記憶されていると判定した場合には、当該進行可能コース情報は、登録コース情報設定部２０９に送信しない。一方、記憶されていないと判定した場合には、当該進行可能コース情報を登録コース情報設定部２０９に送信する。なお、当該登録コース情報設定部２０９の機能的な構成については後述する。例えば、図４Ｎに示した場合、確定コース情報Ｃ−Ｅ６、コスト：１１、ＩＮ：Ｅ２の接続先ノードＥとノードＥからのエッジＥ５、Ｅ６で示されるコース情報コースＥ−Ｅ５及びＥ−Ｅ６が得られるが、当該コース情報は、既に確定コース情報記憶部２０７に記憶されている（確定済みである）ことから、登録コース情報記憶部２０５に記憶されることはない。
【００３７】
上記のようにして、進行可能コース情報取得部２０８は、接続先情報取得部３０１で取得されたノードＩＤ、エッジ情報取得部３０２で取得されたエッジＩＤ、コスト算出部３０３で算出された累積コスト、進入元エッジＩＤ、進入元エッジＩＤを、１または複数の進行可能コース情報として取得する。例えば、上記例の場合、進行可能コース情報として、Ａ−Ｅ１、コスト、１、ＩＮ：Ｅ０、及び、Ａ−Ｅ４、コスト、１、ＩＮ：Ｅ０を取得する。なお、当該進行可能コース情報の形式は、コース情報の形式と同様であるとはいうまでもない。
【００３８】
登録コース情報設定部２０９は、上記進行可能コース情報及び登録コース情報記憶部２０５に記憶されている登録コース情報に基づいて、進行可能コース情報を登録コース情報記憶部２０５に記憶させる。以下、図９を用いて、具体的に説明する。図９は、登録コース情報設定部２０９の機能的構成について説明するための図である。図９に示すように、登録コース情報設定部２０９は、同一コース判定部４０１、累積コスト判定部４０２を有する。
【００３９】
同一コース判定部４０１は、進行可能コース情報に含まれるノードＩＤ及びエッジＩＤに基づき、登録コース情報記憶部２０５を参照して、当該ノードＩＤ及びエッジＩＤと同一のノードＩＤ及びエッジＩＤを有するコース情報が登録コース情報記憶部２０５に記憶されているか否かを判定する。そして、記憶されていないと判定した場合には、当該進行可能コース情報を登録コース情報記憶部２０５に新たに追加して記憶する。
【００４０】
例えば、上記例の場合、進行可能コース情報Ａ−Ｅ１、コスト、１、ＩＮ：Ｅ０、及び、Ａ−Ｅ４、コスト、１、ＩＮ：Ｅ０と同一のノードＩＤ及びエッジＩＤは、登録コース情報記憶部２０５に記憶されていないため、当該２の進行可能コース情報が登録コース情報記憶部２０５に記憶される。この場合の様子を、図４Ｂに示した。
【００４１】
一方、記憶されていると判定した場合には、累積コスト判定部４０２は、当該進行可能コース情報に含まれる累積コスト情報が、同一のノードＩＤ及びエッジＩＤを有するコース情報の累積コスト情報より、小さいか否かを判定する。そして、小さいと判定した場合には、当該コース情報に代えて、当該進行可能コース情報を記憶する。なお、ここで、当該コース情報を当該進行可能コース情報に更新する構成としてもよいことはいうまでもない。
【００４２】
一方、累積コスト判定部４０２は、当該進行可能コース情報に含まれる累積コスト情報が、同一のノードＩＤ及びエッジＩＤを有するコース情報の累積コスト情報以上であると判定した場合には、上記コース情報の更新等は行わない。つまり、登録コース情報記憶部２０５に記憶されている登録コース情報は、変更・更新されない。例えば、図４Ｅに示した場合、進行可能コース情報はＤ−Ｅ５、コスト：５、ＩＮ：Ｅ３が取得されるが、確定コース情報として、Ｄ−Ｅ５、コスト：５、ＩＮ：Ｅ４が記憶されていることから、当該確定コース情報の更新等は行われない。
【００４３】
なお、上記で示した構成は一例であって、これに限定されるものではない。例えば、上記で示した構成と実質的に同一の構成、同一の作用効果を奏する構成又は同一の目的を達成することができる構成で置き換えることができる。
【００４４】
次に、本実施の形態における最短経路探索装置１００の処理のフローについて説明する。図１０は、本実施の形態における最短経路探索装置の処理のフローについて説明するための図である。
【００４５】
初期コース情報設定部２０４は、スタート時におけるコース情報（初期コース情報）を設定し（Ｓ１０１）、登録コース情報記憶部２０５に記憶する（Ｓ１０２）。
【００４６】
登録コース情報記憶部２０５は、スタート時には、上記のように初期コース情報を登録コース情報として記憶する。また、後述するＳ１０６で進行可能コース情報と同一ノードＩＤ及びエッジＩＤを含む登録コース情報が登録コース情報記憶部２０５に含まれていないと判定された場合には、当該進行可能コース情報を記憶する。更に、後述するＳ１０７で進行可能コース情報に含まれる累積コストが、進行可能コース情報と同一のノードＩＤ及びエッジＩＤを含む登録コース情報の累積コストが小さいと判定された場合には、当該進行可能コース情報を当該進行可能コース情報に代えて記憶等する（Ｓ１０２）が、詳細には後述する。
【００４７】
最小登録コース情報抽出部２０６は、登録コース情報記憶部２０５に含まれる１または複数のコース情報（登録コース情報）のうち、最小の累積コスト情報を含む登録コース情報を抽出する（Ｓ１０３）。なお、上述のように複数の登録コース情報に含まれている累積コスト情報が同一の場合には、当該複数の登録コース情報のうちいずれかの登録コース情報を任意に抽出する。また、抽出された登録コース情報が登録コース情報記憶部２０５から削除されることは前述のとおりである。
【００４８】
確定コース情報記憶部２０７は、Ｓ１０３で抽出された登録コース情報を確定コース情報記憶部２０７に記憶する（Ｓ１０４）。進行可能コース情報記憶部は、Ｓ１０４で記憶された確定コース情報に基づいて、１または複数の進行可能コース情報を取得する（Ｓ１０５）。
【００４９】
同一コース判定部４０１は、進行可能コース情報と同一のノードＩＤ及びエッジＩＤを含む登録コース情報が、登録コース情報記憶部２０５に含まれているか否かを判定する。含まれていると判定した場合には、Ｓ１０７に進む。一方、含まれていないと判定した場合には、当該進行可能コース情報を登録コース情報記憶部２０５に記憶させる（Ｓ１０６）。
【００５０】
累積コスト判定部４０２は、当該進行可能コース情報に含まれる累積コスト情報が、同一のノードＩＤ及びエッジＩＤを有するコース情報の累積コスト情報より、小さいか否かを判定する。小さいと判定した場合には、当該進行可能コース情報を、当該同一のノードＩＤ及びエッジＩＤを有するコース情報に代えて、登録コース情報記憶部２０５に記憶させる。一方、小さくないと判定した場合には、Ｓ１０３に戻る（Ｓ１０７）。
【００５１】
次に、上記Ｓ１０５について、図１１を用いてより詳細に説明する。接続先情報取得部３０１は、確定コース情報に基づき、確定コースの接続先のノードＩＤを取得する（Ｓ２０１）。ゴール判定部が、Ｓ２０１で取得されたノードＩＤがゴールノードを示すＩＤ、Ｇである場合には、処理を終了する。一方、Ｓ２０１で取得されたノードＩＤがゴールノードを示すＩＤ、Ｇでない場合には、Ｓ２０３に進む（Ｓ２０２）。
【００５２】
エッジ情報取得部３０２は、上記取得された接続先ノードのノードＩＤ、確定コース情報に含まれるエッジＩＤ、進行可否情報記憶部２０２に記憶された進行可否情報に基づいて、進行可能なエッジ情報を取得する（Ｓ２０３）。進行可能コース情報判定部３０６は、Ｓ２０１とＳ２０３で取得されたノードＩＤ及びエッジＩＤと、同一のノードＩＤ、及び、エッジＩＤを含む確定コース情報が既に確定コース情報記憶部２０７に記憶されているか否かを判定する（Ｓ２０４）。記憶されていると判定した場合には、Ｓ１０３に進む。一方、記憶されていないと判定した場合には、Ｓ２０５に進む。
【００５３】
コスト算出部３０３は、確定コース情報に含まれる累積コスト情報を取得するとともに、確定コース情報に含まれるエッジＩＤを取得する。そして、当該エッジＩＤに基づいて、コスト情報記憶部２０３を参照し、当該エッジＩＤに関連して記憶されているコスト情報を取得し、当該コスト情報と上記確定コース情報に含まれている累積コストの和を算出する（Ｓ２０５）。進入元エッジ情報取得部３０４は、確定コース情報に含まれるエッジＩＤを進入元エッジ情報として取得する（Ｓ２０６）。
【００５４】
上記のように、Ｓ１０５においては、進行可能コース情報取得部２０８は、Ｓ２０１で取得されたノードＩＤ、Ｓ２０３で取得されたエッジＩＤ、Ｓ２０４で算出された累積コスト、Ｓ２０５で取得された進入元エッジＩＤを、１または複数の進行可能コース情報として取得する。なお、上記図１０及び図１１に示したフローは、一例であって、上記フローと実質的に同一のフロー、同一の作用効果を奏するフロー又は同一の目的を達成することができるフローで置き換えることができる。
【００５５】
次に、本実施の形態における最短経路探索装置１００の処理のフローの具体例として、図４Ａ乃至図４Ｏを用いて説明する。なお、この場合における経路は、図３に示したものであることは前述のとおりである。
【００５６】
まず、スタート時においては、図４Ａに示すように、初期コース情報設定部２０４は、スタート時におけるコース情報、Ｓ−Ｅ０、コスト：０、ＩＮ：−を設定し、登録コース情報記憶部２０５に記憶させる。
【００５７】
次に、図４Ｂに示すように、最小登録コース情報抽出部２０６は、登録コース情報記憶部２０５に記憶されたコース情報、Ｓ−Ｅ０、コスト：０、ＩＮ：−を抽出し、確定コース情報記憶部２０７に記憶するとともに、登録コース情報記憶部２０５から削除する。なお、この場合、登録コース情報記憶部２０５には、上記１のコース情報のみしか記憶されていないことから、上記コース情報を抽出することはいうまでもない。
【００５８】
また、進行可能コース情報取得部２０８は、コース情報、Ｓ−Ｅ０、コスト：０、ＩＮ：−に基づいて、当該確定コース情報で示されるコース（確定コース）の次に進行可能なコースを示す進行可能コース情報Ａ−Ｅ１、コスト：１、ＩＮ：Ｅ０及びＡ−Ｅ４、コスト：１、ＩＮ：Ｅ０を取得する。なお、この場合、登録コース情報記憶部２０５には、コース情報が記憶されていないことから、当該２の進行可能コース情報が、登録コース情報として、登録コース情報記憶部２０５に記憶される。
【００５９】
次に、最小登録コース情報抽出部２０６は、最小の累積コスト情報を含む登録コース情報を抽出する。なお、ここでは、登録可能コース情報Ａ−Ｅ１、コスト：１、ＩＮ：Ｅ０、及び、Ａ−Ｅ４、コスト：１、ＩＮ：Ｅ０は、いずれの累積コスト情報が同じ１であることから、最小登録コース情報抽出部２０６は、いずれの登録コース情報を抽出してもよい。よって、ここでは、最小登録コース情報抽出部２０６が、登録コース情報Ａ−Ｅ１、コスト：１、ＩＮ：Ｅ０が抽出したものとして説明する。
【００６０】
次に、図４Ｃに示すように、上記抽出された登録コース情報Ａ−Ｅ１、コスト：１、ＩＮ：Ｅ０が、確定コース情報記憶部２０７に、確定コース情報として、確定コース情報、Ｓ−Ｅ０、コスト：０、ＩＮ：０に追加して、記憶されるとともに、登録コース情報記憶部２０５から削除される。また、進行可能コース情報取得部２０８は、確定コース情報Ａ−Ｅ１、コスト：１、ＩＮ：Ｅ０に基づいて、進行可能コース情報Ｂ−Ｅ３、コスト：４、ＩＮ：Ｅ１を取得する。
【００６１】
具体的には、確定コース情報に含まれるＡ−Ｅ１の接続先はノードＢであり、進行可否情報によりエッジＥ１及びＥ２はノードＢを介して進行不可であることから、進行可能コース情報のノードＩＤはＢとなり、エッジ情報はＥ３となる。また、進行可能コース情報の累積コスト情報は、確定コース情報Ａ−Ｅ１、コスト：１、ＩＮ：Ｅ０に含まれる累積コスト情報１に、エッジＩＤ、Ｅ１のコスト３を加算して、４となる。また、進入元エッジＩＤは、確定コース情報に含まれるエッジＩＤ、Ｅ１より、Ｅ１となる。また、登録コース情報記憶部２０５には、ノードＩＤ、ＢかつエッジＩＤ、Ｅ３を有する登録コース情報は含まれていないことから、当該進行可能コース情報Ｂ−Ｅ３、コスト：４、ＩＮ：Ｅ１を登録コース情報として、登録コース情報記憶部２０５に追加して記憶する。次に、最小登録コース情報抽出部２０６は、登録コース情報記憶部２０５に記憶されている登録コース情報のうち最小のコスト情報を有する登録コース情報、つまり、Ａ−Ｅ４、コスト：１、ＩＮ：Ｅ０を抽出する。
【００６２】
次に、図４Ｄに示すように、上記抽出された登録コース情報Ａ−Ｅ４、コスト：１、ＩＮ：Ｅ０が、確定コース情報記憶部２０７に、確定コース情報として、追加して、記憶されるとともに、登録コース情報記憶部２０５から削除される。また、進行可能コース情報取得部２０８は、確定コース情報Ａ−Ｅ４、コスト：１、ＩＮ：Ｅ０に基づいて、進行可能コース情報Ｄ−Ｅ５、コスト：５、ＩＮ：Ｅ４を取得する。
【００６３】
具体的には、確定コース情報に含まれるＡ−Ｅ４の接続先はノードＤであり、Ｅ３及びＥ４はノードＤを介して進行不可であることから、進行可能コース情報のノードＩＤはＤとなり、エッジ情報はＥ５となる。また、進行可能コース情報の累積コスト情報は、確定コース情報Ａ−Ｅ４、コスト：１、ＩＮ：Ｅ０に含まれる累積コスト情報１に、エッジＩＤ、Ｅ４のコスト４を加算して、５となる。また、進入元エッジＩＤは、確定コース情報に含まれるエッジＩＤ、Ｅ４より、Ｅ４となる。また、登録コース情報記憶部２０５には、ノードＩＤ、ＤかつエッジＩＤ、Ｅ５を有する登録コース情報は含まれていないことから、当該進行可能コース情報Ｄ−Ｅ５、コスト：５、ＩＮ：Ｅ４を登録コース情報として、登録コース情報記憶部２０５に追加して記憶する。
【００６４】
次に、最小登録コース情報抽出部２０６は、登録コース情報記憶部２０５に記憶されている登録コース情報のうち最小のコスト情報を有する登録コース情報、つまり、Ｂ−Ｅ３、コスト：４、ＩＮ：Ｅ１を抽出する。
【００６５】
次に、図４Ｅに示すように、上記抽出された登録コース情報Ｂ−Ｅ３、コスト：４、ＩＮ：Ｅ１が、確定コース情報記憶部２０７に、確定コース情報として、追加して、記憶されるとともに、登録コース情報記憶部２０５から削除される。また、進行可能コース情報取得部２０８は、同様にして、確定コース情報Ｂ−Ｅ３、コスト：４、ＩＮ：Ｅ１に基づいて、進行可能コース情報Ｄ−Ｅ５、コスト：６、ＩＮ：Ｅ４を取得する。
【００６６】
しかしながら、登録コース情報記憶部２０５には、ノードＩＤ、ＤかつエッジＩＤ、Ｅ５を有する登録コース情報Ｄ−Ｅ５、コスト：５、ＩＮ：Ｅ４（同一コース情報）が既に含まれている。したがって、上記進行可能コース情報の累積コスト情報が、当該同一コース情報の累積コスト情報より小さいか否かを判定する。この場合、進行可能コース情報の累積コスト情報が同一コース情報の累積コスト情報以上であるので、変更はされない。
【００６７】
次に、最小登録コース情報抽出部２０６は、登録コース情報記憶部２０５に記憶されている登録コース情報のうち最小のコスト情報を有する登録コース情報、つまり、Ｄ−Ｅ５、コスト：５、ＩＮ：Ｅ４を抽出する。
【００６８】
以下、同様に、図４Ｆに示すように、最小登録コース情報抽出部２０６により、抽出された登録コース情報Ｄ−Ｅ５、コスト：５、ＩＮ：Ｅ４が、確定コース情報記憶部２０７に、確定コース情報として、追加して、記憶されるとともに、登録コース情報記憶部２０５から削除される。また、登録コース情報記憶部２０５には、進行可能コース情報Ｅ−Ｅ５、コスト：６、ＩＮ：Ｅ５、及び、進行可能コース情報Ｅ−Ｅ６、コスト：６、ＩＮ：Ｅ５が、登録コース情報として、登録コース情報記憶部２０５に追加して記憶される。
【００６９】
次に、図４Ｇに示すように、最小登録コース情報抽出部２０６により、抽出された登録コース情報Ｅ−Ｅ５、コスト：６、ＩＮ：Ｅ５が、確定コース情報記憶部２０７に、確定コース情報として、追加して、記憶されるとともに、登録コース情報記憶部２０５から削除される。また、登録コース情報記憶部２０５には、進行可能コース情報Ｄ−Ｅ３、コスト：７、ＩＮ：Ｅ５、及び、進行可能コース情報Ｄ−Ｅ４、コスト：７、ＩＮ：Ｅ５が、登録コース情報として、登録コース情報記憶部２０５に追加して記憶される。
【００７０】
次に、図４Ｈに示すように、最小登録コース情報抽出部２０６により、抽出された登録コース情報Ｅ−Ｅ６、コスト：６、ＩＮ：Ｅ５が、確定コース情報記憶部２０７に、確定コース情報として、追加して、記憶されるとともに、登録コース情報記憶部２０５から削除される。また、登録コース情報記憶部２０５には、進行可能コース情報Ｃ−Ｅ２、コスト：１６、ＩＮ：Ｅ６、及び、進行可能コース情報Ｃ−Ｅ７、コスト：１６、ＩＮ：Ｅ６が、登録コース情報として、登録コース情報記憶部２０５に追加して記憶される。
【００７１】
次に、図４Ｉに示すように、最小登録コース情報抽出部２０６により、抽出された登録コース情報Ｄ−Ｅ３、コスト：７、ＩＮ：Ｅ５が、確定コース情報記憶部２０７に、確定コース情報として、追加して、記憶されるとともに、登録コース情報記憶部２０５から削除される。また、登録コース情報記憶部２０５には、進行可能コース情報Ｂ−Ｅ１、コスト：９、ＩＮ：Ｅ３、及び、進行可能コース情報Ｂ−Ｅ２、コスト：９、ＩＮ：Ｅ３が、登録コース情報として、登録コース情報記憶部２０５に追加して記憶される。
【００７２】
次に、図４Ｊに示すように、最小登録コース情報抽出部２０６により、抽出された登録コース情報Ｄ−Ｅ４、コスト：７、ＩＮ：Ｅ５が、確定コース情報記憶部２０７に、確定コース情報として、追加して、記憶されるとともに、登録コース情報記憶部２０５から削除される。また、登録コース情報記憶部２０５には、進行可能コース情報Ａ−Ｅ０、コスト：１１、ＩＮ：Ｅ４が、登録コース情報として、登録コース情報記憶部２０５に追加して記憶される。
【００７３】
次に、図４Ｋに示すように、最小登録コース情報抽出部２０６により、抽出された登録コース情報Ｂ−Ｅ１、コスト：９、ＩＮ：Ｅ３が、確定コース情報記憶部２０７に、確定コース情報として、追加して、記憶されるとともに、登録コース情報記憶部２０５から削除される。なお、ここで、進行可能コース情報Ａ−Ｅ０、コスト：１２、ＩＮ：Ｅ１が取得されるが、登録コース情報Ａ−Ｅ０、コスト：１１、ＩＮ：Ｅ４が、登録コース情報記憶部２０５に記憶されていることから、当該登録コース情報は変更されない。
【００７４】
次に、図４Ｌに示すように、最小登録コース情報抽出部２０６により、抽出された登録コース情報Ｂ−Ｅ２、コスト：９、ＩＮ：Ｅ３が、確定コース情報記憶部２０７に、確定コース情報として、追加して、記憶されるとともに、登録コース情報記憶部２０５から削除される。また、登録コース情報記憶部２０５には、進行可能コース情報Ｃ−Ｅ６、コスト：１１、ＩＮ：Ｅ２が、登録コース情報として、登録コース情報記憶部２０５に追加して記憶されるとともに、登録コース情報Ｃ−Ｅ７、コスト：１６、ＩＮ：Ｅ６が、取得された進行可能コース情報Ｃ−Ｅ７、コスト：１１、ＩＮ：Ｅ２に変更される。
【００７５】
次に、図４Ｍに示すように、最小登録コース情報抽出部２０６により、抽出された登録コース情報Ａ−Ｅ０、コスト：１１、ＩＮ：Ｅ４が、確定コース情報記憶部２０７に、確定コース情報として、追加して、記憶されるとともに、登録コース情報記憶部２０５から削除される。また、登録コース情報記憶部２０５の内容に変更はない。進行可否情報より、スタートノードではターンできないからである。
【００７６】
次に、図４Ｎに示すように、最小登録コース情報抽出部２０６により、抽出された登録コース情報Ｃ−Ｅ６、コスト：１１、ＩＮ：Ｅ２が、確定コース情報記憶部２０７に、確定コース情報として、追加して、記憶されるとともに、登録コース情報記憶部２０５から削除される。なお、このとき、確定コース情報Ｃ−Ｅ６、コスト：１１、ＩＮ：Ｅ２の接続先ノードＥとノードＥからのエッジＥ５、Ｅ６で示されるコースＥ−Ｅ５及びＥ−Ｅ６は、既に確定コース情報記憶部２０７に記憶されていることから、Ｅ−Ｅ５やＥ−Ｅ６のコースについての進行可能コース情報が生成され、登録コース情報記憶部２０５に記憶されることはない。
【００７７】
次に、図４Ｏに示すように、最小登録コース情報抽出部２０６により、抽出された登録コース情報Ｃ−Ｅ７、コスト：１１、ＩＮ：Ｅ２が、確定コース情報記憶部２０７に、確定コース情報として、追加して、記憶されるとともに、登録コース情報記憶部２０５から削除される。なお、このとき、登録コース情報Ｃ−Ｅ７、コスト：１１、ＩＮ：Ｅ２の接続先のノードはゴールノードであることから、処理が終了する。
【００７８】
以上より、確定コース情報記憶部２０７に確定コース情報が記憶され、最短経路が求められる。具体的には、確定コース情報記憶部２０７に記憶された確定コース情報のエッジ情報と、進入元エッジ情報を新たに記憶された順（図４の下から上に向かう順序）に参照することにより、最短経路を求めることができる。例えば、図４Ｏの場合、最後に記憶された確定コース情報のエッジ情報Ｅ７で進入元エッジ情報はＥ２である。エッジ情報Ｅ２を有する確定コース情報はＢ−Ｅ２、コスト：９、ＩＮ：Ｅ３であり、進入元エッジ情報はＥ３である。したがって、ゴールノードかららＥ７、Ｅ２、Ｅ３の順に最短経路を決定することができる。以下同様にして、エッジＩＤ、Ｇ（ゴールノードに相当）から順に、Ｅ７、Ｅ２、Ｅ３、Ｅ５、Ｅ５、Ｅ４、Ｅ０、Ｓ（スタートノードに相当）の最短経路が求められる。なお、図１２に、このようにして求められた最短経路を示す図である。
【００７９】
上記のように構成することで、ＣＧ（Computer Graphics）やゲームプログラム等で実現される仮想空間内における経路において、あるノードに相当する場所では、対象物を転回（ターン）可能とするとともに、当該経路の最短経路を求めることができる。
【００８０】
また、上記のような仮想空間において、ある程度の長さを有する対象物、例えば、電車や胴体の長い動物など、を上記経路に沿って移動させる場合であって、あるノードで接続される一方のエッジと他方のエッジの角度が所定の角度以下である場合には、通常では当該対象物が曲がらないような不自然な角度で対象物が曲がりつつ、当該一方のエッジと他方のエッジを通過してしまう場合もある。この場合、ノードに接続される一方のエッジと他方のエッジとの角度が所定の角度以下である場合には、当該ノードを当該一方のエッジと他方のエッジとの間を通過不可と設定することにより、最短経路を探索する際に当該ノードを当該一方のエッジと他方のエッジとの間の通過を避けた最短経路を求めることができる。これにより、上記のような対象物が、不自然な角度に折れ曲がりつつ進行するような経路の設定を避けることができ、結果として、上記のような対象物の不自然な移動の表示を避けることができる。また、当該経路に沿って、建物や壁が配置されること等により、当該一方のエッジと当該他方のエッジとの角度が所定の角度以下である場合には、狭い場所に配置された建物等にめり込んで進行するような経路の設定を避けることができる。
【００８１】
なお、本発明は、上記実施の形態に限定されるものではなく、種々の変形が可能である。例えば、上記実施の形態で示した構成と実質的に同一の構成、同一の作用効果を奏する構成又は同一の目的を達成することができる構成で置き換えることができる。具体的には、例えば、上記最短経路探索装置１００は、更に、仮想空間内に配置された経路に沿って対象物を移動させる対象物移動制御部や、当該対象物を仮想空間内に表示させる画像を生成する画像生成部等と組み合わせて、仮想空間において当該対象物を上記最短経路探索装置１００によって求められた経路に沿って移動させる動画像を生成する動画像生成装置や、仮想空間において、上記経路に沿って、キャラクタ（上記対象物に相当する）を移動させるゲーム装置として用いてもよい。更に、当該動画像生成装置またはゲーム装置と、表示部１０５とを組み合わせて、当該表示部１０５に表示される仮想空間において、上記経路に沿って、キャラクタ（上記対象物に相当する）を移動させる動画像を表示させるように構成してもよい。
【符号の説明】
【００８２】
１００最短経路探索装置、１０１制御部、１０２記憶部、１０３通信部、１０４操作部、１０５表示部、１０６内部バス、２０１パス情報記憶部、２０２進行可否情報記憶部、２０３コスト情報記憶部、２０４初期コース情報設定部、２０５登録コース情報記憶部、２０６最小登録コース情報抽出部、２０７確定コース情報記憶部、２０８進行可能コース情報取得部、２０９登録コース情報設定部、３０１接続先情報取得部、３０２エッジ情報取得部、３０３コスト算出部、３０４進入元エッジ情報取得部、３０５ゴール判定部、４０１同一コース判定部、４０２累積コスト判定部。

【特許請求の範囲】
【請求項１】
複数のノードと、該複数のノード間を接続するとともに、通過する際のコストが関連付けられた複数のエッジとで形成された経路において、該複数のノードに含まれるスタートノードからゴールノードまでの最短経路を探索する最短経路探索プログラムであって、
前記各ノードに接続された１または複数のエッジ間の進行の可否を示す進行可否識別情報が、前記各ノードを識別するノード識別情報と、前記各エッジを識別するエッジ識別情報と、に関連付けて記憶された進行可否情報を取得する進行可否情報取得手段、及び、
前記進行可否情報及び前記各エッジに関連付けられたコストに基づいて、前記スタートノードから前記ゴールノードまでの最短経路を取得する最短経路取得手段、
としてコンピュータを機能させるための最短経路探索プログラム。
【請求項２】
前記最短経路取得手段において、更に、
前記ノード識別情報、前記エッジ識別情報、該エッジ識別情報で識別されるエッジに到達するまでの累積コストを示す累積コスト情報、該エッジに進入してきた進入元のエッジを示す進入元エッジ情報を含む１または複数のコース情報を、登録コース情報として、記憶する登録コース情報記憶手段、
前記登録コース情報記憶手段に記憶された１または複数の登録コース情報のうち、最小の累積コスト情報を含む登録コース情報を抽出する最小登録コース情報抽出手段、
前記抽出された登録コース情報を、確定コース情報として、確定コース情報記憶手段に追加して記憶する確定コース情報記憶手段、
前記進行可否情報に基づいて、前記追加して記憶された確定コース情報により示されるコースの次に進行可能なコースを示すコース情報である１または複数の進行可能コース情報を取得する進行可能コース情報取得手段、及び、
前記登録コース情報記憶手段に記憶された登録コース情報及び前記取得された１または複数の進行可能コース情報に基づいて、前記進行可能コース情報を登録コース情報として、前記登録コース情報記憶手段に追加して記憶、または、前記登録コース情報を更新する登録コース情報設定手段、
としてコンピュータを機能させるための請求項１記載の最短経路探索プログラム。
【請求項３】
前記最短経路探索プログラムは、更に、
初期の前記コース情報を設定するとともに、該初期のコース情報を、登録コース情報として、前記登録コース情報記憶手段に記憶させる初期コース情報設定手段、としてコンピュータを機能させるための請求項２記載の最短経路探索プログラム。
【請求項４】
前記進行可能コース情報取得手段は、前記確定コース情報に基づいて、前記１または複数の進行可能コース情報に含まれる累積コスト情報を算出するコスト算出手段を含むことを特徴とする請求項２または３記載の最短経路探索プログラム。
【請求項５】
前記進行可能コース情報取得手段は、前記確定コース情報記憶手段に記憶された確定コース情報と同一のノード識別情報及びエッジ識別情報以外のノード識別情報とエッジ識別情報を含む１または複数の進行可能コース情報を取得することを特徴とする請求項２乃至４のいずれかに記載の最短経路探索プログラム。
【請求項６】
前記登録コース情報設定手段は、前記取得された１または複数の進行可能コース情報の累積コスト情報が、前記取得された１または複数の進行可能コース情報と同一のノード識別情報とエッジ識別情報を含む前記登録コース情報の累積コスト情報より小さい場合には、前記取得された１または複数の進行可能コース情報に基づいて、前記取得された進行可能コース情報と同一のノード識別情報とエッジ識別情報を含む前記登録コース情報を更新することを特徴とする請求項２乃至５のいずれかに記載の最短経路探索プログラム。
【請求項７】
請求項１乃至６のいずれかに記載の最短経路探索プログラムを記憶したコンピュータ読み取り可能な記録媒体。
【請求項８】
複数のノードと、該複数のノード間を接続するとともに、通過する際のコストが関連付けられた複数のエッジとで形成された経路において、該複数のノードに含まれるスタートノードからゴールノードまでの最短経路を探索する最短経路探索装置であって、
前記各ノードに接続された１または複数のエッジ間の進行の可否を示す進行可否識別情報が、前記各ノードを識別するノード識別情報と、前記各エッジを識別するエッジ識別情報と、に関連付けて記憶された進行可否情報を取得する進行可否情報取得手段と、
前記進行可否情報及び前記各エッジに関連付けられたコストに基づいて、前記スタートノードから前記ゴールノードまでの最短経路を取得する最短経路取得手段と、
を有する最短経路探索装置。
【請求項９】
複数のノードと、該複数のノード間を接続するとともに、通過する際のコストが関連付けられた複数のエッジとで形成された経路において、該複数のノードに含まれるスタートノードからゴールノードまでの最短経路を探索する最短経路探索方法であって、
前記各ノードに接続された１または複数のエッジ間の進行の可否を示す進行可否識別情報が、前記各ノードを識別するノード識別情報と、前記各エッジを識別するエッジ識別情報と、に関連付けて記憶された進行可否情報を取得し、
前記進行可否情報及び前記各エッジに関連付けられたコストに基づいて、前記スタートノードから前記ゴールノードまでの最短経路を取得する、
ことを特徴とする最短経路探索方法。

【図１】