"コストが付与されたリンクによって複数のノードが互いに接続されて形成されるネットワーク上で、所望の始点ノードから所望の終端ノード複数可に至るまでの経路を複数本探索する複数経路探索方法であって、経路候補作成手段が、前記始点ノードから接続可能な全てのリンクを選択して経路候補を作成し、記憶手段の、各リンクの終端ノードあるいは終端点に対応する経路候補リスト内に格納する第1の経路候補作成ステップと、経路候補リスト制御手段が、前記記憶手段内のすべての経路候補リストの中で、経路コストが最小となる1本の経路候補を検索し、該経路候補リストから削除する最小コスト経路削除ステップと、前記経路候補リスト制御手段が、前記検索された経路候補の終端ノードから接続可能な全てのリンクを更に選択し、当該経路候補に選択された各リンクを加えた新たな経路候補を作成し、各リンクの終端ノードあるいは終端点に対応する経路候補リスト内に格納する第2の経路候補作成ステップと、必要数判定手段が、所望のすべての終端ノードに対応する経路リストに必要数の経路候補が格納されるまで上記の処理を続ける繰り返しステップと、を行い、前記最小コスト経路削除ステップにおいて、当該経路候補の終端ノードが所望の終端ノードの場合は、当該終端ノードに対応する経路リスト内に当該経路候補を格納するステップを含むことを特徴とする複数経路探索方法。前記記憶手段に、各経路候補リストで、すでに最小経路として削除された経路候補数も含めた経路候補数上限を設定し、前記第1の経路候補作成ステップ及び前記第2の経路候補作成ステップにおいて、前記経路候補数上限を超えない範囲で、経路候補リスト内に経路候補を格納する経路候補格納判定ステップを含む請求項1記載の複数経路探索方法。経路候補格納判定ステップにおいて、新経路候補を、当該経路候補リストの終端ノード/リンク終端点に対応する経路候補リストに格納するかどうかを決定する際に、当該経路候補リスト内で最小経路として削除された経路候補数が当該経路候補リストの経路候補数上限値に達している場合は、当該新経路候補を当該経路候補リストに格納しない請求項2記載の複数経路探索方法。前記経路候補格納判定ステップにおいて、新経路候補を、当該経路候補リストの終端ノード/リンク終端点に対応する経路候補リストに格納するかどうかを決定する際に、1当該経路候補リスト内で最小経路として削除された経路候補数が当該経路候補リストの経路候補数上限値に達しておらず、且2当該経路候補リストで最小経路として削除された経路候補数と経路候補リスト内の経路候補数の合計が経路候補数上限と等しい場合は、当該新経路候補の経路コストが当該経路候補リスト中で最大経路コストを持つ経路候補と比較し、その最大経路コストより新経路候補の経路コストが小さい場合は、最大経路コストを持つ経路候補を当該経路候補リストから削除し、新たに新経路候補を当該経路候補リストに格納する請求項3記載の複数経路探索方法。前記最小コスト経路削除ステップ、または、前記経路候補判定ステップにおいて、経路候補の経路コストを、経路を構成するリンクのコストの総計とするのではなく、前記始点ノードからの経由するリンク数が大きい経路は経路コストが大きくなるようにリンクコストに比重をつける経路コスト調整ステップを含む請求項1または4記載の複数経路探索方法。前記経路コスト調整ステップにおいて、すべての経路候補リストの中で最小経路コストを持つ経路候補をpathとし、その終端ノードからのリンクをEとし、その経路候補とリンクを繋げて新しくできた経路候補をpathとした場合、その新経路候補の経路コストpathを、pathpathEβhopと定義するここでEはリンクコスト、hopはpathが経由するリンク数、βは正数請求項5記載の複数経路探索方法。コストが付与されたリンクによって複数のノードが互いに接続されて形成されるネットワーク上で、所望の始点ノードから所望の終端ノード複数可に至るまでの経路を複数本探索する複数経路探索装置であって、経路候補リストを格納する記憶手段と、前記始点ノードから接続可能な全てのリンクを選択して経路候補を作成し、前記記憶手段の各リンクの終端ノードあるいは終端点に対応する経路候補リスト内に格納する第1の経路候補作成手段と、前記記憶手段のすべての経路候補リストの中で、経路コストが最小となる1本の経路候補を検索し、該経路候補リストから削除する最小コスト経路削除手段と、前記検索された経路候補の終端ノードから接続可能な全てのリンクを更に選択し、当該経路候補に選択された各リンクを加えた新たな経路候補を作成し、各リンクの終端ノードあるいは終端点に対応する経路候補リスト内に格納する第2の経路候補作成手段と、必要数判定手段が、所望のすべての終端ノードに対応する経路リストに必要数の経路候補が格納されるまで前記第1の経路候補作成手段、前記最小コスト経路削除手段、前記第2の経路候補作成手段の各処理を繰り返す必要数判定手段と、を有し、前記最小コスト経路削除手段は、当該経路候補の終端ノードが所望の終端ノードの場合は、当該終端ノードに対応する経路リスト内に当該経路候補を格納する手段を含むことを特徴とする複数経路探索装置。コンピュータを、請求項7に記載の複数経路探索装置の各手段として機能させるための複数経路探索プログラム。既存のkshortestpathアルゴリズムは、始点ノード数、終端ノード数共に1であり、もし複数の終端ノードまでのk本の経路を求める場合は、終端ノード数回のkshortestpathアルゴリズム走行が必要となる。この場合、処理時間が大きくなる課題がある。また、kshortestpathアルゴリズムは経路コストが小さい経路から順番にk本の経路を算出するが、これらの経路がトラフィック分散の観点で最適ではない場合がある。つまり、複数の経路が同一のリンクを使う可能性が高く、そのリンクの利用帯域が大きくなり、結果的にボトルネックとなるリンクを作成してしまう課題がある。本発明は、上記の点に鑑みなされたもので、複数の経路探索処理時間を短縮でき、kshortestpathアルゴリズムの結果として多く見られる複数経路による始点ノードからの経由数が小さい少数の固定リンクの過剰利用を避けることが可能な複数経路探索方法及び装置を提供することを目的とする。上記の課題を解決するため、本発明請求項1は、コストが付与されたリンクによって複数のノードが互いに接続されて形成されるネットワーク上で、所望の始点ノードから所望の終端ノード複数可に至るまでの経路を複数本探索する複数経路探索方法であって、経路候補作成手段が、前記始点ノードから接続可能な全てのリンクを選択して経路候補を作成し、記憶手段内の、各リンクの終端ノードあるいは終端点に対応する経路候補リスト内に格納する第1の経路候補作成ステップと、経路候補リスト制御手段が、前記記憶手段内のすべての経路候補リストの中で、経路コストが最小となる1本の経路候補を検索し、該経路候補リストから削除する最小コスト経路削除ステップと、前記経路候補リスト制御手段が、前記検索された経路候補の終端ノードから接続可能な全てのリンクを更に選択し、当該経路候補に選択された各リンクを加えた新たな経路候補を作成し、各リンクの終端ノードあるいは終端点に対応する経路候補リスト内に格納する第2の経路候補作成ステップと、必要数判定手段が、所望のすべての終端ノードに対応する経路リストに必要数の経路候補が格納されるまで上記の処理を続ける繰り返しステップと、を行い、前記最小コスト経路削除ステップにおいて、当該経路候補の終端ノードが所望の終端ノードの場合は、当該終端ノードに対応する経路リスト内に当該経路候補を格納するステップを含む。また、本発明請求項2は、請求項2において、前記記憶手段に、各経路候補リストで、すでに最小経路として削除された経路候補数も含めた経路候補数上限を設定し、前記第1の経路候補作成ステップ及び前記第2の経路候補作成ステップにおいて、前記経路候補数上限を超えない範囲で、経路候補リスト内に経路候補を格納する経路候補格納判定ステップを含む。また、本発明請求項3は、請求項2の前記経路候補格納判定ステップにおいて、新経路候補を、当該経路候補リストの終端ノード/リンク終端点に対応する経路候補リストに格納するかどうかを決定する際に、当該経路候補リスト内で最小経路として削除された経路候補数が当該経路候補リストの経路候補数上限値に達している場合は、当該新経路候補を当該経路候補リストに格納しない。また、本発明請求項4は、請求項3の前記経路候補格納判定ステップにおいて、新経路候補を、当該経路候補リストの終端ノード/リンク終端点に対応する経路候補リストに格納するかどうかを決定する際に、1当該経路候補リスト内で最小経路として削除された経路候補数が当該経路候補リストの経路候補数上限値に達しておらず、且2当該経路候補リストで最小経路として削除された経路候補数と経路候補リスト内の経路候補数の合計が経路候補数上限と等しい場合は、当該新経路候補の経路コストが当該経路候補リスト中で最大経路コストを持つ経路候補と比較し、その最大経路コストより新経路候補の経路コストが小さい場合は、最大経路コストを持つ経路候補を当該経路候補リストから削除し、新たに新経路候補を当該経路候補リストに格納する。また、本発明請求項5は、請求項1または4の前記最小コスト経路削除ステップ、または、前記経路候補判定ステップにおいて、経路候補の経路コストを、経路を構成するリンクのコストの総計とするのではなく、前記始点ノードからの経由するリンク数が大きい経路は経路コストが大きくなるようにリンクコストに比重をつける経路コスト調整ステップを含む。また、本発明請求項6は、請求項5の前記経路コスト調整ステップにおいて、すべての経路候補リストの中で最小経路コストを持つ経路候補をpathとし、その終端ノードからのリンクをEとし、その経路候補とリンクを繋げて新しくできた経路候補をpathとした場合、その新経路候補の経路コストpathを、pathpathEβhopと定義するここでEはリンクコスト、hopはpathが経由するリンク数、βは正数。本発明請求項7は、コストが付与されたリンクによって複数のノードが互いに接続されて形成されるネットワーク上で、所望の始点ノードから所望の終端ノード複数可に至るまでの経路を複数本探索する複数経路探索装置であって、経路候補リストを格納する記憶手段と、前記始点ノードから接続可能な全てのリンクを選択して経路候補を作成し、前記記憶手段の各リンクの終端ノードあるいは終端点に対応する経路候補リスト内に格納する第1の経路候補作成手段と、前記記憶手段のすべての経路候補リストの中で、経路コストが最小となる1本の経路候補を検索し、該経路候補リストから削除する最小コスト経路削除手段と、前記検索された経路候補の終端ノードから接続可能な全てのリンクを更に選択し、当該経路候補に選択された各リンクを加えた新たな経路候補を作成し、各リンクの終端ノードあるいは終端点に対応する経路候補リスト内に格納する第2の経路候補作成手段と、必要数判定手段が、所望のすべての終端ノードに対応する経路リストに必要数の経路候補が格納されるまで前記第1の経路候補作成手段、前記最小コスト経路削除手段、前記第2の経路候補作成手段の各処理を繰り返す必要数判定手段と、を有し、前記最小コスト経路削除手段は、当該経路候補の終端ノードが所望の終端ノードの場合は、当該終端ノードに対応する経路リスト内に当該経路候補を格納する手段を含む。本発明請求項8は、コンピュータを、請求項7に記載の複数経路探索装置の各手段として機能させるための複数経路探索プログラムである。上記のように、本発明は、ネットワーク上の全ての経路候補リストの中で、経路コストが最小となる1本の経路候補を検索し、当該経路候補の終端ノードが所望の終端ノードの場合は、当該終端ノードに対応する経路リスト内に当該経路候補を格納し、所望の終端ノードに対応する経路リストに必要数の経路候補が格納されるまで上記の処理を繰り返すことにより、kshortestpathアルゴリズムを終端ノード数回実行する必要がなく、処理時間を短縮することが可能となる。以下図面と共に、本発明の実施の形態を説明する。まず、本発明の概要を説明する。図2は、本発明で作成する始点ノードと終端ノードの複数経路探索方法のネットワークへの適用例を示す。同図では、複数経路探索装置としてPCEvol34no3pp5966151987参照の各ノード22にリンクされ、このフィボナッチヒープでの最小ノードがすべての経路候補リスト内での最小経路コストを持つ経路候補となる。PCE1内で保持する3つのマルチパス終端ノード12,15,18は、それぞれ経路リスト122、152、182を保持し、その経路リストの中に、対応する経路候補リスト121、151,181から選択された、すべての経路候補リストの中で最小経路コストを持つ経路候補が順番に格納されていく。なお、図3では各ノードに対応させて経路候補リストを保持しているが、図4のように、経路候補リストをリンクの終端点毎に保持することも可能である。図4においては、図3におけるノード14においてリンク終端点毎に経路候補リストを保持する例を示している。ノード14には3つのリンク終端点が存在するので、各終端点に応じて142、143,144の3つの経路候補リストが対応している。図5は、本発明の第1の実施の形態における装置構成を示す。同図に示す複数経路探索装置は、ノード選択部10、リンク選択部20、経路候補作成部30、経路リスト制御部40から構成される。以下に、上記の構成における動作を図6のフローに沿って説明する。ステップ201ノード選択部10は、ノード情報が入力されると、ノードの選択を行う。このとき、最初は始点ノードが選択され、以降は、ステップ204で選択された経路候補の終端ノードとなる。ステップ202リンク選択部20は、ステップ201で選択されたノードから出ているすべてのリンクを選択する。ステップ203経路候補作成部30は、ステップ202で選択された各リンクを直前のステップ204で選択した経路候補の後尾につなげた新しい経路候補を作成し、経路リスト制御部40に出力する。経路リスト制御部40は、始点ノードから上記で選択されたリンクの終端を持つノードまでの経路ノード順列を、終端ノード/最終リンク終端点に対応する経路リスト記憶部50の経路候補リストに追加する。この際、経路候補上に同じノードを2回通るような経路候補は対象から外す。なお、予め経路候補数上限が設定されている場合は、その上限数以下の経路候補数を維持する当該処理については、図7にて詳述する。なお、新規経路候補の経路コストは、直前のステップ304で選択された経路候補の経路コストに追加されるリンクコストを追加した形になるが、経路が経由するリンク数が多い場合は経路コストが大きくなるように比重をつけることも可能であり、その一例として、新経路候補の経路コストpathをpathpathEβhopと定義することも可能である。ここで、βを正数とするとリンク数に応じて比重が設定されるが、βを0に設定すると従来手法の経路コストと同じとなる。当該処理を行うことで、始点ノードからの経由数が小さいリンクのコストが、経由数が大きいリンクのコストに比較して小さくなり、結果として経由数が小さいリンクが均等に複数の経路を探索する際に選択されることになる。このため、kshortestpathアルゴリズムの結果として多く見られる複数経路による固定リンクの過剰利用が避けられる。ステップ204経路リスト制御部40は、図3のフィボナッチヒープ22を用いてすべての経路候補リストの中で最小の経路候補を選択し、その経路候補を取り出し、当該の経路候補リストから削除する。ステップ205ステップ204で選択した経路候補の終端ノードが所望の終端ノードであるかどうかを判断し、所望の終端ノードである場合は、ステップ206に移行し、そうでない場合はステップ201に移行する。ステップ206経路リスト制御部40は、当該経路候補を経路リスト記憶部50の当該終端ノードに対応する経路リストに格納する。ステップ207経路リスト制御部40は、すべての所望の終端ノードに対応する経路リストに所望数の経路が格納されたかどうかを判断し、すべて格納された場合には処理を終了し、まだ格納されきれていない場合は、ステップ201に戻る。[第2の実施の形態]本実施の形態では、経路候補数の管理方法について説明する。図7は、本発明の第2の実施の形態における経路候補リストのデータ構造と新規経路候補受付判断を説明するための図である。本実施の形態では、経路候補リスト記憶部50内に、経路候補条件管理メモリ41、最小経路として削除された経路候補数管理メモリ42、最小経路として削除された経路候補数を含めた経路候補数管理メモリ43を有する。経路候補数上限管理メモリ41は、すでに削除された経路候補数を含めた当該経路候補リスト中の経路候補数の上限を管理する。ここではその上限値をAとする。最小経路として削除された経路候補数管理メモリ42は、当該経路候補リストで最小経路として削除された経路数を管理する。ここではその値をBとする。最小経路として削除された経路候補数を含めた経路候補数管理メモリ43は、すでに最小経路として削除された経路候補数を含めた当該経路候補リスト中の経路候補数を管理する。ここではその値をCとする。同図の経路候補リストに示す、経路候補リスト内で最小の経路コストを持つ経路候補44は、フィボナッチヒープ22のノードにリンクしている。経路候補45は経路候補リスト内で最大の経路コストを持つ経路候補である。上記の各管理メモリでそれぞれ保持される値、A,B,Cについて、経路リスト制御部40は、以下のような制御を行うものとする。1C<Aの場合は、経路候補数上限まで経路候補が当該経路候補リストに格納されていないので、当該経路候補リストにステップ203で生成された新経路候補を格納する。2B=Aの場合は経路候補リストに経路候補を格納しない。3C=A∧B≠Aの場合は、当該新規経路候補46を経路候補45の経路コストと比較し、当該新規経路候補の経路コストが経路候補45の経路コストより小さいときのみ、経路候補45を経路候補リストから削除した後に、新規経路候補46を経路候補リストに格納する。上記のような制御を行うことにより、図6に示す処理において、扱う経路候補数を制限することが可能になり、さらなる処理時間の短縮が可能になる。また、各ノード、リンクの終端点に対応する経路候補リストの経路候補数上限の設定ができるので、より容量の大きいノード、リンクには高い上限値を設ける等の調整が可能となる。なお、上記の図5に示す複数経路探索装置の構成要素の動作をプログラムとして構築し、当該装置として利用されるコンピュータにインストールして実行させる、または、ネットワークを介して流通させることが可能である。本発明は、上記の実施の形態に限定されることなく、特許請求の範囲内において、種々変更応用が可能である。"