経路決定装置および経路決定方法
【課題】ノードがリンクを介して他の多くのノードと隣接している場合に、最短経路を決定するまでの時間が長くなってしまうのを回避する。
【解決手段】複数のノードを１つずつ始点ノードとして選択する選択部と、選択された始点ノードを、決定済みの最短経路の終点ノードとして認識し、その後、当該始点ノードから、決定済みの最短経路の終点ノードに隣接し、かつ、当該始点ノードからの最短経路が未決定のノードである未決定ノードまでの通信経路を最短経路候補とし、コスト値が最小の最短経路候補を最短経路として決定するとともに、決定した最短経路の終点ノードを、決定済みの最短経路の終点ノードとして新たに認識することを繰り返す決定部とを有し、決定部は、当該始点ノードから、未決定ノードのうち、決定済みの最短経路の終点ノードとの間のリンクに設定されたコスト値が最小である未決定ノードまでの通信経路を最短経路候補とする。
【解決手段】複数のノードを１つずつ始点ノードとして選択する選択部と、選択された始点ノードを、決定済みの最短経路の終点ノードとして認識し、その後、当該始点ノードから、決定済みの最短経路の終点ノードに隣接し、かつ、当該始点ノードからの最短経路が未決定のノードである未決定ノードまでの通信経路を最短経路候補とし、コスト値が最小の最短経路候補を最短経路として決定するとともに、決定した最短経路の終点ノードを、決定済みの最短経路の終点ノードとして新たに認識することを繰り返す決定部とを有し、決定部は、当該始点ノードから、未決定ノードのうち、決定済みの最短経路の終点ノードとの間のリンクに設定されたコスト値が最小である未決定ノードまでの通信経路を最短経路候補とする。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、複数のノードから構成される通信ネットワークにおける２つのノード間の最短経路を決定する経路決定装置および経路決定方法に関する。
【背景技術】
【０００２】
隣接するノードとリンクを介して接続された複数のノードで構成される通信ネットワークにおいては、その複数のノードのいずれかである始点ノードから、その複数のノードのうちの始点ノード以外のノードである終点ノードまで複数の通信経路が存在する場合がある。そのため、その複数の通信経路のうち、最も効率的な通信経路である最短経路を決定する必要がある。
【０００３】
そこで、リンクにコスト値と呼ばれる重み値を設定し、始点ノードから終点ノードまでの複数の通信経路のそれぞれのコスト値を計算することにより、コスト値が最小となる通信経路を最短経路として決定するのが一般的である。
【０００４】
上述したような計算によって最短経路を決定するためのアルゴリズムの１つであるダイクストラ法が例えば、非特許文献１に開示されている。
【０００５】
図８は、ダイクストラ法を用いて最短経路を決定する動作を説明するためのフローチャートである。
【０００６】
まず、通信ネットワークを構成する複数のノードのうち始点ノードとして選択されていないノードが存在するかどうかが確認される（ステップＳ１０１）。
【０００７】
ステップＳ１０１における確認の結果、始点ノードとして選択されていないノードが存在しない場合、処理が終了する。
【０００８】
一方、ステップＳ１０１における確認の結果、始点ノードとして選択されていないノードが存在する場合には、始点ノードとして選択されていないノードの１つが始点ノードとして選択される（ステップＳ１０２）。なお、始点ノードとして選択されたノードは、決定済みの最短経路の終点ノードとして認識される。
【０００９】
次に、決定済みの最短経路の終点ノードに隣接し、かつ、始点ノードからの最短経路が未決定のノードが存在する場合、始点ノードから、そのノードまでの通信経路が最短経路候補とされ、コスト値が計算される（ステップＳ１０３）。
【００１０】
次に、最短経路候補が存在するかどうかが確認される（ステップＳ１０４）。
【００１１】
ステップＳ１０４における確認の結果、最短経路候補が存在する場合、コスト値が最小の最短経路候補が最短経路として決定され（ステップＳ１０５）、ステップＳ１０３の動作へ遷移する。
【００１２】
一方、ステップＳ１０４における確認の結果、最短経路候補が存在しない場合にはステップＳ１０１の動作へ遷移する。
【００１３】
以降、ステップＳ１０１〜Ｓ１０５の動作が繰り返され、通信ネットワークを構成する複数のノードのそれぞれを始点ノードとした場合の最短経路が決定される。
【００１４】
図９〜図１１は、図８に示したフローチャートに従って最短経路を決定する動作の具体例を説明するための図であり、（ａ）は通信ネットワークの一例を示す図であり、（ｂ）は最短経路候補の一例を示す図である。ここでは、最短経路が決定されていく動作の具体例を図９〜図１１を順番に参照しながら説明する。
【００１５】
なお、図９（ａ）、図１０（ａ）および図１１（ａ）に示す通信ネットワークは同じものである。
【００１６】
また、図９（ａ）、図１０（ａ）および図１１（ａ）において、ノードは円で示されており、その円の中に記載されたアルファベットにより、通信ネットワークを構成する複数のノードのそれぞれが識別されている。以降、例えば円の中にＡと記載されたノードのことをノードＡという。また、通信経路を＜ ＞を用いて表記する。例えばノードＡからノードＢまでの通信経路の場合、＜Ａ→Ｂ＞と表記する。
【００１７】
また、図９（ａ）、図１０（ａ）および図１１（ａ）において、ノードを示す円と円との間の実線または破線がリンクを示しており、リンクの近傍の数字がそのリンクに設定されたコスト値を示している。
【００１８】
まず、上述したステップＳ１０１の動作に従い、通信ネットワークを構成するノードＡ〜Ｉのうち始点ノードとして選択されていないノードが存在するかどうかが確認される。ここでは、ノードＡ〜Ｉのいずれも始点ノードとして選択されていないものとする。
【００１９】
従って、上述したステップＳ１０２の動作に従い、ノードＡ〜Ｉのうちの１つが始点ノードとして選択される。ここでは、ノードＡが始点ノードとして選択されるものとする。これにより、ノードＡは決定済みの最短経路の終点ノードとして認識される。
【００２０】
次に、上述したステップＳ１０３の動作に従い、ノードＡに隣接し、かつ、ノードＡからの最短経路が未決定のノードへの通信経路が最短経路候補とされ、コスト値が計算される。ここでは、ノードＡに隣接し、かつ、ノードＡからの最短経路が未決定のノードは、ノードＢ、ノードＣおよびノードＤである。
【００２１】
従って、＜Ａ→Ｂ＞と、＜Ａ→Ｃ＞と、＜Ａ→Ｄ＞との３つが最短経路候補となる。ここまでに最短経路候補となっている通信経路が、図９（ｂ）に示され、また、図９（ａ）おいて実線で示されている。
【００２２】
次に、上述したステップＳ１０４の動作に従い、最短経路候補が存在するかどうかが確認される。ここでは、最短経路候補は、図９（ｂ）に示す３つである。つまり、最短経路候補が存在する。従って、上述したステップＳ１０５の動作に従い、この３つの最短経路候補うち、コスト値が最小の＜Ａ→Ｄ＞が最短経路として決定する。
【００２３】
次に、上述したステップＳ１０３の動作へ遷移し、ノードＤに隣接し、かつ、ノードＡからの最短経路が未決定のノードへの通信経路が最短経路候補とされ、コスト値が計算される。ここでは、ノードＤに隣接し、かつ、ノードＡからの最短経路が未決定のノードは、ノードＥ、ノードＦおよびノードＧである。
【００２４】
従って、既に最短経路候補となっている＜Ａ→Ｂ＞と、＜Ａ→Ｃ＞との２つに加え、＜Ａ→Ｄ→Ｅ＞と、＜Ａ→Ｄ→Ｆ＞と、＜Ａ→Ｄ→Ｇ＞との３つが最短経路候補となる。ここまでに最短経路候補となっている通信経路が、図１０（ｂ）に示され、また、図１０（ａ）において実線で示されている。なお、＜Ａ→Ｄ＞は最短経路として決定済みであるため最短経路候補からは除外されている。
【００２５】
次に、上述したステップＳ１０４の動作に従い、最短経路候補が存在するかどうかが確認される。ここでは、最短経路候補は、図１０（ｂ）に示す５つである。つまり、最短経路候補が存在する。従って、上述したステップＳ１０５の動作に従い、この５つの最短経路候補のうち、コスト値が最小の＜Ａ→Ｄ→Ｆ＞が最短経路として決定する。
【００２６】
次に、上述したステップＳ１０３の動作へ遷移し、ノードＦに隣接し、かつ、ノードＡからの最短経路が未決定のノードへの通信経路が最短経路候補とされ、コスト値が計算される。ここでは、ノードＦに隣接し、かつ、ノードＡからの最短経路が未決定のノードは、ノードＨおよびノードＩである。
【００２７】
従って、既に最短経路候補となっている＜Ａ→Ｂ＞と、＜Ａ→Ｃ＞と、＜Ａ→Ｄ→Ｅ＞と、＜Ａ→Ｄ→Ｇ＞との４つに加え、＜Ａ→Ｄ→Ｆ→Ｈ＞と、＜Ａ→Ｄ→Ｆ→Ｉ＞との２つが最短経路候補となる。ここまでに最短経路候補となっている通信経路が、図１１（ｂ）に示され、また、図１１（ａ）おいて実線で示されている。なお、＜Ａ→Ｄ→Ｆ＞は最短経路として決定済みであるため最短経路候補からは除外されている。
【００２８】
次に、上述したステップＳ１０４の動作に従い、最短経路候補が存在するかどうかが確認される。ここでは、最短経路候補は、図１１（ｂ）に示す６つである。つまり、最短経路候補が存在する。従って、上述したステップＳ１０５の動作に従い、この６つの最短経路候補うち、コスト値が最小の＜Ａ→Ｃ＞が最短経路として決定する。
【００２９】
ノードＡからノードＢ〜Ｉのそれぞれまでの最短経路が決定するまで、このような動作が繰り返し行われる。そして、ノードＡからノードＢ〜Ｉのそれぞれまでの最短経路が決定すると、ノードＢ〜Ｉのそれぞれを始点ノードとした場合の最短経路を決定する。そして、ノードＡ〜Ｉのすべてのノードを始点ノードとした場合の最短経路が決定すると、最短経路を決定する計算が終了する。
【先行技術文献】
【非特許文献】
【００３０】
【非特許文献１】Dijkstra, E. W. (1959). "A note on two problems in connexion with graphs".Numerische Mathematik 1:269-271
【発明の概要】
【発明が解決しようとする課題】
【００３１】
上述したダイクストラ法のようなアルゴリズムは、始点ノードから、決定済みの最短経路の終点ノードに隣接し、かつ、その始点ノードからの最短経路が未決定のノードまでの通信経路のすべてを最短経路候補として追加する。そのため、ノードがリンクを介して他の多くのノードと隣接している場合、最短経路候補の数が多くなる。この場合、コスト値が最小となる最短経路候補を決定する際の計算量が大きくなり、最短経路を決定するまでの時間が長くなってしまうという問題点がある。
【００３２】
本発明は、ノードがリンクを介して他の多くのノードと隣接している場合に、最短経路を決定するまでの時間が長くなってしまうのを回避することができる経路決定方法および経路決定装置を提供することを目的とする。
【課題を解決するための手段】
【００３３】
上記目的を達成するために本発明の経路決定装置は、隣接するノードとコスト値が設定されたリンクを介して接続された複数のノードのそれぞれから、該複数のノードのうち当該ノード以外のノードである終点ノードまでの最短経路を決定する経路決定装置であって、
前記複数のノードのそれぞれを１つずつ始点ノードとして選択する選択部と、
前記選択部にて選択された始点ノードを、決定済みの最短経路の終点ノードとして認識し、その後、当該始点ノードから、前記決定済みの最短経路の終点ノードに隣接し、かつ、当該始点ノードからの最短経路が未決定のノードである未決定ノードまでの通信経路を、最短経路の候補となる最短経路候補とし、該最短経路候補のうち、コスト値が最小の最短経路候補を最短経路として決定するとともに、該決定した最短経路の終点ノードを、前記決定済みの最短経路の終点ノードとして認識しているノードに代えて、前記決定済みの最短経路の終点ノードとして新たに認識することを繰り返す決定部と、を有し、
前記決定部は、当該始点ノードから、前記未決定ノードのうち、前記決定済みの最短経路の終点ノードとの間のリンクに設定されたコスト値が最小である未決定ノードまでの通信経路を前記最短経路候補とする。
【００３４】
また、上記目的を達成するために本発明の経路決定方法は、隣接するノードとコスト値が設定されたリンクを介して接続された複数のノードのそれぞれから、該複数のノードのうち当該ノード以外のノードである終点ノードまでの最短経路を決定する経路決定装置における経路決定方法であって、
前記複数のノードのそれぞれを１つずつ始点ノードとして選択する処理と、
前記選択した始点ノードを、決定済みの最短経路の終点ノードとして認識する処理と、
当該始点ノードから、前記決定済みの最短経路の終点ノードに隣接し、かつ、当該始点ノードからの最短経路が未決定のノードである未決定ノードまでの通信経路を、最短経路の候補となる最短経路候補とし、該最短経路候補のうち、コスト値が最小の最短経路候補を最短経路として決定するとともに、該決定した最短経路の終点ノードを、前記決定済みの最短経路の終点ノードとして認識しているノードに代えて、前記決定済みの最短経路の終点ノードとして新たに認識することを繰り返す決定処理と、を有し、
前記決定処理では、当該始点ノードから、前記未決定ノードのうち、前記決定済みの最短経路の終点ノードとの間のリンクに設定されたコスト値が最小である未決定ノードまでの通信経路を前記最短経路候補とする。
【発明の効果】
【００３５】
本発明は以上説明したように構成されているので、始点ノードから、決定済みの最短経路の終点ノードに隣接し、かつ、その始点ノードからの最短経路が未決定のノードへの通信経路のすべてを最短経路候補に追加することがなくなる。
【００３６】
そのため、最短経路候補の数が抑制され、コスト値が最小となる最短経路を決定する際の計算量を少なくすることができる。
【００３７】
従って、ノードがリンクを介して他の多くのノードと隣接している場合に、最短経路を決定するまでの時間が長くなってしまうのを回避することができる。
【図面の簡単な説明】
【００３８】
【図１】ダイクストラ法のアルゴリズムの性質を説明するための図である。
【図２】本発明の経路決定装置の実施の一形態の構成を示すブロック図である。
【図３】図２に示した経路決定装置が最短経路を決定する動作を説明するためのフローチャートである。
【図４】図２に示した経路決定装置が最短経路を決定する動作の詳細を説明するためのフローチャートである。
【図５】図３および図４に示したフローチャートに従って、経路決定装置が最短経路を決定する動作の具体例を説明するための図である。
【図６】図３および図４に示したフローチャートに従って、経路決定装置が最短経路を決定する動作の具体例を説明するための図である。
【図７】図３および図４に示したフローチャートに従って、経路決定装置が最短経路を決定する動作の具体例を説明するための図である。
【図８】ダイクストラ法を用いて最短経路を決定する動作を説明するためのフローチャートである。
【図９】図８に示したフローチャートに従って最短経路を決定する動作の具体例を説明するための図であり、（ａ）は通信ネットワークの一例を示す図であり、（ｂ）は最短経路候補の一例を示す図である。
【図１０】図８に示したフローチャートに従って最短経路を決定する動作の具体例を説明するための図であり、（ａ）は通信ネットワークの一例を示す図であり、（ｂ）は最短経路候補の一例を示す図である。
【図１１】図８に示したフローチャートに従って最短経路を決定する動作の具体例を説明するための図であり、（ａ）は通信ネットワークの一例を示す図であり、（ｂ）は最短経路候補の一例を示す図である。
【発明を実施するための形態】
【００３９】
以下に、本発明の実施の形態について図面を参照して説明するが、その前に、上述したダイクストラ法のアルゴリズムの性質について説明する。
【００４０】
図１は、ダイクストラ法のアルゴリズムの性質を説明するための図である。なお、ここでは、上述した図９（ａ）、図１０（ａ）および図１１（ａ）に示した通信ネットワークを構成する複数のノードおよびコスト値に基づいて説明する。
【００４１】
図１（ａ）、図１（ｂ）および図１（ｄ）、図１（ｅ）、図１（ｆ）は、図９〜図１１を参照しながら説明した動作において決定した最短経路の終点ノードから、その終点ノードとリンクを介して隣接するノードまでの通信経路を、コスト値が小さな順番に並べたものである。
【００４２】
具体的には、図１（ａ）および図１（ｄ）は、ノードＡと、ノードＡとリンクを介して隣接するノードとの間の通信経路を、コスト値が小さな順番に並べて記載したものである。また、図１（ｂ）および図１（ｅ）は、ノードＤと、ノードＤとリンクを介して隣接するノードとの間の通信経路を、コスト値が小さな順番に並べて記載したものである。また、図１（ｆ）は、ノードＦと、ノードＦとリンクを介して隣接するノードとの間の通信経路を、コスト値が小さな順番に並べて記載したものである。
【００４３】
まず、＜Ａ→Ｄ＞が最短経路として決定した場合、図１（ａ）および図１（ｂ）の図中網掛けされた通信経路は、決定済みの最短経路上のノードへの通信経路となるため、最短経路候補を検討する際の対象から除外される。
【００４４】
図１（ｃ）は、＜Ａ→Ｄ＞が最短経路として決定した後の最短経路候補をコスト値が小さな順番に並べたものである。
【００４５】
図１（ｃ）に示した最短経路候補のうち、ノードＡからノードＡに隣接するノードまでの最短経路候補の順番は、図１（ａ）に示した順番と同じである。すなわち、図１（ａ）および図１（ｃ）において、＜Ａ→Ｃ＞は＜Ａ→Ｂ＞よりも上位となっている。
【００４６】
また、図１（ｃ）に示した最短経路候補のうち、ノードＡからノードＤを介してノードＤに隣接するノードまでの最短経路候補の順番は、ノードＤからノードＤに隣接するノードまでの通信経路に着目すると、図１（ｂ）に示した順番と同じである。すなわち、図１（ｂ）において＜Ｄ→Ｆ＞は＜Ｄ→Ｇ＞および＜Ｄ→Ｅ＞よりも上位となり、図１（ｃ）において＜Ａ→Ｄ→Ｆ＞は＜Ａ→Ｄ→Ｇ＞および＜Ａ→Ｄ→Ｅ＞よりも上位となっている。また、図１（ｂ）において＜Ｄ→Ｇ＞は＜Ｄ→Ｅ＞よりも上位となり、図１（ｃ）において＜Ａ→Ｄ→Ｇ＞は＜Ａ→Ｄ→Ｅ＞よりも上位となっている。
【００４７】
次に、＜Ａ→Ｄ→Ｆ＞が最短経路として決定した場合、図１（ｄ）、図１（ｅ）および図１（ｆ）の図中網掛けされた通信経路は、決定済みの最短経路上のノードへの通信経路となるため、最短経路候補を検討する際の対象から除外される。
【００４８】
図１（ｇ）は、＜Ａ→Ｄ→Ｆ＞が最短経路として決定した後の最短経路候補をコスト値が小さな順番に並べたものである。
【００４９】
図１（ｇ）に示した最短経路候補のうち、ノードＡからノードＡに隣接するノードまでの最短経路候補の順番は、図１（ｄ）に示した順番と同じである。また、図１（ｇ）に示した最短経路候補のうち、ノードＡからノードＤを介してノードＤに隣接するノードまでの最短経路候補の順番は、ノードＤからノードＤに隣接するノードまでの通信経路に着目すると、図１（ｂ）に示した順番と同じである。
【００５０】
また、図１（ｇ）に示した最短経路候補のうち、ノードＡからノードＤとノードＦとを介してノードＦに隣接するノードまでの最短経路候補の順番は、ノードＦからノードＦに隣接するノードまでの通信経路に着目すると、図１（ｆ）に示した順番と同じである。すなわち、図１（ｆ）において＜Ｆ→Ｉ＞は＜Ｆ→Ｈ＞よりも上位となり、図１（ｇ）において＜Ａ→Ｄ→Ｆ→Ｉ＞は＜Ａ→Ｄ→Ｆ→Ｈ＞よりも上位となっている。
【００５１】
このように、新たに最短経路が決定して最短経路候補が追加されても最短経路候補は、決定済みの最短経路の終点ノード毎に見ると、その終点ノードとその終点ノードに隣接するノードとを接続するリンクに設定されたコスト値が小さな順番に並ぶことになる。すなわち、最短経路は、決定済みの最短経路の終点ノード毎に見ると、その終点ノードとその終点ノードに隣接するノードとを接続するリンクに設定されたコスト値が小さな順番に決定していくことになる。
【００５２】
これは、始点ノードから、決定済みの最短経路の終点ノードまでのコスト値が同じであり、その終点ノードと、その終点ノードに隣接し、かつ、始点ノードからの最短経路が未決定のノードとを接続するリンクに設定されたコスト値の差が、最短経路候補のコスト値の差となるためである。
【００５３】
従って、最短経路を決定する際には、始点ノードから、決定済みの最短経路の終点ノードに隣接し、かつ、始点ノードからの最短経路が未決定のノードのうち、その終点ノードとの間のリンクに設定されたコスト値が最小であるノードまでの通信経路だけを最短経路候補として追加すればよいことになる。本実施形態では、このようにして最短経路候補を追加していく。
【００５４】
図２は、本発明の経路決定装置の実施の一形態の構成を示すブロック図である。
【００５５】
本実施形態の経路決定装置は図２に示すように、記憶部１１と、選択部１２と、決定部１３とを備えている。
【００５６】
記憶部１１は、通信ネットワークを示すネットワーク構成情報を記憶する。なお、ネットワーク構成情報には、通信ネットワークを構成する複数のノードを示す情報と、リンクに設定されたコスト値を示す情報とが含まれている。
【００５７】
選択部１２は、決定部１３から出力された選択指示を受け付ける。なお、選択指示とは、記憶部１１に記憶されたネットワーク構成情報が示す通信ネットワークを構成する複数のノードのうちの１つを始点ノードとして選択させるための指示である。なお、以降、記憶部１１に記憶されたネットワーク構成情報が示す通信ネットワークを構成する複数のノードのことを単に、複数のノードという。選択部１２は、決定部１３から出力された選択指示を受け付けると、複数のノードのうち、始点ノードとして選択していないノードが存在するかどうかを確認する。なお、選択部１２は、決定部１３から出力された選択指示を受け付ける度に、この確認を実行する。確認の結果、複数のノードのうち、始点ノードとして選択していないノードが存在する場合、選択部１２は、始点ノードとして選択していないノードの１つを始点ノードとして選択する。そして、選択部１２は、選択した始点ノードを示す始点ノード情報を決定部１３へ出力する。
【００５８】
決定部１３は、複数のノードのそれぞれについて、コスト順番情報を生成する。コスト順番情報とは、ノードとそのノードとリンクを介して隣接するノードとの間の通信経路を、コスト値が小さな順番に並べた情報である。次に、決定部１３は、選択指示を選択部１２へ出力する。その後、決定部１３は、選択部１２から出力された始点ノード情報を受け付ける。そして、決定部１３は、受け付けた始点ノード情報が示す始点ノードから、複数のノードのうちその始点ノード以外のすべてのノードまでの最短経路を決定する。そして、決定部１３は、選択指示を選択部１２へ出力する。なお、決定部１３が最短経路を決定する動作の詳細については後述する。
【００５９】
以下に、上記のように構成された経路決定装置１０において最短経路を決定する動作について説明する。
【００６０】
図３は、図２に示した経路決定装置１０が最短経路を決定する動作を説明するためのフローチャートである。
【００６１】
まず、決定部１３は、複数のノードのそれぞれについて、コスト順番情報を生成する（ステップＳ１）。
【００６２】
そして、決定部１３は、選択部１２に選択指示を出力する。
【００６３】
決定部１３から出力された選択指示を受け付けた選択部１２は、複数のノードのうち、始点ノードとして選択していないノードが存在するかどうかを確認する（ステップＳ２）。
【００６４】
ステップＳ２における確認の結果、複数のノードのうち、始点ノードとして選択していないノードが存在しない場合、処理を終了する。
【００６５】
一方、ステップＳ２における確認の結果、複数のノードのうち、始点ノードとして選択していないノードが存在する場合、選択部１２は、始点ノードとして選択していないノードの１つを始点ノードとして選択する（ステップＳ３）。
【００６６】
そして、選択部１２は、選択した始点ノードを示す始点ノード情報を決定部１３へ出力する。
【００６７】
選択部１２から出力された始点ノード情報を受け付けた決定部１３は、受け付けた始点ノード情報が示す始点ノードから、複数のノードのうちその始点ノード以外のすべてのノードまでの最短経路を決定する（ステップＳ４）。
【００６８】
次に、決定部１３は、選択指示を選択部１２へ出力する。そして、ステップＳ２の動作へ遷移する。
【００６９】
以降、ステップＳ２〜Ｓ４の動作が繰り返され、複数のノードのそれぞれを始点ノードとした場合の最短経路が決定される。
【００７０】
次に、上述したステップＳ４において最短経路を決定する動作の詳細について説明する。
【００７１】
図４は、図２に示した経路決定装置１０が最短経路を決定する動作の詳細を説明するためのフローチャートである。なお、ここでは、決定済みの最短経路上でその決定済みの最短経路の終点ノードと始点ノード側で隣接するノードのことを、その終点ノードの親ノードと定義する。
【００７２】
まず、決定部１３は、受け付けた始点ノード情報が示す始点ノードを、決定済みの最短経路の終点ノードとして認識する（ステップＳ４１）。
【００７３】
次に、決定部１３は、決定済みの最短経路の終点ノードに隣接し、かつ、始点ノードからの最短経路が未決定のノードである未決定ノードが存在するかどうかを確認する（ステップＳ４２）。
【００７４】
ステップＳ４２における確認の結果、決定済みの最短経路の終点ノードに隣接し、かつ、始点ノードからの最短経路が未決定のノードが存在する場合、決定部１３は、その終点ノードのコスト順番情報に含まれる通信経路のうち、決定済みの最短経路上のノードへの通信経路を除いて最上位となる通信経路に、決定済みの最短経路を加えた通信経路を最短経路候補とし、コスト値を計算する（ステップＳ４３）。
【００７５】
次に、決定部１３は、決定済みの最短経路の終点ノードの親ノードに隣接し、かつ、始点ノードからの最短経路が未決定のノードが存在するかどうかを確認する（ステップＳ４４）。
【００７６】
ステップＳ４４における確認の結果、決定済みの最短経路の終点ノードの親ノードに隣接し、かつ、始点ノードからの最短経路が未決定のノードが存在する場合、決定部１３は、その親ノードのコスト順番情報に含まれる通信経路のうち、決定済みの最短経路上のノードへの通信経路を除いて最上位となる通信経路に、決定済みの最短経路のうち始点ノードからその親ノードまでの通信経路を加えた通信経路を最短経路候補とし、コスト値を計算する（ステップＳ４５）。
【００７７】
次に、決定部１３は、最短経路候補が存在するかどうかを確認する（ステップＳ４６）。
【００７８】
ステップＳ４６における確認の結果、最短経路候補が存在する場合、コスト値が最小の最短経路候補を最短経路として決定する（ステップＳ４７）。
【００７９】
次に、決定部１３は、決定済みの最短経路の終点ノードとして認識しているノードに代えて、ステップＳ４７にて決定した最短経路の終点ノードを、決定済みの最短経路の終点ノードとして新たに認識する（ステップＳ４８）。そして、ステップＳ４２の動作へ遷移する。
【００８０】
なお、ステップＳ４２における確認の結果、決定済みの最短経路の終点ノードに隣接し、かつ、始点ノードからの最短経路が未決定のノードが存在しない場合、ステップＳ４４の動作へ遷移する。
【００８１】
また、ステップＳ４４における確認の結果、決定済みの最短経路の終点ノードの親ノードに隣接し、かつ、始点ノードからの最短経路が未決定のノードが存在しない場合、ステップＳ４６の動作へ遷移する。
【００８２】
また、ステップＳ４６における確認の結果、最短経路候補が存在しない場合、処理を終了する。これは、すなわち、始点ノードから、複数のノードのうち始点ノード以外のすべてのノードまでの最短経路が決定している場合である。この場合、図３を参照しながら説明したステップＳ２の動作へ遷移することになる。
【００８３】
次に、図３および図４に示したフローチャートに従って、経路決定装置１０が最短経路を決定する動作の具体例について説明する。
【００８４】
図５〜図７は、図３および図４に示したフローチャートに従って、経路決定装置１０が最短経路を決定する動作の具体例を説明するための図である。ここでは、経路決定装置１０が最短経路を決定していく動作の具体例を図５〜図７を順番に参照しながら説明する。
【００８５】
なお、図５（ａ）、図６（ａ）および図７（ａ）は、記憶部１１に記憶されたネットワーク構成情報が示す通信ネットワークを示している。なお、この通信ネットワークは、図９（ａ）、図１０（ａ）および図１１（ａ）に示した通信ネットワークと同じ構成である。
【００８６】
また、図５（ｂ）、図６（ｂ）および図７（ｂ）はノードＡのコスト順番情報を示しており、図６（ｃ）および図７（ｃ）はノードＤのコスト順番情報を示しており、図７（ｄ）はノードＦのコスト順番情報を示している。
【００８７】
まず、上述したステップＳ１の動作に従い、決定部１３は、ノードＡ〜Ｉのそれぞれについてコスト順番情報を生成する。
【００８８】
次に、上述したステップＳ２の動作に従い、選択部１２は、ノードＡ〜Ｉのうち、始点ノードとして選択していないノードがあるかどうかを確認する。ここでは、ノードＡ〜Ｉのいずれも始点ノードとして選択されていないものとする。
【００８９】
従って、選択部１２は、上述したステップＳ３の動作に従い、ノードＡ〜Ｉのうちの１つを始点ノードとして選択する。ここでは、選択部１２は、ノードＡを始点ノードとして選択するものとする。
【００９０】
次に、上述したステップＳ４１の動作に従い、決定部１３は、ノードＡを、決定済みの最短経路の終点ノードとして認識する。
【００９１】
次に、上述したステップＳ４２の動作に従い、決定部１３は、ノードＡに隣接し、かつ、ノードＡからの最短経路が未決定のノードが存在するかどうかを確認する。ここでは、ノードＡに隣接し、かつ、ノードＡからの最短経路が未決定のノードは、ノードＢ、ノードＣおよびノードＤである。つまり、ノードＡに隣接し、かつ、ノードＡからの最短経路が未決定のノードが存在する。
【００９２】
従って、上述したステップＳ４３の動作に従い、決定部１３は、決定済みの最短経路の終点ノードのコスト順番情報に含まれる通信経路のうち、決定済みの最短経路上のノードへの通信経路を除いて最上位となる通信経路に、決定済みの最短経路を加えた通信経路を最短経路候補とし、コスト値を計算する。ここでは、決定済みの最短経路は存在しない。そのため、決定部１３は、図５（ｂ）に示したコスト順番情報において最上位である＜Ａ→Ｄ＞を最短経路候補とする。
【００９３】
次に、上述したステップＳ４４の動作に従い、決定部１３は、決定済みの最短経路の終点ノードの親ノードに隣接し、かつ、始点ノードからの最短経路が未決定のノードが存在するかどうかを確認する。ここでは、決定済みの最短経路の終点ノードはノードＡであるが、ノードＡは始点ノードでもあるため、親ノードは存在しない。そのため、親ノードに隣接し、かつ、始点ノードからの最短経路が未決定のノードは存在しない。従って、上述したステップＳ４６の動作へ遷移し、決定部１３は、最短経路候補が存在するかどうかを確認する。ここまでに最短経路候補となっている通信経路が、図５（ｃ）に示され、また、図５（ａ）おいて実線で示されている。
【００９４】
ここでは、最短経路候補は、図５（ｃ）に示す１つである。つまり、最短経路候補が存在する。従って、上述したステップＳ４７の動作に従い、決定部１３は、コスト値が最小の＜Ａ→Ｄ＞を最短経路として決定する。
【００９５】
次に、上述したステップＳ４８の動作に従い、決定部１３は、決定済みの最短経路の終点ノードとして認識しているノードに代えて、ステップＳ４７にて決定した最短経路の終点ノードを、決定済みの最短経路の終点ノードとして新たに認識する。ここでは、決定部１３は、ノードＡに代えて、ノードＤを決定済みの最短経路の終点ノードとして新たに認識する。
【００９６】
そして、上述したステップＳ４２の動作へ遷移し、決定部１３は、ノードＤに隣接し、かつ、ノードＡからの最短経路が未決定のノードが存在するかどうかを確認する。ここでは、ノードＤに隣接し、かつ、ノードＡからの最短経路が未決定のノードはノードＥ、ノードＦおよびノードＧである。つまり、ノードＤに隣接し、かつ、ノードＡからの最短経路が未決定のノードが存在する。
【００９７】
従って、上述したステップＳ４３の動作に従い、決定部１３は、決定済みの最短経路の終点ノードのコスト順番情報に含まれる通信経路のうち、決定済みの最短経路上のノードへの通信経路を除いて最上位となる通信経路に、決定済みの最短経路を加えた通信経路を最短経路候補とし、コスト値を計算する。ここでは、決定部１３は、図６（ｃ）に示したノードＤのコスト順番情報において、決定済みの最短経路上のノードへの通信経路である＜Ｄ→Ａ＞を除いて最上位となる＜Ｄ→Ｆ＞に、＜Ａ→Ｄ＞を加えた＜Ａ→Ｄ→Ｆ＞を最短経路候補に追加する。
【００９８】
次に、上述したステップＳ４４の動作に従い、決定部１３は、決定済みの最短経路の終点ノードの親ノードに隣接し、かつ、始点ノードからの最短経路が未決定のノードが存在するかどうかを確認する。ここでは、決定済みの最短経路の終点ノードはノードＤである。そして、ノードＤの親ノードはノードＡである。つまり、決定部１３は、ノードＡに隣接し、かつ、ノードＡからの最短経路が未決定のノードがあるかどうかを確認する。ここでは、ノードＡに隣接し、かつ、ノードＡからの最短経路が未決定のノードはノードＢおよびノードＣである。つまり、ノードＡに隣接し、かつ、ノードＡからの最短経路が未決定のノードが存在する。
【００９９】
従って、上述したステップＳ４５の動作に従い、決定部１３は、決定済みの最短経路の終点ノードの親ノードのコスト順番情報に含まれる通信経路のうち、決定済みの最短経路上のノードへの通信経路を除いて最上位となる通信経路に、決定済みの最短経路のうち始点ノードからその親ノードまでの通信経路を加えた通信経路を最短経路候補とし、コスト値を計算する。図６（ｂ）に示したノードＡのコスト順番情報において、決定済みの最短経路上のノードへの通信経路である＜Ａ→Ｄ＞を除いて最上位となる通信経路は＜Ａ→Ｃ＞である。但し、決定済みの最短経路は＜Ａ→Ｄ＞であるため、決定済みの最短経路のうち始点ノードからその親ノードまでの通信経路は存在しない。従って、決定部１３は、＜Ａ→Ｃ＞を最短経路候補として追加する。ここまでに最短経路候補となっている通信経路が、図６（ｄ）に示され、また、図６（ａ）おいて実線で示されている。
【０１００】
次に、上述したステップＳ４６の動作に従い、決定部１３は、最短経路候補が存在するかどうかを確認する。ここでは、最短経路候補は、図６（ｄ）に示す２つである。つまり、最短経路候補が存在する。従って、上述したステップＳ４７の動作に従い、決定部１３は、この２つの最短経路候補のうちコスト値が最小の＜Ａ→Ｄ→Ｆ＞を最短経路として決定する。
【０１０１】
次に、上述したステップＳ４８の動作に従い、決定部１３は、決定済みの最短経路の終点ノードとして認識しているノードに代えて、ステップＳ４７にて決定した最短経路の終点ノードを、決定済みの最短経路の終点ノードとして新たに認識する。ここでは、決定部１３は、ノードＤに代えて、ノードＦを決定済みの最短経路の終点ノードとして新たに認識する。
【０１０２】
そして、上述したステップＳ４２の動作へ遷移し、決定部１３は、ノードＦに隣接し、かつ、ノードＡからの最短経路が未決定のノードが存在するかどうかを確認する。ここでは、ノードＦに隣接し、かつ、ノードＡからの最短経路が未決定のノードはノードＨおよびノードＩである。つまり、ノードＦに隣接し、かつ、ノードＡからの最短経路が未決定のノードが存在する。
【０１０３】
従って、上述したステップＳ４３の動作に従い、決定部１３は、決定済みの最短経路の終点ノードのコスト順番情報に含まれる通信経路のうち、決定済みの最短経路上のノードへの通信経路を除いて最上位となる通信経路に、決定済みの最短経路を加えた通信経路を最短経路候補とし、コスト値を計算する。ここでは、決定部１３は、図７（ｄ）に示したノードＦのコスト順番情報において、決定済みの最短経路上のノードへの通信経路である＜Ｆ→Ｄ＞を除いて最上位となる＜Ｆ→Ｉ＞に、＜Ａ→Ｄ→Ｆ＞を加えた＜Ａ→Ｄ→Ｆ→Ｉ＞を最短経路候補に追加する。
【０１０４】
次に、上述したステップＳ４４の動作に従い、決定部１３は、決定済みの最短経路の終点ノードの親ノードに隣接し、かつ、始点ノードからの最短経路が未決定のノードが存在するかどうかを確認する。ここでは、決定済みの最短経路の終点ノードはノードＦである。そして、ノードＦの親ノードはノードＤである。つまり、決定部１３は、ノードＤに隣接し、かつ、ノードＡからの最短経路が未決定のノードがあるかどうかを確認する。ここでは、ノードＤに隣接し、かつ、ノードＡからの最短経路が未決定のノードはノードＥおよびノードＧである。つまり、ノードＤに隣接し、かつ、ノードＡからの最短経路が未決定のノードが存在する。
【０１０５】
従って、上述したステップＳ４５の動作に従い、決定部１３は、決定済みの最短経路の終点ノードの親ノードのコスト順番情報に含まれる通信経路のうち、決定済みの最短経路上のノードへの通信経路を除いて最上位となる通信経路に、決定済みの最短経路のうち始点ノードからその親ノードまでの通信経路を加えた通信経路を最短経路候補とし、コスト値を計算する。ここでは、決定部１３は、図７（ｃ）に示したノードＤのコスト順番情報において、決定済みの最短経路上のノードへの通信経路である＜Ｄ→Ｆ＞および＜Ｄ→Ａ＞を除いて最上位となる＜Ｄ→Ｇ＞に、＜Ａ→Ｄ＞を加えた＜Ａ→Ｄ→Ｇ＞を最短経路候補として追加する。
【０１０６】
次に、上述したステップＳ４６の動作に従い、決定部１３は、最短経路候補が存在するかどうかを確認する。
【０１０７】
ここでは、最短経路候補は、図７（ｅ）に示す３つである。つまり、最短経路候補が存在する。従って、上述したステップＳ４７の動作に従い、決定部１３は、この３つ最短経路候補のうちコスト値が最小の＜Ａ→Ｃ＞を最短経路として決定する。
【０１０８】
次に、上述したステップＳ４８の動作に従い、決定部１３は、決定済みの最短経路の終点ノードとして認識しているノードに代えて、ステップＳ４７にて決定した最短経路の終点ノードを、決定済みの最短経路の終点ノードとして新たに認識する。ここでは、決定部１３は、ノードＦに代えて、ノードＣを決定済みの最短経路の終点ノードとして新たに認識する。
【０１０９】
以降、ノードＡからノードＢ〜Ｉのそれぞれまでの最短経路が決定するまで、上述したステップＳ４２〜Ｓ４８の動作が繰り返される。そして、ノードＡからノードＢ〜Ｉのそれぞれまでの最短経路が決定すると、上述したステップＳ２の動作へ遷移し、ノードＡ〜ＩのうちノードＡ以外のノードのいずれかが始点ノードとして選択される。
【０１１０】
このように本実施形態において経路決定装置１０は、複数のノードのそれぞれを１つずつ始点ノードとして選択する選択部１２と、選択部１２にて選択された始点ノードを、決定済みの最短経路の終点ノードとして認識する決定部１３を有する。
【０１１１】
決定部１３は、その後、当該始点ノードから、決定済みの最短経路の終点ノードに隣接し、かつ、当該始点ノードからの最短経路が未決定のノードである未決定ノードまでの通信経路を、最短経路の候補となる最短経路候補とし、最短経路候補のうち、コスト値が最小の最短経路候補を最短経路として決定するとともに、決定した最短経路の終点ノードを、決定済みの最短経路の終点ノードとして認識しているノードに代えて、決定済みの最短経路の終点ノードとして新たに認識することを繰り返す。このとき、決定部１３は、当該始点ノードから、未決定ノードのうち、決定済みの最短経路の終点ノードとの間のリンクに設定されたコスト値が最小である未決定ノードまでの通信経路を最短経路候補とする。
【０１１２】
これにより、始点ノードから、決定済みの最短経路の終点ノードに隣接し、かつ、その始点ノードからの最短経路が未決定のノードへの通信経路のすべてを最短経路候補に追加することがなくなる。
【０１１３】
そのため、最短経路候補の数が抑制され、コスト値が最小となる最短経路を決定する際の計算量を少なくすることができる。
【０１１４】
上述したダイクストラ法では、始点ノードから、以下の（１）および（２）に示す条件を満たすノードへの通信経路を最短経路候補としている。
【０１１５】
（１）決定済みの最短経路の終点ノードに隣接
（２）始点ノードからの最短経路が未決定
これに対して本実施形態では、始点ノードから、上記の（１）および（２）に加え、以下の（３）に示す条件を満たすノードへの通信経路を最短経路候補としている。
【０１１６】
（３）決定済みの最短経路の終点ノートと最小のコスト値で接続
つまり、ダイクストラ法では、最短経路候補として追加される通信経路の数は、決定済みの最短経路の終点ノードとリンクを介して接続するノードの数に応じた数となる。一方、本実施形態では、最短経路候補として追加される通信経路の数は、決定済みの最短経路の終点ノードあたり１つだけとなる。
【０１１７】
見方を変えると、ダイクストラ法の場合、コスト値が最小の最短経路候補を最短経路として決定する処理において、始点ノードから、決定済みの最短経路の終点ノードに隣接するノードまでの通信経路を、コスト値の小さな順番に並べている。
【０１１８】
一方、本実施形態では、複数のノードのそれぞれについて、そのノードと、そのノードに隣接するノードとの間の通信経路を、コスト値が小さな順番に予め並べておく。そして、コスト値が最小の最短経路候補を最短経路として決定する処理においては、始点ノードから、決定済みの最短経路の終点ノードに隣接するノードのうち、コスト値が最小のノードまでの通信経路を最短経路候補として追加しているだけである。従って、始点ノードが変わる度に、同じノードに隣接するノードまでの通信経路をコスト値が小さな順番に並べる必要はない。よって、本実施形態では、ダイクストラ法に比べて計算量を削減することができる。
【０１１９】
従って、ノードがリンクを介して他の多くのノードと隣接している場合に、最短経路を決定するまでの時間が長くなってしまうのを回避することができる。
【符号の説明】
【０１２０】
１０ 経路決定装置
１１ 記憶部
１２ 選択部
１３ 決定部
【技術分野】
【０００１】
本発明は、複数のノードから構成される通信ネットワークにおける２つのノード間の最短経路を決定する経路決定装置および経路決定方法に関する。
【背景技術】
【０００２】
隣接するノードとリンクを介して接続された複数のノードで構成される通信ネットワークにおいては、その複数のノードのいずれかである始点ノードから、その複数のノードのうちの始点ノード以外のノードである終点ノードまで複数の通信経路が存在する場合がある。そのため、その複数の通信経路のうち、最も効率的な通信経路である最短経路を決定する必要がある。
【０００３】
そこで、リンクにコスト値と呼ばれる重み値を設定し、始点ノードから終点ノードまでの複数の通信経路のそれぞれのコスト値を計算することにより、コスト値が最小となる通信経路を最短経路として決定するのが一般的である。
【０００４】
上述したような計算によって最短経路を決定するためのアルゴリズムの１つであるダイクストラ法が例えば、非特許文献１に開示されている。
【０００５】
図８は、ダイクストラ法を用いて最短経路を決定する動作を説明するためのフローチャートである。
【０００６】
まず、通信ネットワークを構成する複数のノードのうち始点ノードとして選択されていないノードが存在するかどうかが確認される（ステップＳ１０１）。
【０００７】
ステップＳ１０１における確認の結果、始点ノードとして選択されていないノードが存在しない場合、処理が終了する。
【０００８】
一方、ステップＳ１０１における確認の結果、始点ノードとして選択されていないノードが存在する場合には、始点ノードとして選択されていないノードの１つが始点ノードとして選択される（ステップＳ１０２）。なお、始点ノードとして選択されたノードは、決定済みの最短経路の終点ノードとして認識される。
【０００９】
次に、決定済みの最短経路の終点ノードに隣接し、かつ、始点ノードからの最短経路が未決定のノードが存在する場合、始点ノードから、そのノードまでの通信経路が最短経路候補とされ、コスト値が計算される（ステップＳ１０３）。
【００１０】
次に、最短経路候補が存在するかどうかが確認される（ステップＳ１０４）。
【００１１】
ステップＳ１０４における確認の結果、最短経路候補が存在する場合、コスト値が最小の最短経路候補が最短経路として決定され（ステップＳ１０５）、ステップＳ１０３の動作へ遷移する。
【００１２】
一方、ステップＳ１０４における確認の結果、最短経路候補が存在しない場合にはステップＳ１０１の動作へ遷移する。
【００１３】
以降、ステップＳ１０１〜Ｓ１０５の動作が繰り返され、通信ネットワークを構成する複数のノードのそれぞれを始点ノードとした場合の最短経路が決定される。
【００１４】
図９〜図１１は、図８に示したフローチャートに従って最短経路を決定する動作の具体例を説明するための図であり、（ａ）は通信ネットワークの一例を示す図であり、（ｂ）は最短経路候補の一例を示す図である。ここでは、最短経路が決定されていく動作の具体例を図９〜図１１を順番に参照しながら説明する。
【００１５】
なお、図９（ａ）、図１０（ａ）および図１１（ａ）に示す通信ネットワークは同じものである。
【００１６】
また、図９（ａ）、図１０（ａ）および図１１（ａ）において、ノードは円で示されており、その円の中に記載されたアルファベットにより、通信ネットワークを構成する複数のノードのそれぞれが識別されている。以降、例えば円の中にＡと記載されたノードのことをノードＡという。また、通信経路を＜ ＞を用いて表記する。例えばノードＡからノードＢまでの通信経路の場合、＜Ａ→Ｂ＞と表記する。
【００１７】
また、図９（ａ）、図１０（ａ）および図１１（ａ）において、ノードを示す円と円との間の実線または破線がリンクを示しており、リンクの近傍の数字がそのリンクに設定されたコスト値を示している。
【００１８】
まず、上述したステップＳ１０１の動作に従い、通信ネットワークを構成するノードＡ〜Ｉのうち始点ノードとして選択されていないノードが存在するかどうかが確認される。ここでは、ノードＡ〜Ｉのいずれも始点ノードとして選択されていないものとする。
【００１９】
従って、上述したステップＳ１０２の動作に従い、ノードＡ〜Ｉのうちの１つが始点ノードとして選択される。ここでは、ノードＡが始点ノードとして選択されるものとする。これにより、ノードＡは決定済みの最短経路の終点ノードとして認識される。
【００２０】
次に、上述したステップＳ１０３の動作に従い、ノードＡに隣接し、かつ、ノードＡからの最短経路が未決定のノードへの通信経路が最短経路候補とされ、コスト値が計算される。ここでは、ノードＡに隣接し、かつ、ノードＡからの最短経路が未決定のノードは、ノードＢ、ノードＣおよびノードＤである。
【００２１】
従って、＜Ａ→Ｂ＞と、＜Ａ→Ｃ＞と、＜Ａ→Ｄ＞との３つが最短経路候補となる。ここまでに最短経路候補となっている通信経路が、図９（ｂ）に示され、また、図９（ａ）おいて実線で示されている。
【００２２】
次に、上述したステップＳ１０４の動作に従い、最短経路候補が存在するかどうかが確認される。ここでは、最短経路候補は、図９（ｂ）に示す３つである。つまり、最短経路候補が存在する。従って、上述したステップＳ１０５の動作に従い、この３つの最短経路候補うち、コスト値が最小の＜Ａ→Ｄ＞が最短経路として決定する。
【００２３】
次に、上述したステップＳ１０３の動作へ遷移し、ノードＤに隣接し、かつ、ノードＡからの最短経路が未決定のノードへの通信経路が最短経路候補とされ、コスト値が計算される。ここでは、ノードＤに隣接し、かつ、ノードＡからの最短経路が未決定のノードは、ノードＥ、ノードＦおよびノードＧである。
【００２４】
従って、既に最短経路候補となっている＜Ａ→Ｂ＞と、＜Ａ→Ｃ＞との２つに加え、＜Ａ→Ｄ→Ｅ＞と、＜Ａ→Ｄ→Ｆ＞と、＜Ａ→Ｄ→Ｇ＞との３つが最短経路候補となる。ここまでに最短経路候補となっている通信経路が、図１０（ｂ）に示され、また、図１０（ａ）において実線で示されている。なお、＜Ａ→Ｄ＞は最短経路として決定済みであるため最短経路候補からは除外されている。
【００２５】
次に、上述したステップＳ１０４の動作に従い、最短経路候補が存在するかどうかが確認される。ここでは、最短経路候補は、図１０（ｂ）に示す５つである。つまり、最短経路候補が存在する。従って、上述したステップＳ１０５の動作に従い、この５つの最短経路候補のうち、コスト値が最小の＜Ａ→Ｄ→Ｆ＞が最短経路として決定する。
【００２６】
次に、上述したステップＳ１０３の動作へ遷移し、ノードＦに隣接し、かつ、ノードＡからの最短経路が未決定のノードへの通信経路が最短経路候補とされ、コスト値が計算される。ここでは、ノードＦに隣接し、かつ、ノードＡからの最短経路が未決定のノードは、ノードＨおよびノードＩである。
【００２７】
従って、既に最短経路候補となっている＜Ａ→Ｂ＞と、＜Ａ→Ｃ＞と、＜Ａ→Ｄ→Ｅ＞と、＜Ａ→Ｄ→Ｇ＞との４つに加え、＜Ａ→Ｄ→Ｆ→Ｈ＞と、＜Ａ→Ｄ→Ｆ→Ｉ＞との２つが最短経路候補となる。ここまでに最短経路候補となっている通信経路が、図１１（ｂ）に示され、また、図１１（ａ）おいて実線で示されている。なお、＜Ａ→Ｄ→Ｆ＞は最短経路として決定済みであるため最短経路候補からは除外されている。
【００２８】
次に、上述したステップＳ１０４の動作に従い、最短経路候補が存在するかどうかが確認される。ここでは、最短経路候補は、図１１（ｂ）に示す６つである。つまり、最短経路候補が存在する。従って、上述したステップＳ１０５の動作に従い、この６つの最短経路候補うち、コスト値が最小の＜Ａ→Ｃ＞が最短経路として決定する。
【００２９】
ノードＡからノードＢ〜Ｉのそれぞれまでの最短経路が決定するまで、このような動作が繰り返し行われる。そして、ノードＡからノードＢ〜Ｉのそれぞれまでの最短経路が決定すると、ノードＢ〜Ｉのそれぞれを始点ノードとした場合の最短経路を決定する。そして、ノードＡ〜Ｉのすべてのノードを始点ノードとした場合の最短経路が決定すると、最短経路を決定する計算が終了する。
【先行技術文献】
【非特許文献】
【００３０】
【非特許文献１】Dijkstra, E. W. (1959). "A note on two problems in connexion with graphs".Numerische Mathematik 1:269-271
【発明の概要】
【発明が解決しようとする課題】
【００３１】
上述したダイクストラ法のようなアルゴリズムは、始点ノードから、決定済みの最短経路の終点ノードに隣接し、かつ、その始点ノードからの最短経路が未決定のノードまでの通信経路のすべてを最短経路候補として追加する。そのため、ノードがリンクを介して他の多くのノードと隣接している場合、最短経路候補の数が多くなる。この場合、コスト値が最小となる最短経路候補を決定する際の計算量が大きくなり、最短経路を決定するまでの時間が長くなってしまうという問題点がある。
【００３２】
本発明は、ノードがリンクを介して他の多くのノードと隣接している場合に、最短経路を決定するまでの時間が長くなってしまうのを回避することができる経路決定方法および経路決定装置を提供することを目的とする。
【課題を解決するための手段】
【００３３】
上記目的を達成するために本発明の経路決定装置は、隣接するノードとコスト値が設定されたリンクを介して接続された複数のノードのそれぞれから、該複数のノードのうち当該ノード以外のノードである終点ノードまでの最短経路を決定する経路決定装置であって、
前記複数のノードのそれぞれを１つずつ始点ノードとして選択する選択部と、
前記選択部にて選択された始点ノードを、決定済みの最短経路の終点ノードとして認識し、その後、当該始点ノードから、前記決定済みの最短経路の終点ノードに隣接し、かつ、当該始点ノードからの最短経路が未決定のノードである未決定ノードまでの通信経路を、最短経路の候補となる最短経路候補とし、該最短経路候補のうち、コスト値が最小の最短経路候補を最短経路として決定するとともに、該決定した最短経路の終点ノードを、前記決定済みの最短経路の終点ノードとして認識しているノードに代えて、前記決定済みの最短経路の終点ノードとして新たに認識することを繰り返す決定部と、を有し、
前記決定部は、当該始点ノードから、前記未決定ノードのうち、前記決定済みの最短経路の終点ノードとの間のリンクに設定されたコスト値が最小である未決定ノードまでの通信経路を前記最短経路候補とする。
【００３４】
また、上記目的を達成するために本発明の経路決定方法は、隣接するノードとコスト値が設定されたリンクを介して接続された複数のノードのそれぞれから、該複数のノードのうち当該ノード以外のノードである終点ノードまでの最短経路を決定する経路決定装置における経路決定方法であって、
前記複数のノードのそれぞれを１つずつ始点ノードとして選択する処理と、
前記選択した始点ノードを、決定済みの最短経路の終点ノードとして認識する処理と、
当該始点ノードから、前記決定済みの最短経路の終点ノードに隣接し、かつ、当該始点ノードからの最短経路が未決定のノードである未決定ノードまでの通信経路を、最短経路の候補となる最短経路候補とし、該最短経路候補のうち、コスト値が最小の最短経路候補を最短経路として決定するとともに、該決定した最短経路の終点ノードを、前記決定済みの最短経路の終点ノードとして認識しているノードに代えて、前記決定済みの最短経路の終点ノードとして新たに認識することを繰り返す決定処理と、を有し、
前記決定処理では、当該始点ノードから、前記未決定ノードのうち、前記決定済みの最短経路の終点ノードとの間のリンクに設定されたコスト値が最小である未決定ノードまでの通信経路を前記最短経路候補とする。
【発明の効果】
【００３５】
本発明は以上説明したように構成されているので、始点ノードから、決定済みの最短経路の終点ノードに隣接し、かつ、その始点ノードからの最短経路が未決定のノードへの通信経路のすべてを最短経路候補に追加することがなくなる。
【００３６】
そのため、最短経路候補の数が抑制され、コスト値が最小となる最短経路を決定する際の計算量を少なくすることができる。
【００３７】
従って、ノードがリンクを介して他の多くのノードと隣接している場合に、最短経路を決定するまでの時間が長くなってしまうのを回避することができる。
【図面の簡単な説明】
【００３８】
【図１】ダイクストラ法のアルゴリズムの性質を説明するための図である。
【図２】本発明の経路決定装置の実施の一形態の構成を示すブロック図である。
【図３】図２に示した経路決定装置が最短経路を決定する動作を説明するためのフローチャートである。
【図４】図２に示した経路決定装置が最短経路を決定する動作の詳細を説明するためのフローチャートである。
【図５】図３および図４に示したフローチャートに従って、経路決定装置が最短経路を決定する動作の具体例を説明するための図である。
【図６】図３および図４に示したフローチャートに従って、経路決定装置が最短経路を決定する動作の具体例を説明するための図である。
【図７】図３および図４に示したフローチャートに従って、経路決定装置が最短経路を決定する動作の具体例を説明するための図である。
【図８】ダイクストラ法を用いて最短経路を決定する動作を説明するためのフローチャートである。
【図９】図８に示したフローチャートに従って最短経路を決定する動作の具体例を説明するための図であり、（ａ）は通信ネットワークの一例を示す図であり、（ｂ）は最短経路候補の一例を示す図である。
【図１０】図８に示したフローチャートに従って最短経路を決定する動作の具体例を説明するための図であり、（ａ）は通信ネットワークの一例を示す図であり、（ｂ）は最短経路候補の一例を示す図である。
【図１１】図８に示したフローチャートに従って最短経路を決定する動作の具体例を説明するための図であり、（ａ）は通信ネットワークの一例を示す図であり、（ｂ）は最短経路候補の一例を示す図である。
【発明を実施するための形態】
【００３９】
以下に、本発明の実施の形態について図面を参照して説明するが、その前に、上述したダイクストラ法のアルゴリズムの性質について説明する。
【００４０】
図１は、ダイクストラ法のアルゴリズムの性質を説明するための図である。なお、ここでは、上述した図９（ａ）、図１０（ａ）および図１１（ａ）に示した通信ネットワークを構成する複数のノードおよびコスト値に基づいて説明する。
【００４１】
図１（ａ）、図１（ｂ）および図１（ｄ）、図１（ｅ）、図１（ｆ）は、図９〜図１１を参照しながら説明した動作において決定した最短経路の終点ノードから、その終点ノードとリンクを介して隣接するノードまでの通信経路を、コスト値が小さな順番に並べたものである。
【００４２】
具体的には、図１（ａ）および図１（ｄ）は、ノードＡと、ノードＡとリンクを介して隣接するノードとの間の通信経路を、コスト値が小さな順番に並べて記載したものである。また、図１（ｂ）および図１（ｅ）は、ノードＤと、ノードＤとリンクを介して隣接するノードとの間の通信経路を、コスト値が小さな順番に並べて記載したものである。また、図１（ｆ）は、ノードＦと、ノードＦとリンクを介して隣接するノードとの間の通信経路を、コスト値が小さな順番に並べて記載したものである。
【００４３】
まず、＜Ａ→Ｄ＞が最短経路として決定した場合、図１（ａ）および図１（ｂ）の図中網掛けされた通信経路は、決定済みの最短経路上のノードへの通信経路となるため、最短経路候補を検討する際の対象から除外される。
【００４４】
図１（ｃ）は、＜Ａ→Ｄ＞が最短経路として決定した後の最短経路候補をコスト値が小さな順番に並べたものである。
【００４５】
図１（ｃ）に示した最短経路候補のうち、ノードＡからノードＡに隣接するノードまでの最短経路候補の順番は、図１（ａ）に示した順番と同じである。すなわち、図１（ａ）および図１（ｃ）において、＜Ａ→Ｃ＞は＜Ａ→Ｂ＞よりも上位となっている。
【００４６】
また、図１（ｃ）に示した最短経路候補のうち、ノードＡからノードＤを介してノードＤに隣接するノードまでの最短経路候補の順番は、ノードＤからノードＤに隣接するノードまでの通信経路に着目すると、図１（ｂ）に示した順番と同じである。すなわち、図１（ｂ）において＜Ｄ→Ｆ＞は＜Ｄ→Ｇ＞および＜Ｄ→Ｅ＞よりも上位となり、図１（ｃ）において＜Ａ→Ｄ→Ｆ＞は＜Ａ→Ｄ→Ｇ＞および＜Ａ→Ｄ→Ｅ＞よりも上位となっている。また、図１（ｂ）において＜Ｄ→Ｇ＞は＜Ｄ→Ｅ＞よりも上位となり、図１（ｃ）において＜Ａ→Ｄ→Ｇ＞は＜Ａ→Ｄ→Ｅ＞よりも上位となっている。
【００４７】
次に、＜Ａ→Ｄ→Ｆ＞が最短経路として決定した場合、図１（ｄ）、図１（ｅ）および図１（ｆ）の図中網掛けされた通信経路は、決定済みの最短経路上のノードへの通信経路となるため、最短経路候補を検討する際の対象から除外される。
【００４８】
図１（ｇ）は、＜Ａ→Ｄ→Ｆ＞が最短経路として決定した後の最短経路候補をコスト値が小さな順番に並べたものである。
【００４９】
図１（ｇ）に示した最短経路候補のうち、ノードＡからノードＡに隣接するノードまでの最短経路候補の順番は、図１（ｄ）に示した順番と同じである。また、図１（ｇ）に示した最短経路候補のうち、ノードＡからノードＤを介してノードＤに隣接するノードまでの最短経路候補の順番は、ノードＤからノードＤに隣接するノードまでの通信経路に着目すると、図１（ｂ）に示した順番と同じである。
【００５０】
また、図１（ｇ）に示した最短経路候補のうち、ノードＡからノードＤとノードＦとを介してノードＦに隣接するノードまでの最短経路候補の順番は、ノードＦからノードＦに隣接するノードまでの通信経路に着目すると、図１（ｆ）に示した順番と同じである。すなわち、図１（ｆ）において＜Ｆ→Ｉ＞は＜Ｆ→Ｈ＞よりも上位となり、図１（ｇ）において＜Ａ→Ｄ→Ｆ→Ｉ＞は＜Ａ→Ｄ→Ｆ→Ｈ＞よりも上位となっている。
【００５１】
このように、新たに最短経路が決定して最短経路候補が追加されても最短経路候補は、決定済みの最短経路の終点ノード毎に見ると、その終点ノードとその終点ノードに隣接するノードとを接続するリンクに設定されたコスト値が小さな順番に並ぶことになる。すなわち、最短経路は、決定済みの最短経路の終点ノード毎に見ると、その終点ノードとその終点ノードに隣接するノードとを接続するリンクに設定されたコスト値が小さな順番に決定していくことになる。
【００５２】
これは、始点ノードから、決定済みの最短経路の終点ノードまでのコスト値が同じであり、その終点ノードと、その終点ノードに隣接し、かつ、始点ノードからの最短経路が未決定のノードとを接続するリンクに設定されたコスト値の差が、最短経路候補のコスト値の差となるためである。
【００５３】
従って、最短経路を決定する際には、始点ノードから、決定済みの最短経路の終点ノードに隣接し、かつ、始点ノードからの最短経路が未決定のノードのうち、その終点ノードとの間のリンクに設定されたコスト値が最小であるノードまでの通信経路だけを最短経路候補として追加すればよいことになる。本実施形態では、このようにして最短経路候補を追加していく。
【００５４】
図２は、本発明の経路決定装置の実施の一形態の構成を示すブロック図である。
【００５５】
本実施形態の経路決定装置は図２に示すように、記憶部１１と、選択部１２と、決定部１３とを備えている。
【００５６】
記憶部１１は、通信ネットワークを示すネットワーク構成情報を記憶する。なお、ネットワーク構成情報には、通信ネットワークを構成する複数のノードを示す情報と、リンクに設定されたコスト値を示す情報とが含まれている。
【００５７】
選択部１２は、決定部１３から出力された選択指示を受け付ける。なお、選択指示とは、記憶部１１に記憶されたネットワーク構成情報が示す通信ネットワークを構成する複数のノードのうちの１つを始点ノードとして選択させるための指示である。なお、以降、記憶部１１に記憶されたネットワーク構成情報が示す通信ネットワークを構成する複数のノードのことを単に、複数のノードという。選択部１２は、決定部１３から出力された選択指示を受け付けると、複数のノードのうち、始点ノードとして選択していないノードが存在するかどうかを確認する。なお、選択部１２は、決定部１３から出力された選択指示を受け付ける度に、この確認を実行する。確認の結果、複数のノードのうち、始点ノードとして選択していないノードが存在する場合、選択部１２は、始点ノードとして選択していないノードの１つを始点ノードとして選択する。そして、選択部１２は、選択した始点ノードを示す始点ノード情報を決定部１３へ出力する。
【００５８】
決定部１３は、複数のノードのそれぞれについて、コスト順番情報を生成する。コスト順番情報とは、ノードとそのノードとリンクを介して隣接するノードとの間の通信経路を、コスト値が小さな順番に並べた情報である。次に、決定部１３は、選択指示を選択部１２へ出力する。その後、決定部１３は、選択部１２から出力された始点ノード情報を受け付ける。そして、決定部１３は、受け付けた始点ノード情報が示す始点ノードから、複数のノードのうちその始点ノード以外のすべてのノードまでの最短経路を決定する。そして、決定部１３は、選択指示を選択部１２へ出力する。なお、決定部１３が最短経路を決定する動作の詳細については後述する。
【００５９】
以下に、上記のように構成された経路決定装置１０において最短経路を決定する動作について説明する。
【００６０】
図３は、図２に示した経路決定装置１０が最短経路を決定する動作を説明するためのフローチャートである。
【００６１】
まず、決定部１３は、複数のノードのそれぞれについて、コスト順番情報を生成する（ステップＳ１）。
【００６２】
そして、決定部１３は、選択部１２に選択指示を出力する。
【００６３】
決定部１３から出力された選択指示を受け付けた選択部１２は、複数のノードのうち、始点ノードとして選択していないノードが存在するかどうかを確認する（ステップＳ２）。
【００６４】
ステップＳ２における確認の結果、複数のノードのうち、始点ノードとして選択していないノードが存在しない場合、処理を終了する。
【００６５】
一方、ステップＳ２における確認の結果、複数のノードのうち、始点ノードとして選択していないノードが存在する場合、選択部１２は、始点ノードとして選択していないノードの１つを始点ノードとして選択する（ステップＳ３）。
【００６６】
そして、選択部１２は、選択した始点ノードを示す始点ノード情報を決定部１３へ出力する。
【００６７】
選択部１２から出力された始点ノード情報を受け付けた決定部１３は、受け付けた始点ノード情報が示す始点ノードから、複数のノードのうちその始点ノード以外のすべてのノードまでの最短経路を決定する（ステップＳ４）。
【００６８】
次に、決定部１３は、選択指示を選択部１２へ出力する。そして、ステップＳ２の動作へ遷移する。
【００６９】
以降、ステップＳ２〜Ｓ４の動作が繰り返され、複数のノードのそれぞれを始点ノードとした場合の最短経路が決定される。
【００７０】
次に、上述したステップＳ４において最短経路を決定する動作の詳細について説明する。
【００７１】
図４は、図２に示した経路決定装置１０が最短経路を決定する動作の詳細を説明するためのフローチャートである。なお、ここでは、決定済みの最短経路上でその決定済みの最短経路の終点ノードと始点ノード側で隣接するノードのことを、その終点ノードの親ノードと定義する。
【００７２】
まず、決定部１３は、受け付けた始点ノード情報が示す始点ノードを、決定済みの最短経路の終点ノードとして認識する（ステップＳ４１）。
【００７３】
次に、決定部１３は、決定済みの最短経路の終点ノードに隣接し、かつ、始点ノードからの最短経路が未決定のノードである未決定ノードが存在するかどうかを確認する（ステップＳ４２）。
【００７４】
ステップＳ４２における確認の結果、決定済みの最短経路の終点ノードに隣接し、かつ、始点ノードからの最短経路が未決定のノードが存在する場合、決定部１３は、その終点ノードのコスト順番情報に含まれる通信経路のうち、決定済みの最短経路上のノードへの通信経路を除いて最上位となる通信経路に、決定済みの最短経路を加えた通信経路を最短経路候補とし、コスト値を計算する（ステップＳ４３）。
【００７５】
次に、決定部１３は、決定済みの最短経路の終点ノードの親ノードに隣接し、かつ、始点ノードからの最短経路が未決定のノードが存在するかどうかを確認する（ステップＳ４４）。
【００７６】
ステップＳ４４における確認の結果、決定済みの最短経路の終点ノードの親ノードに隣接し、かつ、始点ノードからの最短経路が未決定のノードが存在する場合、決定部１３は、その親ノードのコスト順番情報に含まれる通信経路のうち、決定済みの最短経路上のノードへの通信経路を除いて最上位となる通信経路に、決定済みの最短経路のうち始点ノードからその親ノードまでの通信経路を加えた通信経路を最短経路候補とし、コスト値を計算する（ステップＳ４５）。
【００７７】
次に、決定部１３は、最短経路候補が存在するかどうかを確認する（ステップＳ４６）。
【００７８】
ステップＳ４６における確認の結果、最短経路候補が存在する場合、コスト値が最小の最短経路候補を最短経路として決定する（ステップＳ４７）。
【００７９】
次に、決定部１３は、決定済みの最短経路の終点ノードとして認識しているノードに代えて、ステップＳ４７にて決定した最短経路の終点ノードを、決定済みの最短経路の終点ノードとして新たに認識する（ステップＳ４８）。そして、ステップＳ４２の動作へ遷移する。
【００８０】
なお、ステップＳ４２における確認の結果、決定済みの最短経路の終点ノードに隣接し、かつ、始点ノードからの最短経路が未決定のノードが存在しない場合、ステップＳ４４の動作へ遷移する。
【００８１】
また、ステップＳ４４における確認の結果、決定済みの最短経路の終点ノードの親ノードに隣接し、かつ、始点ノードからの最短経路が未決定のノードが存在しない場合、ステップＳ４６の動作へ遷移する。
【００８２】
また、ステップＳ４６における確認の結果、最短経路候補が存在しない場合、処理を終了する。これは、すなわち、始点ノードから、複数のノードのうち始点ノード以外のすべてのノードまでの最短経路が決定している場合である。この場合、図３を参照しながら説明したステップＳ２の動作へ遷移することになる。
【００８３】
次に、図３および図４に示したフローチャートに従って、経路決定装置１０が最短経路を決定する動作の具体例について説明する。
【００８４】
図５〜図７は、図３および図４に示したフローチャートに従って、経路決定装置１０が最短経路を決定する動作の具体例を説明するための図である。ここでは、経路決定装置１０が最短経路を決定していく動作の具体例を図５〜図７を順番に参照しながら説明する。
【００８５】
なお、図５（ａ）、図６（ａ）および図７（ａ）は、記憶部１１に記憶されたネットワーク構成情報が示す通信ネットワークを示している。なお、この通信ネットワークは、図９（ａ）、図１０（ａ）および図１１（ａ）に示した通信ネットワークと同じ構成である。
【００８６】
また、図５（ｂ）、図６（ｂ）および図７（ｂ）はノードＡのコスト順番情報を示しており、図６（ｃ）および図７（ｃ）はノードＤのコスト順番情報を示しており、図７（ｄ）はノードＦのコスト順番情報を示している。
【００８７】
まず、上述したステップＳ１の動作に従い、決定部１３は、ノードＡ〜Ｉのそれぞれについてコスト順番情報を生成する。
【００８８】
次に、上述したステップＳ２の動作に従い、選択部１２は、ノードＡ〜Ｉのうち、始点ノードとして選択していないノードがあるかどうかを確認する。ここでは、ノードＡ〜Ｉのいずれも始点ノードとして選択されていないものとする。
【００８９】
従って、選択部１２は、上述したステップＳ３の動作に従い、ノードＡ〜Ｉのうちの１つを始点ノードとして選択する。ここでは、選択部１２は、ノードＡを始点ノードとして選択するものとする。
【００９０】
次に、上述したステップＳ４１の動作に従い、決定部１３は、ノードＡを、決定済みの最短経路の終点ノードとして認識する。
【００９１】
次に、上述したステップＳ４２の動作に従い、決定部１３は、ノードＡに隣接し、かつ、ノードＡからの最短経路が未決定のノードが存在するかどうかを確認する。ここでは、ノードＡに隣接し、かつ、ノードＡからの最短経路が未決定のノードは、ノードＢ、ノードＣおよびノードＤである。つまり、ノードＡに隣接し、かつ、ノードＡからの最短経路が未決定のノードが存在する。
【００９２】
従って、上述したステップＳ４３の動作に従い、決定部１３は、決定済みの最短経路の終点ノードのコスト順番情報に含まれる通信経路のうち、決定済みの最短経路上のノードへの通信経路を除いて最上位となる通信経路に、決定済みの最短経路を加えた通信経路を最短経路候補とし、コスト値を計算する。ここでは、決定済みの最短経路は存在しない。そのため、決定部１３は、図５（ｂ）に示したコスト順番情報において最上位である＜Ａ→Ｄ＞を最短経路候補とする。
【００９３】
次に、上述したステップＳ４４の動作に従い、決定部１３は、決定済みの最短経路の終点ノードの親ノードに隣接し、かつ、始点ノードからの最短経路が未決定のノードが存在するかどうかを確認する。ここでは、決定済みの最短経路の終点ノードはノードＡであるが、ノードＡは始点ノードでもあるため、親ノードは存在しない。そのため、親ノードに隣接し、かつ、始点ノードからの最短経路が未決定のノードは存在しない。従って、上述したステップＳ４６の動作へ遷移し、決定部１３は、最短経路候補が存在するかどうかを確認する。ここまでに最短経路候補となっている通信経路が、図５（ｃ）に示され、また、図５（ａ）おいて実線で示されている。
【００９４】
ここでは、最短経路候補は、図５（ｃ）に示す１つである。つまり、最短経路候補が存在する。従って、上述したステップＳ４７の動作に従い、決定部１３は、コスト値が最小の＜Ａ→Ｄ＞を最短経路として決定する。
【００９５】
次に、上述したステップＳ４８の動作に従い、決定部１３は、決定済みの最短経路の終点ノードとして認識しているノードに代えて、ステップＳ４７にて決定した最短経路の終点ノードを、決定済みの最短経路の終点ノードとして新たに認識する。ここでは、決定部１３は、ノードＡに代えて、ノードＤを決定済みの最短経路の終点ノードとして新たに認識する。
【００９６】
そして、上述したステップＳ４２の動作へ遷移し、決定部１３は、ノードＤに隣接し、かつ、ノードＡからの最短経路が未決定のノードが存在するかどうかを確認する。ここでは、ノードＤに隣接し、かつ、ノードＡからの最短経路が未決定のノードはノードＥ、ノードＦおよびノードＧである。つまり、ノードＤに隣接し、かつ、ノードＡからの最短経路が未決定のノードが存在する。
【００９７】
従って、上述したステップＳ４３の動作に従い、決定部１３は、決定済みの最短経路の終点ノードのコスト順番情報に含まれる通信経路のうち、決定済みの最短経路上のノードへの通信経路を除いて最上位となる通信経路に、決定済みの最短経路を加えた通信経路を最短経路候補とし、コスト値を計算する。ここでは、決定部１３は、図６（ｃ）に示したノードＤのコスト順番情報において、決定済みの最短経路上のノードへの通信経路である＜Ｄ→Ａ＞を除いて最上位となる＜Ｄ→Ｆ＞に、＜Ａ→Ｄ＞を加えた＜Ａ→Ｄ→Ｆ＞を最短経路候補に追加する。
【００９８】
次に、上述したステップＳ４４の動作に従い、決定部１３は、決定済みの最短経路の終点ノードの親ノードに隣接し、かつ、始点ノードからの最短経路が未決定のノードが存在するかどうかを確認する。ここでは、決定済みの最短経路の終点ノードはノードＤである。そして、ノードＤの親ノードはノードＡである。つまり、決定部１３は、ノードＡに隣接し、かつ、ノードＡからの最短経路が未決定のノードがあるかどうかを確認する。ここでは、ノードＡに隣接し、かつ、ノードＡからの最短経路が未決定のノードはノードＢおよびノードＣである。つまり、ノードＡに隣接し、かつ、ノードＡからの最短経路が未決定のノードが存在する。
【００９９】
従って、上述したステップＳ４５の動作に従い、決定部１３は、決定済みの最短経路の終点ノードの親ノードのコスト順番情報に含まれる通信経路のうち、決定済みの最短経路上のノードへの通信経路を除いて最上位となる通信経路に、決定済みの最短経路のうち始点ノードからその親ノードまでの通信経路を加えた通信経路を最短経路候補とし、コスト値を計算する。図６（ｂ）に示したノードＡのコスト順番情報において、決定済みの最短経路上のノードへの通信経路である＜Ａ→Ｄ＞を除いて最上位となる通信経路は＜Ａ→Ｃ＞である。但し、決定済みの最短経路は＜Ａ→Ｄ＞であるため、決定済みの最短経路のうち始点ノードからその親ノードまでの通信経路は存在しない。従って、決定部１３は、＜Ａ→Ｃ＞を最短経路候補として追加する。ここまでに最短経路候補となっている通信経路が、図６（ｄ）に示され、また、図６（ａ）おいて実線で示されている。
【０１００】
次に、上述したステップＳ４６の動作に従い、決定部１３は、最短経路候補が存在するかどうかを確認する。ここでは、最短経路候補は、図６（ｄ）に示す２つである。つまり、最短経路候補が存在する。従って、上述したステップＳ４７の動作に従い、決定部１３は、この２つの最短経路候補のうちコスト値が最小の＜Ａ→Ｄ→Ｆ＞を最短経路として決定する。
【０１０１】
次に、上述したステップＳ４８の動作に従い、決定部１３は、決定済みの最短経路の終点ノードとして認識しているノードに代えて、ステップＳ４７にて決定した最短経路の終点ノードを、決定済みの最短経路の終点ノードとして新たに認識する。ここでは、決定部１３は、ノードＤに代えて、ノードＦを決定済みの最短経路の終点ノードとして新たに認識する。
【０１０２】
そして、上述したステップＳ４２の動作へ遷移し、決定部１３は、ノードＦに隣接し、かつ、ノードＡからの最短経路が未決定のノードが存在するかどうかを確認する。ここでは、ノードＦに隣接し、かつ、ノードＡからの最短経路が未決定のノードはノードＨおよびノードＩである。つまり、ノードＦに隣接し、かつ、ノードＡからの最短経路が未決定のノードが存在する。
【０１０３】
従って、上述したステップＳ４３の動作に従い、決定部１３は、決定済みの最短経路の終点ノードのコスト順番情報に含まれる通信経路のうち、決定済みの最短経路上のノードへの通信経路を除いて最上位となる通信経路に、決定済みの最短経路を加えた通信経路を最短経路候補とし、コスト値を計算する。ここでは、決定部１３は、図７（ｄ）に示したノードＦのコスト順番情報において、決定済みの最短経路上のノードへの通信経路である＜Ｆ→Ｄ＞を除いて最上位となる＜Ｆ→Ｉ＞に、＜Ａ→Ｄ→Ｆ＞を加えた＜Ａ→Ｄ→Ｆ→Ｉ＞を最短経路候補に追加する。
【０１０４】
次に、上述したステップＳ４４の動作に従い、決定部１３は、決定済みの最短経路の終点ノードの親ノードに隣接し、かつ、始点ノードからの最短経路が未決定のノードが存在するかどうかを確認する。ここでは、決定済みの最短経路の終点ノードはノードＦである。そして、ノードＦの親ノードはノードＤである。つまり、決定部１３は、ノードＤに隣接し、かつ、ノードＡからの最短経路が未決定のノードがあるかどうかを確認する。ここでは、ノードＤに隣接し、かつ、ノードＡからの最短経路が未決定のノードはノードＥおよびノードＧである。つまり、ノードＤに隣接し、かつ、ノードＡからの最短経路が未決定のノードが存在する。
【０１０５】
従って、上述したステップＳ４５の動作に従い、決定部１３は、決定済みの最短経路の終点ノードの親ノードのコスト順番情報に含まれる通信経路のうち、決定済みの最短経路上のノードへの通信経路を除いて最上位となる通信経路に、決定済みの最短経路のうち始点ノードからその親ノードまでの通信経路を加えた通信経路を最短経路候補とし、コスト値を計算する。ここでは、決定部１３は、図７（ｃ）に示したノードＤのコスト順番情報において、決定済みの最短経路上のノードへの通信経路である＜Ｄ→Ｆ＞および＜Ｄ→Ａ＞を除いて最上位となる＜Ｄ→Ｇ＞に、＜Ａ→Ｄ＞を加えた＜Ａ→Ｄ→Ｇ＞を最短経路候補として追加する。
【０１０６】
次に、上述したステップＳ４６の動作に従い、決定部１３は、最短経路候補が存在するかどうかを確認する。
【０１０７】
ここでは、最短経路候補は、図７（ｅ）に示す３つである。つまり、最短経路候補が存在する。従って、上述したステップＳ４７の動作に従い、決定部１３は、この３つ最短経路候補のうちコスト値が最小の＜Ａ→Ｃ＞を最短経路として決定する。
【０１０８】
次に、上述したステップＳ４８の動作に従い、決定部１３は、決定済みの最短経路の終点ノードとして認識しているノードに代えて、ステップＳ４７にて決定した最短経路の終点ノードを、決定済みの最短経路の終点ノードとして新たに認識する。ここでは、決定部１３は、ノードＦに代えて、ノードＣを決定済みの最短経路の終点ノードとして新たに認識する。
【０１０９】
以降、ノードＡからノードＢ〜Ｉのそれぞれまでの最短経路が決定するまで、上述したステップＳ４２〜Ｓ４８の動作が繰り返される。そして、ノードＡからノードＢ〜Ｉのそれぞれまでの最短経路が決定すると、上述したステップＳ２の動作へ遷移し、ノードＡ〜ＩのうちノードＡ以外のノードのいずれかが始点ノードとして選択される。
【０１１０】
このように本実施形態において経路決定装置１０は、複数のノードのそれぞれを１つずつ始点ノードとして選択する選択部１２と、選択部１２にて選択された始点ノードを、決定済みの最短経路の終点ノードとして認識する決定部１３を有する。
【０１１１】
決定部１３は、その後、当該始点ノードから、決定済みの最短経路の終点ノードに隣接し、かつ、当該始点ノードからの最短経路が未決定のノードである未決定ノードまでの通信経路を、最短経路の候補となる最短経路候補とし、最短経路候補のうち、コスト値が最小の最短経路候補を最短経路として決定するとともに、決定した最短経路の終点ノードを、決定済みの最短経路の終点ノードとして認識しているノードに代えて、決定済みの最短経路の終点ノードとして新たに認識することを繰り返す。このとき、決定部１３は、当該始点ノードから、未決定ノードのうち、決定済みの最短経路の終点ノードとの間のリンクに設定されたコスト値が最小である未決定ノードまでの通信経路を最短経路候補とする。
【０１１２】
これにより、始点ノードから、決定済みの最短経路の終点ノードに隣接し、かつ、その始点ノードからの最短経路が未決定のノードへの通信経路のすべてを最短経路候補に追加することがなくなる。
【０１１３】
そのため、最短経路候補の数が抑制され、コスト値が最小となる最短経路を決定する際の計算量を少なくすることができる。
【０１１４】
上述したダイクストラ法では、始点ノードから、以下の（１）および（２）に示す条件を満たすノードへの通信経路を最短経路候補としている。
【０１１５】
（１）決定済みの最短経路の終点ノードに隣接
（２）始点ノードからの最短経路が未決定
これに対して本実施形態では、始点ノードから、上記の（１）および（２）に加え、以下の（３）に示す条件を満たすノードへの通信経路を最短経路候補としている。
【０１１６】
（３）決定済みの最短経路の終点ノートと最小のコスト値で接続
つまり、ダイクストラ法では、最短経路候補として追加される通信経路の数は、決定済みの最短経路の終点ノードとリンクを介して接続するノードの数に応じた数となる。一方、本実施形態では、最短経路候補として追加される通信経路の数は、決定済みの最短経路の終点ノードあたり１つだけとなる。
【０１１７】
見方を変えると、ダイクストラ法の場合、コスト値が最小の最短経路候補を最短経路として決定する処理において、始点ノードから、決定済みの最短経路の終点ノードに隣接するノードまでの通信経路を、コスト値の小さな順番に並べている。
【０１１８】
一方、本実施形態では、複数のノードのそれぞれについて、そのノードと、そのノードに隣接するノードとの間の通信経路を、コスト値が小さな順番に予め並べておく。そして、コスト値が最小の最短経路候補を最短経路として決定する処理においては、始点ノードから、決定済みの最短経路の終点ノードに隣接するノードのうち、コスト値が最小のノードまでの通信経路を最短経路候補として追加しているだけである。従って、始点ノードが変わる度に、同じノードに隣接するノードまでの通信経路をコスト値が小さな順番に並べる必要はない。よって、本実施形態では、ダイクストラ法に比べて計算量を削減することができる。
【０１１９】
従って、ノードがリンクを介して他の多くのノードと隣接している場合に、最短経路を決定するまでの時間が長くなってしまうのを回避することができる。
【符号の説明】
【０１２０】
１０ 経路決定装置
１１ 記憶部
１２ 選択部
１３ 決定部
【特許請求の範囲】
【請求項１】
隣接するノードとコスト値が設定されたリンクを介して接続された複数のノードのそれぞれから、該複数のノードのうち当該ノード以外のノードである終点ノードまでの最短経路を決定する経路決定装置であって、
前記複数のノードのそれぞれを１つずつ始点ノードとして選択する選択部と、
前記選択部にて選択された始点ノードを、決定済みの最短経路の終点ノードとして認識し、その後、当該始点ノードから、前記決定済みの最短経路の終点ノードに隣接し、かつ、当該始点ノードからの最短経路が未決定のノードである未決定ノードまでの通信経路を、最短経路の候補となる最短経路候補とし、該最短経路候補のうち、コスト値が最小の最短経路候補を最短経路として決定するとともに、該決定した最短経路の終点ノードを、前記決定済みの最短経路の終点ノードとして認識しているノードに代えて、前記決定済みの最短経路の終点ノードとして新たに認識することを繰り返す決定部と、を有し、
前記決定部は、当該始点ノードから、前記未決定ノードのうち、前記決定済みの最短経路の終点ノードとの間のリンクに設定されたコスト値が最小である未決定ノードまでの通信経路を前記最短経路候補とする経路決定装置。
【請求項２】
請求項１に記載の経路決定装置において、
前記決定部は、前記複数のノードのそれぞれについて、当該ノードに隣接するノードまでの通信経路を、コスト値が小さな順番に並べた情報であるコスト順番情報を予め生成し、前記決定済みの最短経路の終点ノードの前記コスト順番情報において、当該決定済みの最短経路上のノードへの通信経路を除いて最上位となる通信経路に、当該決定済みの最短経路を加えた通信経路と、当該決定済みの最短経路上で当該決定済みの最短経路の終点ノードと当該始点ノード側で隣接するノードである親ノードの前記コスト順番情報において、当該決定済みの最短経路上のノードへの通信経路を除いて最上位となる通信経路に、当該決定済みの最短経路のうち当該始点ノードから前記親ノードまでの通信経路を加えた通信経路とを、前記最短経路候補とする経路決定装置。
【請求項３】
隣接するノードとコスト値が設定されたリンクを介して接続された複数のノードのそれぞれから、該複数のノードのうち当該ノード以外のノードである終点ノードまでの最短経路を決定する経路決定装置における経路決定方法であって、
前記複数のノードのそれぞれを１つずつ始点ノードとして選択する処理と、
前記選択した始点ノードを、決定済みの最短経路の終点ノードとして認識する処理と、
当該始点ノードから、前記決定済みの最短経路の終点ノードに隣接し、かつ、当該始点ノードからの最短経路が未決定のノードである未決定ノードまでの通信経路を、最短経路の候補となる最短経路候補とし、該最短経路候補のうち、コスト値が最小の最短経路候補を最短経路として決定するとともに、該決定した最短経路の終点ノードを、前記決定済みの最短経路の終点ノードとして認識しているノードに代えて、前記決定済みの最短経路の終点ノードとして新たに認識することを繰り返す決定処理と、を有し、
前記決定処理では、当該始点ノードから、前記未決定ノードのうち、前記決定済みの最短経路の終点ノードとの間のリンクに設定されたコスト値が最小である未決定ノードまでの通信経路を前記最短経路候補とする経路決定方法。
【請求項４】
請求項３に記載の経路決定方法において、
前記複数のノードのそれぞれについて、当該ノードに隣接するノードまでの通信経路を、コスト値が小さな順番に並べた情報であるコスト順番情報を予め生成する処理をさらに有し、
前記決定処理では、前記決定済みの最短経路の終点ノードの前記コスト順番情報において、当該決定済みの最短経路上のノードへの通信経路を除いて最上位となる通信経路に、当該決定済みの最短経路を加えた通信経路と、当該決定済みの最短経路上で当該決定済みの最短経路の終点ノードと当該始点ノード側で隣接するノードである親ノードの前記コスト順番情報において、当該決定済みの最短経路上のノードへの通信経路を除いて最上位となる通信経路に、当該決定済みの最短経路のうち当該始点ノードから前記親ノードまでの通信経路を加えた通信経路とを、前記最短経路候補とする経路決定方法。
【請求項１】
隣接するノードとコスト値が設定されたリンクを介して接続された複数のノードのそれぞれから、該複数のノードのうち当該ノード以外のノードである終点ノードまでの最短経路を決定する経路決定装置であって、
前記複数のノードのそれぞれを１つずつ始点ノードとして選択する選択部と、
前記選択部にて選択された始点ノードを、決定済みの最短経路の終点ノードとして認識し、その後、当該始点ノードから、前記決定済みの最短経路の終点ノードに隣接し、かつ、当該始点ノードからの最短経路が未決定のノードである未決定ノードまでの通信経路を、最短経路の候補となる最短経路候補とし、該最短経路候補のうち、コスト値が最小の最短経路候補を最短経路として決定するとともに、該決定した最短経路の終点ノードを、前記決定済みの最短経路の終点ノードとして認識しているノードに代えて、前記決定済みの最短経路の終点ノードとして新たに認識することを繰り返す決定部と、を有し、
前記決定部は、当該始点ノードから、前記未決定ノードのうち、前記決定済みの最短経路の終点ノードとの間のリンクに設定されたコスト値が最小である未決定ノードまでの通信経路を前記最短経路候補とする経路決定装置。
【請求項２】
請求項１に記載の経路決定装置において、
前記決定部は、前記複数のノードのそれぞれについて、当該ノードに隣接するノードまでの通信経路を、コスト値が小さな順番に並べた情報であるコスト順番情報を予め生成し、前記決定済みの最短経路の終点ノードの前記コスト順番情報において、当該決定済みの最短経路上のノードへの通信経路を除いて最上位となる通信経路に、当該決定済みの最短経路を加えた通信経路と、当該決定済みの最短経路上で当該決定済みの最短経路の終点ノードと当該始点ノード側で隣接するノードである親ノードの前記コスト順番情報において、当該決定済みの最短経路上のノードへの通信経路を除いて最上位となる通信経路に、当該決定済みの最短経路のうち当該始点ノードから前記親ノードまでの通信経路を加えた通信経路とを、前記最短経路候補とする経路決定装置。
【請求項３】
隣接するノードとコスト値が設定されたリンクを介して接続された複数のノードのそれぞれから、該複数のノードのうち当該ノード以外のノードである終点ノードまでの最短経路を決定する経路決定装置における経路決定方法であって、
前記複数のノードのそれぞれを１つずつ始点ノードとして選択する処理と、
前記選択した始点ノードを、決定済みの最短経路の終点ノードとして認識する処理と、
当該始点ノードから、前記決定済みの最短経路の終点ノードに隣接し、かつ、当該始点ノードからの最短経路が未決定のノードである未決定ノードまでの通信経路を、最短経路の候補となる最短経路候補とし、該最短経路候補のうち、コスト値が最小の最短経路候補を最短経路として決定するとともに、該決定した最短経路の終点ノードを、前記決定済みの最短経路の終点ノードとして認識しているノードに代えて、前記決定済みの最短経路の終点ノードとして新たに認識することを繰り返す決定処理と、を有し、
前記決定処理では、当該始点ノードから、前記未決定ノードのうち、前記決定済みの最短経路の終点ノードとの間のリンクに設定されたコスト値が最小である未決定ノードまでの通信経路を前記最短経路候補とする経路決定方法。
【請求項４】
請求項３に記載の経路決定方法において、
前記複数のノードのそれぞれについて、当該ノードに隣接するノードまでの通信経路を、コスト値が小さな順番に並べた情報であるコスト順番情報を予め生成する処理をさらに有し、
前記決定処理では、前記決定済みの最短経路の終点ノードの前記コスト順番情報において、当該決定済みの最短経路上のノードへの通信経路を除いて最上位となる通信経路に、当該決定済みの最短経路を加えた通信経路と、当該決定済みの最短経路上で当該決定済みの最短経路の終点ノードと当該始点ノード側で隣接するノードである親ノードの前記コスト順番情報において、当該決定済みの最短経路上のノードへの通信経路を除いて最上位となる通信経路に、当該決定済みの最短経路のうち当該始点ノードから前記親ノードまでの通信経路を加えた通信経路とを、前記最短経路候補とする経路決定方法。
【図２】
【図３】
【図４】
【図５】
【図８】
【図９】
【図１０】
【図１１】
【図１】
【図６】
【図７】
【図３】
【図４】
【図５】
【図８】
【図９】
【図１０】
【図１１】
【図１】
【図６】
【図７】
【公開番号】特開２０１２−２５３５４１（Ｐ２０１２−２５３５４１Ａ）
【公開日】平成２４年１２月２０日（２０１２．１２．２０）
【国際特許分類】
【出願番号】特願２０１１−１２４１９０（Ｐ２０１１−１２４１９０）
【出願日】平成２３年６月２日（２０１１．６．２）
【出願人】（０００００４２２６）日本電信電話株式会社 (13,992)
【Ｆターム（参考）】
【公開日】平成２４年１２月２０日（２０１２．１２．２０）
【国際特許分類】
【出願日】平成２３年６月２日（２０１１．６．２）
【出願人】（０００００４２２６）日本電信電話株式会社 (13,992)
【Ｆターム（参考）】
[ Back to top ]