(57)【要約】【課題】グラフに含まれる各頂点間の最短経路を表す最短経路行列について、最短経路を高速に復元可能な最短経路行列を生成する。【解決手段】付与部１２が、複数の頂点と頂点間を接続する辺とで表されたグラフにおける各頂点間の最短経路上の２以上の辺を含む中間経路の各々に識別情報を付与し、生成部１４が、グラフに含まれる全頂点から全頂点への最短経路を表す行列の各要素の値として、各要素に対応する行及び列に対応する頂点間の最短経路上の中間経路の識別情報を用いて最短経路行列を生成する。【選択図】図８
2019139576.tif 000002
【特許請求の範囲】
【請求項１】
複数の頂点と頂点間を接続する辺とで表されたグラフにおける各頂点間の最短経路上の２以上の辺を含む中間経路の各々に識別情報を付与し、
前記グラフに含まれる全頂点から全頂点への最短経路を表す行列の各要素の値として、前記各要素に対応する行及び列に対応する頂点間の最短経路上の中間経路の識別情報を用いて最短経路行列を生成する
ことを含む処理をコンピュータに実行させるための最短経路行列生成プログラム。
【請求項２】
前記グラフを、指定された数の部分グラフに分割し、各部分グラフについて、前記部分グラフに含まれる頂点を用いて表され、かつ他の部分グラフと辺で接続された頂点を始点及び終点とする経路を、前記中間経路とする請求項１に記載の最短経路行列生成プログラム。
【請求項３】
前記中間経路と、前記中間経路の識別情報とを対応付けた中間経路表を生成し、
前記最短経路行列の各要素の値として前記中間経路の識別情報を用いる際、前記中間経路表を参照する
請求項１又は請求項２に記載の最短経路行列生成プログラム。
【請求項４】
複数の頂点と頂点間を接続する辺とで表されたグラフにおける各頂点間の最短経路上の２以上の辺を含む中間経路の各々に識別情報を付与する付与部と、
前記グラフに含まれる全頂点から全頂点への最短経路を表す行列の各要素の値として、前記各要素に対応する行及び列に対応する頂点間の最短経路上の中間経路の識別情報を用いて最短経路行列を生成する生成部と、
を含む最短経路行列生成装置。
【請求項５】
複数の頂点と頂点間を接続する辺とで表されたグラフにおける各頂点間の最短経路上の２以上の辺を含む中間経路の各々に識別情報を付与し、
前記グラフに含まれる全頂点から全頂点への最短経路を表す行列の各要素の値として、前記各要素に対応する行及び列に対応する頂点間の最短経路上の中間経路の識別情報を用いて最短経路行列を生成する
ことを含む処理をコンピュータが実行する最短経路行列生成方法。
【発明の詳細な説明】
【技術分野】
【０００１】
開示の技術は、最短経路行列生成プログラム、最短経路行列生成装置、及び最短経路行列生成方法に関する。
【背景技術】
【０００２】
近年、ＳＮＳ（Social Networking Service）、顧客関係管理、ネットワーク管理、バイオエンジニアリング、輸送などの分野で、ネットワーク的データを活用するアプリケーションが増えてきている。ネットワーク的データとは、各要素と、要素間の関係とを表すデータである。例えば、インターネット、通信網、交通網、輸送網などのいわゆるネットワークや、人間関係、分子間の関係などを表すデータがある。
【０００３】
また、ネットワーク的データは、各要素に対応する頂点（vertex）と、関係する要素間に対応する頂点間を結ぶ辺（edge）とを含むグラフで表すことができる。例えば、人間関係を表すネットワーク的データのグラフは、一人の人間を一つの要素として頂点で表し、人間同士の関係を、頂点間を結ぶ辺として表すことができる。
【０００４】
なお、グラフＧに含まれる頂点の集合をＶ、辺の集合をＥとすると、グラフＧは、Ｇ＝（Ｖ，Ｅ）と表すことができる。また、グラフにおいて、１つの辺で結ばれた２つの頂点は、「隣接している（adjacent）」という。また、頂点の列ｖ０，ｖ１，・・・，ｖｎにおいて、任意のｉ（１≦ｉ≦ｎ）に対して、頂点ｖｉ−１と頂点ｖｉとが隣接している場合、この頂点の列を経路（パス）と呼び、その長さはｎである。また、頂点ｖ０を経路の「始点」、頂点ｖｎを経路の「終点」という。また、２頂点間の経路のうち、長さが最も短い経路を最短経路といい、２頂点間の最短経路の長さを距離という。
【０００５】
また、上記のようなグラフには、辺に向きがない無向グラフと、辺に向きがある有向グラフとがある。例えば、道路が全て両方向から通行可能であれば、道路網を無向グラフで表現できる。しかし、一方通行の道路を含む道路網は、有向グラフでないと表現できない。なお、上記の各定義は、無向グラフを前提にしている。
【０００６】
また、上記のようなネットワーク的データのグラフには、各辺に重みが付与された重みありグラフと、各辺に重みが付与されていない重みなしグラフとがある。例えば、線路網は、各駅を頂点に対応させ、隣り合う駅同士に対応する頂点間を辺で結び、駅間の距離に応じた重みを各辺に付与することで、重みありグラフとして表現できる。一方、人間関係を表すネットワーク的データにおいて、関係の有無のみに着目し、関係の親密さは問わない場合、人間関係は重みなしグラフで表現できることになる。
【０００７】
一方、ネットワーク的データの中からビジネス、経営、研究などに重要な情報を抽出するなどのデータ分析に対するニーズが高まっている。ネットワーク的データを表すグラフに対するデータ分析も同様にニーズがある。例えば、グラフにおいて、２頂点間の最短経路を求めることは、グラフに対するデータ分析として重要である。
【０００８】
以下に重みなし無向グラフが有効な３つの例を挙げる。例えば、人間関係を表すネットワーク的データでは、ＳＮＳにおいて友人関係にある人間同士や、社内でメールのやり取りを行なっている人間同士などを辺で結んだグラフが考えられる。このグラフ中に頂点として表されているある人から、その人とは直接の関係はない別の人にアクセスしたい場合を考える。この場合、グラフにおいて、二人を表す頂点間の最短経路がわかれば、最も少ない手間で、経路上に存在する頂点に対応する知人を通して、目的とする人にコンタクトを取ることができる。
【０００９】
また、コンピュータネットワークを表すグラフでは、頂点間の最短経路がわかれば、頂点に対応する装置間において、通信回数が最小の経路で通信を行なうことが可能となる。
【００１０】
また、例えば、ルービックキューブ（登録商標）の各局面を頂点、１つの回転で遷移できる局面同士を辺で結ぶグラフを考える。この場合、ある局面に対応する頂点から、最終局面（各面が１色のみの状態）に対応する頂点までの最短経路は、最適（最小手数の）解を示すことになる。
【００１１】
なお、グラフにおける２頂点間の最短経路を最短経路木（一次元配列）として表現する技術が存在する。経路木を用いて最短経路を表現する技術の一例として、通信網中の３つ以上のノード間の最短路を検出する装置が提案されている。この装置では、全てのノード、パス及び各パスの長さ、基本閉路及び指定ノードからなる通信網の経路情報を入力する。そして、この装置は、各指定ノード対の最短路により基準部分網を構成し、基準部分網中の指定ノード以外の中間ノードを検出し、基準部分網に含まれる閉路を所定の基本閉路に分解し、基本閉路中の中間ノードを検出する。また、この装置は、選択された中間ノードと指定ノードとにより比較部分網を構成し、基準部分網の最短木長と比較部分網の最短木長とを比較する。
【先行技術文献】
【特許文献】
【００１２】
【特許文献１】特開平８−１９５８０７号公報
【発明の概要】
【発明が解決しようとする課題】
【００１３】
グラフにおける全頂点から全頂点への最短経路は、頂点毎に、その頂点から他の全頂点への最短経路を最短経路木（一次元配列）として表現し、グラフ全体の最短経路木群を最短経路行列（二次元配列）として表現することができる。全頂点から全頂点への最短経路を求めるには、多大な時間を要するため、各頂点間の最短経路を最短経路行列の形で予め求めておき、主記憶や二次記憶などの記憶部に格納しておく。そして、頂点を指定した最短経路の問い合わせを受け付けた場合に、記憶部から最短経路行列を読み出して、該当の最短経路を復元して応答するということが可能である。
【００１４】
例えば、鉄道網において、各駅への他の全駅からの最短経路を駅毎に求めておき、それを最短経路行列で表現し、最短経路行列を記憶部に記憶しておく。そして、ユーザから任意の二駅間の最短経路の問い合わせを受け付けた場合に、記憶部に記憶された最短経路行列から、該当の二駅間の最短経路木を読み出して、その最短経路木が示す最短経路を応答する。これにより、最短経路の問い合わせに対して高速に応答することができる。
【００１５】
ただし、駅の数をｎとすると、単純な方式では、駅毎の最短経路木を保持するためにＯ（ｎ）のメモリ量が必要であり、駅全体についての最短経路行列を保持するために必要なメモリ量は、Ｏ（ｎ２）となる。ここで、Ｏ（ｘ）は、ｘの定数倍であること、すなわちｘに比例している量であることを意味する。道路網などの頂点数が大きいグラフでは、最短経路行列のサイズ（データ量）は膨大なものになる。例えば、頂点数が１億個あるグラフについて、最短経路行列の１要素当たりのデータ量が４バイトであるとすると、最短経路行列は、４０ペタ（＝４×１０８×１０８）バイトのサイズを要することになる。
【００１６】
そこで、最短経路行列を記憶部に記憶する際、圧縮して記憶することでそのサイズを大幅に削減することが可能である。
【００１７】
しかし、従来技術を用いて生成された最短経路行列を圧縮して記憶しておいた場合、この圧縮された最短経路行列から、要求のあった２頂点間の最短経路を復元するには時間を要する。
【００１８】
開示の技術は、一つの側面として、グラフに含まれる各頂点間の最短経路を表す最短経路行列について、最短経路を高速に復元可能な最短経路行列を生成することを目的とする。
【課題を解決するための手段】
【００１９】
一つの態様では、複数の頂点と頂点間を接続する辺とで表されたグラフにおける各頂点間の最短経路上の２以上の辺を含む中間経路の各々に識別情報を付与する。そして、前記グラフに含まれる全頂点から全頂点への最短経路を表す行列の各要素の値として、前記各要素に対応する行及び列に対応する頂点間の最短経路上の中間経路の識別情報を用いて最短経路行列を生成する。
【発明の効果】
【００２０】
一つの側面として、グラフに含まれる各頂点間の最短経路を表す最短経路行列について、最短経路を高速に復元可能な最短経路行列を生成することができる、という効果を有する。
【図面の簡単な説明】
【００２１】
【図１】グラフの一例を示す図である。
【図２】最短経路木の一例を示す図である。
【図３】最短経路木を表す配列の一例を示す図である。
【図４】最短経路行列の一例を示す図である。
【図５】参考例に係る情報処理装置の機能ブロック図である。
【図６】参考例における最短経路行列生成処理の一例を示すフローチャートである。
【図７】参考例における最短経路復元処理の一例を示すフローチャートである。
【図８】実施形態に係る情報処理装置の機能ブロック図である。
【図９】幅優先探索アルゴリズムを説明するためのフローチャートである。
【図１０】幅優先探索アルゴリズムを説明するためのグラフの一例である。
【図１１】幅優先探索アルゴリズムによる最短経路行列の生成を説明するための図である。
【図１２】実施形態に係る情報処理装置として機能するコンピュータの概略構成を示すブロック図である。
【図１３】実施形態における最短経路行列生成処理の一例を示すフローチャートである。
【図１４】表生成処理の一例を示すフローチャートである。
【図１５】行列生成処理の一例を示すフローチャートである。
【図１６】（ｋ，ｍ’）取得処理の一例を示すフローチャートである。
【図１７】具体例を説明するためのグラフの一例を示す図である。
【図１８】具体例におけるクラスタリング結果の一例を示す図である。
【図１９】実施形態における最短経路行列の生成を説明するための図である。
【図２０】実施形態における最短経路行列の生成を説明するための図である。
【図２１】実施形態における最短経路復元処理の一例を示すフローチャートである。
【図２２】比較方式と本方式とのアクセス回数の比較を説明するための図である。
【図２３】比較方式と本方式とのアクセス回数の比較結果を示す図である。
【図２４】クラスタリングの一例を示す図である。
【図２５】分割数によるアクセス回数の比較結果を示す図である。
【図２６】非連結なグラフの最短経路行列の生成を説明するための図である。
【発明を実施するための形態】
【００２２】
以下の実施形態では、頂点と、頂点間を接続する辺とで構成されたグラフに含まれる各頂点について、他の頂点の各々との最短経路を表現する最短経路行列を生成する。
【００２３】
まず、実施形態の詳細を説明する前に、最短経路行列の概要について説明する。
【００２４】
図１にグラフの一例を示す。図１において、頂点を黒丸で表し、頂点に併記した数字で頂点の識別番号（以下、「頂点番号」という）を表している。以下の各図においても同様である。なお、本明細書では、グラフのｎ個の頂点に１からｎまでの頂点番号を付与して、各頂点を識別するものとする。以下、頂点番号ｘの頂点を「頂点ｘ」と表記する。
【００２５】
図１に示すグラフにおいて、各頂点から頂点１への最短経路を考える。このグラフの最短経路は、図２に示すような最短経路木で表すことができる。
【００２６】
なお、一般的に、最短経路木に含まれる頂点数をｎとした場合、最短経路木に含まれる辺の数はｎ−１である。また、最短経路木は、ある頂点を一番上に、それに繋がる頂点（群）をその下に、さらにその頂点（群）に繋がる頂点をその下に、・・・というように、木を逆にしたような形に書くことができる。この場合、一番上の頂点を「根」という。また、その頂点より下に頂点が存在しない頂点を「葉」という。また、ある頂点ｖのすぐ下に繋がる頂点ｗを頂点ｖの子、頂点ｖを頂点ｗの親という。
【００２７】
図２上図は、最短経路の終点である頂点１を根とする最短経路木であり、図２下図は、根を一番上にして表した最短経路木の例である。例えば、頂点６から頂点１への最短経路は、頂点６から順にその親を辿って頂点１に到達するまでに経由する頂点の列として求めることができる。
【００２８】
頂点１を根とする最短経路木は、図３に示すような配列として表現することができる。図３の例では、配列のｉ番目の要素には、頂点ｉから頂点１へ辿る際に次に辿るべき頂点の頂点番号、すなわち頂点ｉから頂点１への最短経路における頂点ｉの親の頂点番号が格納されている。頂点１は最短経路の終点であり、親は存在しないため、頂点１に対応する配列の要素には、親が存在しないことを示す値を格納する。その値としては、最短経路行列の値として取りえない値、例えば、最大の整数値とすることとし、ここでは、その値をＥで表す。すなわち、Ｅが格納されている要素に対応する頂点は、最短経路の終点であることを示している。
【００２９】
図１に示すグラフに対して、全頂点から全頂点への最短経路木を示す配列を、頂点１に対応する配列から頂点８に対応する配列まで順に並べて二次元の配列として表現した最短経路行列を、図４に示す。このような最短経路行列から最短経路を復元する場合、その最短経路の長さをＬとすると、Ｌ個の最短経路行列の要素にアクセスする必要がある。最短経路行列の要素へのアクセスにおおよそ比例したディスクの入出力回数を要するので、この最短経路行列へのアクセス回数を削減することができれば、ディスクの入出力回数を削減することができ、最短経路行列から高速に最短経路を復元することができる。
【００３０】
そこで、以下の実施形態では、最短経路行列の要素の値として、上述の親の頂点番号だけではなく、最短経路上に現れる長さ２以上の経路（以下、「中間経路」という）の識別情報を用いる。
【００３１】
なお、中間経路としては、最短経路上に現れる点（以下、「中間点」という）、辺（以下、「中間辺」という）も存在する。中間点は長さ０、中間辺は長さ１の中間経路と考えることができる。ただし、以下の実施形態では、詳細は後述するが、高速に最短経路を復元することを目的とするため、中間経路として、長さ２以上のものを対象とする。なお、以下では、説明を簡単にするため、図１に示すような重みなし無向グラフを例に説明する。重みなしであるため、各辺の長さを１と捉える。したがって、長さ２以上の経路とは、２以上の辺を含む経路を意味する。
【００３２】
＜参考例＞
次に、以下で詳述する実施形態の理解を助けるために、最短経路行列の要素の値として、中間点及び中間辺の識別情報を用いる場合を参考例として説明する。
【００３３】
図５に、参考例に係る情報処理装置１００Ｒの機能ブロック図を示す。情報処理装置１００Ｒは、付与部１２Ｒ及び生成部１４Ｒを含む最短経路行列生成部１０Ｒと、復元部２２Ｒを含む最短経路復元部２０Ｒとを含む。
【００３４】
付与部１２Ｒは、グラフに含まれる各頂点間の最短経路を求める。最短経路の求め方は、従来既知の手法を用いることができる。そして、付与部１２Ｒは、最短経路上の中間経路である中間点及び中間辺の各々に、最短経路行列の要素の値として使用するための識別情報を付与する。上述したように、グラフのｎ個の頂点には、１からｎまでの頂点番号が付与されているため、中間点の識別情報としては、この頂点番号をそのまま使用する。辺の識別情報は、通常、辺の両端の頂点の頂点番号の組で表される。この辺の識別情報を中間辺の識別情報として用いてもよい。ただし、この場合、１つの中間辺の識別情報のデータ量は、頂点番号２つ分のデータ量となるため、データ量の小さい識別情報を付与し直してもよい。本参考例では、 付与部１２Ｒは、ｎを全頂点数として、中間辺の各々に対して、ｎ＋１、ｎ＋２、・・・という識別情報を付与するものとする。以下では、付与部１２Ｒにより中間辺に付与される識別情報を「中間辺番号」という。
【００３５】
付与部１２Ｒは、中間辺と、その中間辺に付与した中間辺番号とを対応付けて記憶した２つの中間経路表Ｐ１、Ｐ２を生成する。Ｐ１は最短経路行列生成において、Ｐ２は最短経路行列復元において用いられる。なお、全ての中間辺に中間辺番号を付与する必要はなく、最短経路行列で用いる中間辺に対してのみ中間辺番号を付与して、中間経路表に記憶すればよい。これにより、中間経路表のサイズを抑えることができる。なお、中間経路表としては、ハッシュ表などのインデクス付表を用いることができる。以下では、中間経路表Ｐ１において、両端が頂点ｋ１及び頂点ｋ２である中間辺に中間辺番号「ｘ」を付与したことを表すレコードを、Ｐ１［（ｋ１，ｋ２）］＝ｘと表記する。Ｐ２は逆に中間辺番号に中間辺を対応させるので、Ｐ２［ｘ］＝（ｋ１，ｋ２）となる。
【００３６】
生成部１４Ｒは、グラフに含まれる全頂点から全頂点への最短経路を表す行列の各要素の値として、各要素に対応する行及び列に対応する頂点間の最短経路上の頂点（中間点を含む）の頂点番号、及び中間辺の中間辺番号を用いて、最短経路行列を生成する。
【００３７】
ここで、中間点の頂点番号を用いた最短経路行列の生成について考える。頂点ｉから頂点ｊへの最短経路、すなわち、頂点ｉから頂点ｊへの頂点の列を、σ［ｉ，ｊ］と表す。例えば、図１に示すグラフにおいて、頂点８から頂点１への最短経路、すなわちσ［８，１］は、８，７，５，３，１である。このことを、σ［８，１］＝［８，７，５，３，１］と表記する。
【００３８】
また、最短経路行列をＳで表した際、最短経路行列Ｓのｉ行ｊ列の要素をＳ［ｉ，ｊ］と表記する。Ｓ［ｉ，ｊ］には、頂点ｉから頂点ｊへの最短経路における頂点ｉの親の頂点番号だけでなく、頂点ｉから頂点ｊへの最短経路上の中間点の頂点番号が格納される。例えば、図２に示すグラフの最短経路行列について、中間点を使用しない場合には、図４に示すように、Ｓ［８，１］＝７である。生成部１４Ｒは、これを、例えば、σ［８，１］の中間点を用いて、Ｓ［８，１］＝３とすることができる。
【００３９】
具体的には、生成部１４Ｒは、付与部１２Ｒにより求められた最短経路σ［ｉ，ｊ］の情報から中間点を取得する。そして、生成部１４Ｒは、取得した中間点の中から選択した中間点の頂点番号をＳ［ｉ，ｊ］の要素の値として格納する。頂点番号の選択方法としては、例えば、ランダムに選択したり、最も小さい頂点番号を選択したり、既に他の要素の値として選択されている頂点番号のうち、出現頻度が最も高い頂点番号を選択したりするなど、任意の方法を採用することができる。
【００４０】
中間点の場合と同様に、中間辺の中間辺番号を用いた最短経路行列の生成について考える。生成部１４Ｒは、付与部１２Ｒにより求められた最短経路σ［ｉ，ｊ］の情報から取得した中間点に、辺を構成する中間点の組が含まれる場合、その中間点の組で構成される中間辺の中間辺番号を、Ｓ［ｉ，ｊ］の要素の値として格納してもよい。具体的には、上記の中間点の場合と同様に、生成部１４Ｒは、最短経路σ［ｉ，ｊ］の情報から中間辺を取得し、取得した中間辺の中から最短経路行列の要素の値として用いる中間辺を選択する。中間辺を選択する際には、付与部１２Ｒが生成した中間経路表Ｐ１が参照される。そして、生成部１４Ｒは、選択した中間辺の中間辺番号を中間経路表Ｐ１から取得して、Ｓ［ｉ，ｊ］の要素の値として格納する。
【００４１】
生成部１４Ｒは、生成した最短経路行列Ｓを圧縮する。最短経路行列Ｓは、ｎ画素×ｎ画素の画像と同じデータ構造であるため、ロスレスの画像の圧縮アルゴリズムなどを用いて、圧縮することができる。生成部１４Ｒは、圧縮した最短経路行列Ｓを、付与部１２Ｒが生成した中間経路表Ｐ２と共に、行列データベース（ＤＢ）３０Ｒに格納して、所定の記憶領域に記憶する。
【００４２】
なお、生成部１４Ｒは、中間経路表Ｐ２も圧縮して、行列ＤＢ３０Ｒに格納することもできる。中間経路表Ｐ２の圧縮には、既存の圧縮技術を用いることができる。例えば、インデクスとしてＢ−ｔｒｅｅを使うのであれば、内部でキー順にソートされるので、キーのプレフィクスを圧縮することができる。また、どのような中間経路表にも使える単純な方法であるが、既存の情報圧縮技術を使って入出力におけるページ単位に圧縮することもできる。
【００４３】
復元部２２Ｒは、始点及び終点を指定した最短経路の問い合わせを受け付けると、行列ＤＢ３０Ｒに格納された最短経路行列Ｓ及び中間経路表Ｐ２を伸長を行いながら用いて、指定された始点及び終点に対応する頂点間の最短経路を復元する。
【００４４】
具体的には、指定された始点に対応する頂点がｉ（以下、「始点ｉ」と表記する）、終点に対応する頂点がｊ（以下、「終点ｊ」と表記する）の場合、すなわち、σ［ｉ，ｊ］を求める場合、復元部２２Ｒは、最短経路行列Ｓから、Ｓ［ｉ，ｊ］の値ｋ１を取得する。まず、Ｓ［ｉ，ｊ］の値が中間点番号である場合について説明する。σ［ｉ，ｊ］は、σ［ｉ，ｋ１］とσ［ｋ１，ｊ］との和（２つの最短経路を頂点ｋ１で結合したもの）として求めることができる。復元部２２Ｒは、σ［ｉ，ｋ１］についても、その中間点として、Ｓ［ｉ，ｋ１］の値ｋ２を取得し、σ［ｉ，ｋ２］とσ［ｋ２，ｋ１］との和として求める。また、σ［ｋ１，ｊ］についても同様に、Ｓ［ｋ１，ｊ］の値ｋ３を取得し、σ［ｋ１，ｋ３］とσ［ｋ３，ｊ］との和として求める。復元部２２Ｒは、中間点で分割された最短経路が一つの経路として繋がるまで、上記の処理を再帰的に繰り返すことにより、全体の最短経路を求める。
【００４５】
また、復元部２２Ｒは、Ｓ［ｉ，ｊ］から得られる値が中間辺の中間辺番号ｘの場合、中間経路表Ｐ２を参照して、Ｐ２［ｘ］＝（ｋ１，ｋ２）から、その中間辺の両端の頂点の頂点番号ｋ１、ｋ２を特定する。そして、復元部２２Ｒは、σ［ｉ，ｊ］として、上記と同様に、σ［ｉ，ｋ１］とσ［ｋ２，ｊ］とを、辺（ｋ１，ｋ２）で結合することにより復元する。
【００４６】
なお、長さ２以上の最短経路σ［ｉ，ｊ］において、中間点ｋが始点ｉ又は終点ｊに一致すると、最短経路を復元できなくなる。例えば、ｋ＝ｉの場合、σ［ｉ，ｊ］は、σ［ｉ，ｉ］とσ［ｉ，ｊ］との和ということになり、当初と同じσ［ｉ，ｊ］が出てきてしまい、再帰処理が進まないためである。ｋ＝ｊの場合も同様である。したがって、σ［ｉ，ｊ］が長さ２以上の最短経路の場合、始点ｉ、及び終点ｊを中間点とすることはできない。また、σ［ｉ，ｊ］が長さ１の最短経路の場合、すなわち、始点ｉと終点ｊとが隣接している場合も上記と同様に、中間点ｋが始点ｉに一致すると、最短経路を求めることができなくなる。ｋ＝ｊの場合は、親の頂点番号を用いる場合と同様であるため、問題ない。したがって、σ［ｉ，ｊ］が長さ１の最短経路の場合、始点ｉを中間点とすることはできない。
【００４７】
次に、参考例に係る情報処理装置１００Ｒの作用について説明する。まず、情報処理装置１００ＲにグラフＧ（Ｇ＝（Ｖ，Ｅ））が入力され、最短経路行列の生成が指示されると、情報処理装置１００Ｒの最短経路行列生成部１０Ｒにおいて、図６に示す最短経路行列生成処理が実行される。そして、最短経路行列が生成されて行列ＤＢ３０Ｒに格納された状態で、最短経路σ［ｉ，ｊ］の探索要求を受け付けると、情報処理装置１００Ｒの最短経路復元部２０Ｒにおいて、図７に示す最短経路復元処理が実行される。以下、参考例における最短経路行列生成処理及び最短経路復元処理の各々について詳述する。
【００４８】
まず、図６に示す最短経路行列生成処理のステップＳ１で、付与部１２Ｒが、入力されたグラフＧに含まれる各頂点（１，・・・，ｎ）間の最短経路を求める。そして、最短経路上の中間辺の各々に中間辺番号（ｎ＋１，ｎ＋２，・・・）を付与する。付与部１２Ｒは、中間辺（ｋ１，ｋ２）と、その中間辺に付与した中間辺番号（ｘ）とを対応付けて格納した中間経路表（Ｐ１［（ｋ１，ｋ２）］＝ｘ、Ｐ２［ｘ］＝（ｋ１，ｋ２））を生成する。
【００４９】
次に、ステップＳ２で、生成部１４Ｒが、グラフに含まれる全頂点から全頂点への最短経路を表す行列の各要素の値を、以下の手順で求める。まず、生成部１４Ｒは、σ［ｉ，ｊ］の中間点の頂点番号を、付与部１２Ｒが求めた最短経路の情報から取得する。そして、生成部１４Ｒは、取得した中間点の頂点番号から、最短経路行列の要素の値として用いる頂点番号又は中間辺を選択する。そして、中間辺を選択した場合は付与部１２Ｒが生成した中間経路表Ｐ１から中間辺番号を取得し、選択した頂点番号又は中間辺番号をＳ［ｉ，ｊ］の要素の値として格納する。
【００５０】
次に、ステップＳ３で、生成部１４Ｒが、生成した最短経路行列Ｓを圧縮して、付与部１２Ｒが生成した中間経路表Ｐ２と共に、行列ＤＢ３０Ｒに格納して、所定の記憶領域に記憶する。そして、最短経路行列生成処理は終了する。
【００５１】
次に、図７に示す最短経路復元処理について説明する。
【００５２】
ステップＳ６で、復元部２２Ｒが、受け付けた最短経路σ［ｉ，ｊ］の問い合わせについて、行列ＤＢ３０Ｒに格納された最短経路行列Ｓから、Ｓ［ｉ，ｊ］の値ｋを取得する。ｋが中間点の頂点番号の場合、復元部２２Ｒは、σ［ｉ，ｋ］とσ［ｋ，ｊ］との和として、σ［ｉ，ｊ］を求める。ｋが中間辺の中間辺番号の場合、復元部２２Ｒは、中間経路表Ｐ２からｋに対応する中間辺（ｋ１，ｋ２）を特定する。そして、復元部２２Ｒは、σ［ｉ，ｋ１］とσ［ｋ２，ｊ］とを、中間辺（ｋ１，ｋ２）で結合することにより、σ［ｉ，ｊ］を求める。復元部２２Ｒは、σ［ｉ，ｋ］、σ［ｋ，ｊ］、σ［ｉ，ｋ１］、σ［ｋ２，ｊ］等についても、中間点又は中間辺で分割された最短経路が一つの経路として繋がるまで、ステップＳ６及びＳ７の処理を再帰的に繰り返す。これにより、復元部２２Ｒは、全体の最短経路σ［ｉ，ｊ］を復元し、復元した最短経路σ［ｉ，ｊ］を出力して、最短経路復元処理を終了する。なお、最短経路行列や中間経路表Ｐ２にアクセスする際には伸長処理を行う。
【００５３】
＜実施形態＞
以下、図面を参照して開示の技術に係る実施形態の一例を詳細に説明する。なお、本実施形態において、参考例と共通する内容については、詳細な説明を省略する。
【００５４】
上述したように、本実施形態では、中間経路として、長さ２以上の経路を対象とする。この理由について、上記の参考例を参照しながら説明する。
【００５５】
参考例では、最短経路行列の要素の値として、最短経路上の中間点の頂点番号、又は中間辺の中間辺番号を用いる場合について説明した。この場合、最短経路の復元時に、最短経路行列（の要素）及び中間経路表へのアクセス回数が多くなる。最短経路行列及び中間経路表へのアクセスが多くなると、最短経路の復元処理に時間を要してしまう。
【００５６】
例えば、図２のグラフにおける最短経路σ［８，１］＝［８，７，５，３，１］の例で説明する。最短経路行列の要素の値として、親の頂点番号のみを用いる場合は、Ｓ［８，１］に頂点８の親である頂点７の頂点番号「７」が格納されているため、次に、Ｓ［７，１］にアクセスする。Ｓ［７，１］には、「５」が格納されているため、次に、Ｓ［５，１］にアクセスし、Ｓ［５，１］には、「３」が格納されているため、次に、Ｓ［３，１］にアクセスする。Ｓ［３，１］には終点である「１」が格納されているため、最短経路σ［８，１］は、この時点で［８，７，５，３，１］であることがわかり、Ｓ［１，１］にアクセスする必要はない。すなわち、最短経路行列へのアクセス回数はＳ［８，１］、Ｓ［７，１］、Ｓ［５，１］、及びＳ［３，１］の４回である。最短経路行列の要素の値として親の頂点番号のみを用いる場合は、一般に、長さＬの最短経路を求めるために必要な最短経路行列へのアクセス回数は、Ｌ回である。
【００５７】
最短経路行列の要素の値として中間点の頂点番号を用いる場合は、最短経路行列へのアクセス回数が、中間点を入れる毎に１回増えてしまう。例えば、Ｓ［８，１］＝５であったとする。この場合、σ［８，１］＝σ［８，５］＋σ［５，１］と計算できる。σ［８，５］及びσ［５，１］については、親を順次辿る方法で求めるとする。その場合、σ［８，５］及びσ［５，１］のそれぞれについて２回、最短経路行列へのアクセスが必要になる。すなわち、最短経路行列へのアクセスが全体で５回必要で、上記の親の頂点番号のみを用いた場合に比べ、１回増えることになる。さらに、σ［８，５］及びσ［５，１］についても中間点を使った場合は、最短経路行列へのアクセスがそれぞれ１回増えるため、全体で３回増えることになる。このように、最短経路行列の要素の値として中間点を用いる場合は、中間点１個に対し、最短経路行列へのアクセス回数が１回増えることになる。
【００５８】
次に、最短経路行列の要素の値として中間辺の中間辺番号を用いる場合を考える。Ｓ［８，１］＝９で、「９」は、中間辺（５，３）の中間辺番号であるとする。したがって、σ［８，１］＝σ［８，５］＋［５，３］＋σ［３，１］と計算できる。ここまでで、最短経路行列へ１回、中間経路表へ１回アクセスを要している。σ［８，５］及びσ［３，１］は、親を順次辿る方法で求める場合、σ［８，５］について２回、σ［３，１］について１回の最短経路行列へのアクセスが必要になる。したがって、全体で、最短経路行列へのアクセスが４回、中間経路表へのアクセスが１回必要になる。すなわち、上記の親の頂点番号のみを用いた場合に比べ、中間経路表へのアクセスが１回分増える。
【００５９】
一方、中間経路として、長さが２以上の経路を考える。Ｓ［８，１］＝１０で、「１０」は、長さが２以上の［７，５，３］という中間経路を表しているものとする。したがって、σ［８，１］＝σ［８，７］＋［７，５，３］＋σ［３，１］と計算できる。ここまでで、最短経路行列へ１回、中間経路表へ１回アクセスを要している。σ［８，７］及びσ［３，１］は、親を順次辿る方法で求める場合、σ［８，７］に１回、σ［３，１］に１回の最短経路行列へのアクセスが必要になる。したがって、全体で、最短経路行列へのアクセスが３回、中間経路表へのアクセスが１回必要になる。すなわち、上記の親の頂点番号のみを用いた場合に比べ、最短経路行列へのアクセスが１回減ったものの、中間経路表へのアクセスが１回増えたことになる。
【００６０】
最短経路行列へのアクセスと中間経路表へのアクセスとは、処理負荷が同じとは限らない。圧縮率の違いやデータの並びにより入出力回数が異なったり、ＣＰＵの処理負荷が異なったりする可能性があるためである。最短経路行列へのアクセスの方が、中間経路表へのアクセスより処理負荷が重い場合、中間経路長が２以上であれば、最短経路行列の要素の値として中間経路を用いる方が、親の頂点番号のみを用いる場合よりも高速に最短経路行列を復元できることになる。
【００６１】
一方、最短経路行列のアクセスの方が、処理負荷が軽い場合は、中間経路長が２以上のある整数以上であれば、親の頂点番号のみを用いる場合よりも高速に最短経路行列を復元可能になる値があると考えられる。そこで、本実施形態では、この値を「最小中間経路長（Ｌｍｉｎ）」とし、中間経路長がＬｍｉｎ以上の中間経路の識別情報（以下、「中間経路番号」という）のみを、最短経路行列の要素の値として用いる場合について説明する。なお、本実施形態では、Ｌｍｉｎ＝２として説明する。
【００６２】
また、最短経路行列に用いる中間経路が長いほど、最短経路の復元時の最短経路行列へのアクセス回数は減る。しかし、逆に中間経路を長くすれば、アクセス回数が減るとは限らない。その長い中間経路を含む最短経路はそう多くないはずだからである。このように中間経路長とアクセス回数との関係は一概には言えないが、中間経路表のサイズとアクセス回数との間にはトレードオフの関係があることが予想される。すなわち、中間経路表のサイズが大きくなればアクセス回数が減り、逆に中間経路表のサイズが小さくなればアクセス回数が増える傾向があると予想される。極端な例では、最短経路行列へのアクセス回数を最小化する場合には、全ての最短経路を中間経路表で管理すれば、最短経路行列へのアクセス回数は１回で済む。しかし、この場合、中間経路表のサイズは膨大なものになる。一方、中間経路表のサイズを最小化する場合には、中間経路を中間経路表に持たせなければよい。しかし、この場合、親の頂点番号のみを用いる場合と同じ回数の最短経路行列へのアクセス回数が必要になる。
【００６３】
したがって、中間経路表のサイズをできるだけ小さく保ちながら、最短経路行列へのアクセス回数をできるだけ削減できるように調整できることが望ましい。本実施形態では、このような調整も可能とする場合について説明する。
【００６４】
まず、本実施形態の概要を以下に示す。各項目の詳細については後述する。
（１）グラフをクラスタリングすると共に、切断点を求める。
（２）頂点クラスタ対応表、及び中間経路表を生成する。
（３）長さが最小中間経路長（Ｌｍｉｎ）以上の中間経路の中間経路番号を用いて最短経路行列を生成する。
（４）最短経路行列及び中間経路表Ｐ２を圧縮する。
【００６５】
上述のように、中間経路の長さは、中間経路表のサイズをできるだけ小さく保ちながら、最短経路行列へのアクセス回数をできるだけ削減できるように調整する必要がある。上記（１）に示すように、グラフをクラスタリングするのはこのためである。クラスタリングの結果、グラフは、切断辺で連結された複数のクラスタに分割される。なお、切断辺とは、辺の一端の頂点と他端の頂点とが、異なるクラスタに属する辺である。また、切断辺の両端の頂点を切断点という。そして、各クラスタの切断点を始点及び終点とし、そのクラスタ内に含まれる頂点だけからなる最小中間経路長Ｌｍｉｎ以上の最短経路を、中間経路として用いる。
【００６６】
図８に示すように、本実施形態に係る情報処理装置１００は、付与部１２及び生成部１４を含む最短経路行列生成部１０と、復元部２２を含む最短経路復元部２０とを含む。最短経路行列生成部１０は、開示の技術の最短経路行列生成装置の一例であり、付与部１２は、開示の技術の付与部の一例であり、生成部１４は、開示の技術の生成部の一例である。
【００６７】
付与部１２は、入力されたグラフを、指定された数の部分グラフに分割（クラスタリング）する。クラスタリングの手法としては、従来既知の手法を用いることができる。そして、付与部１２は、各部分グラフについて、その部分グラフに含まれる頂点を用いて表され、かつ切断点を始点及び終点とする経路を中間経路とし、その中間経路に中間経路番号を付与する。
【００６８】
具体的には、付与部１２は、全体のグラフをＧ＝（Ｖ，Ｅ）とし、１≦ｉ≦ｐとして、以下に示すように、グラフＧを、Ｖｉと、両端がＶｉに含まれる頂点からなる辺の集合Ｅｉとからなる部分グラフＧｉ＝（Ｖｉ，Ｅｉ）の列Ｇ１，Ｇ２，・・・，Ｇｐに分割する。
Ｇｉ＝（Ｖｉ，Ｅｉ）
Ｅｉ＝｛（ｖ１，ｖ２）∈Ｅ｜ｖ１，ｖ２∈Ｖｉ｝
【００６９】
このように、１つのグラフを複数のグラフに分割することは、上述のように、「クラスタリング」と呼ばれ、各連結部分グラフＧｉ（ｉ＝１，２，・・・，ｐ））は「クラスタ」と呼ばれる。また、以下では、ｐを「クラスタ数」という。このクラスタリングにより、グラフＧをｐ個の互いに重複がない連結部分グラフに分割でき、かつ切断点が求められたことになる。各部分グラフＧｉは連結しているものとする。
【００７０】
なお、無向グラフの部分グラフ内の任意の２頂点について、一方から他方への経路がある場合、その部分グラフは連結であるといい、連結している部分グラフを連結部分グラフと呼ぶ。
【００７１】
グラフを分割する際には、上述のように、中間経路表のサイズをできるだけ小さく保ちながら、最短経路行列へのアクセス回数をできるだけ削減できるように調整することを考慮して、次の２つの要求がなるべく満たされるような制約条件を設定する。
１）各Ｖｉに含まれる頂点の数は均等
２）切断辺の数が少ない
【００７２】
なお、辺ｅ＝（ｖ１，ｖ２）が２つのグラフＧ１＝（Ｖ１，Ｅ１）とＧ２＝（Ｖ２，Ｅ２）と  に跨っている、すなわち、ｖ１∈Ｖ１、ｖ２∈Ｖ２である場合、頂点ｖ１及びｖ２が「切断点」であり、辺ｅが「切断辺」である。すなわち、切断辺の数が少ないとは、ｐ個の部分グラフＧ１，Ｇ２，・・・，Ｇｐに跨る辺、すなわち、どのＧｉにも含まれない辺の数が少ないことを意味する。
【００７３】
また、付与部１２は、前述のように、各クラスタＧｉ内の切断点を始点及び終点とし、Ｇｉ内に含まれる頂点のみからなる最小中間経路長Ｌｍｉｎ以上の最短経路を、中間経路として用いる。
【００７４】
ｐの値によってクラスタが決まり、中間経路も決まるため、中間経路を管理する中間経路表の大きさが決まる。ｐの値は、グラフ全体の大きさに基づいて適切な値に設定しておくことができる。ただし、適切な値に設定するため、以下に述べるような注意が必要である。例えば、ｐを大きくしてｎに近づければ、中間経路の平均長は小さくなるため、最短経路行列へのアクセス回数は増えるように思われるが、中間経路を使える最短経路が増え、逆にアクセス回数は減る可能性もある。その場合は、前述のように、中間経路表のサイズは大きくなると予想される。逆に、ｐを小さくすれば、中間経路の平均長は大きくなるため、最短経路行列へのアクセス回数は減るようにも思われるが、中間経路を使える最短経路は少なくなり、逆にアクセス回数は増える可能性もある。その場合は、中間経路表のサイズは小さくなると予想される。このように、トレードオフの関係にあると予想される最短経路行列へのアクセス回数と中間経路表のサイズは、ｐを変動させることで変わる。上述のようにその動きがｐと平均中間経路長の間の関係のようには予測できない面はあるものの、少なくともｐの値を１からｎまでの間の適当な範囲で変動させることで、ユーザに最適と思われるバランスに調整することが可能である。
【００７５】
また、付与部１２は、各頂点がいずれのクラスタに属するかを示す頂点クラスタ対応表を生成する。例えば、付与部１２は、頂点番号ｉをキーとし、頂点ｉが属するクラスタＧｋの番号ｋを値とするインデクス付表で、頂点クラスタ対応表Ｃを生成する。本実施形態では、インデクス付表Ｔにおいて、キーｘに対する値をＴ［ｘ］と表す。したがって、頂点クラスタ対応表Ｃの場合、キーｉに対する頂点クラスタ対応表Ｃの値をＣ［ｉ］で表す。すなわち、Ｃ［ｉ］＝ｋである。なお、インデクス付表とは、例えば、主記憶上のハッシュ表や二分木、又は二次記憶上のＢ−ｔｒｅｅやハッシュ表のように、キーからインデクスを使って値に直接アクセスできる表をいう。
【００７６】
また、付与部１２は、最短経路σ［ｉ，ｊ］上に、［ｋ１，ｋ２，・・・，ｋＬ＋１］（２≦Ｌ）という中間経路、すなわち長さＬのσ［ｋ１，ｋＬ＋１］という中間経路があれば、その中間経路に中間経路番号を付与して、中間経路表で管理する。［ｋ１，ｋ２，・・・，ｋＬ＋１］という中間経路の情報を中間経路表で管理することで、参考例における中間辺の辺番号と同様に、最短経路行列の要素の値として用いることができる。また、この長さＬの中間経路の中間経路番号を最短経路行列の要素の値とすることで、最短経路行列へのアクセス回数をＬ−１回減らすことが可能となる。
【００７７】
付与部１２は、中間経路表として、最短経路行列で用いる中間経路を管理する中間経路表Ｐ１、及び中間経路表Ｐ２を生成する。中間経路表Ｐ１は、最短経路行列の生成時に、各中間経路に付与された中間経路番号を参照する際に使用される。中間経路表Ｐ２は、最短経路の復元時に、最短経路行列で用いられている中間経路番号が示す中間経路を特定する際に使用される。例えば、付与部１２は、中間経路表Ｐ１及びＰ２の各々をインデクス付表で生成することができる。
【００７８】
具体的には、付与部１２は、中間経路の始点をｉ、終点をｊとすると、中間経路表Ｐ１のキーをｉとｊとのタプル（ｉ，ｊ）とし、（ｉ，ｊ）のｉを「ｓｔａｒｔ」、ｊを「ｅｎｄ」と定義する。これにより、中間経路表Ｐ１において、ｋｅｙ＝（ｉ，ｊ）とした場合、ｉの値はｋｅｙ．ｓｔａｒｔ、ｊの値はｋｅｙ．ｅｎｄで参照できるものとする。付与部１２は、始点ｉ及び終点ｊの中間経路に中間経路番号を付与し、その中間経路番号をＰ１［（ｉ，ｊ）］の値として格納することで、中間経路表Ｐ１を生成する。
【００７９】
また、中間経路を［ｉ１，ｉ２，・・・，ｉｈ］とし、この中間経路の中間経路番号をｕｎｏとすると、付与部１２は、中間経路表Ｐ２のキーをｕｎｏとし、Ｐ２［ｕｎｏ］の値として［ｉ１，ｉ２，・・・，ｉｈ］を格納することで、中間経路表Ｐ２を生成する。［ｉ１，ｉ２，・・・，ｉｈ］は、頂点ｉ１、ｉ２、・・・、及びｉｈからなるリストである。
【００８０】
より具体的には、付与部１２は、各クラスタＧｋ（ｋ＝１，２，・・・，ｐ）について、Ｇｋ内の切断点間の最短経路を、既存の最短経路を求めるアルゴリズムを用いて求める。例えば、以下に述べる幅優先探索アルゴリズムを、全点から全点への最短経路を求めるのではなく、切断点を出発点として、全ての切断点に到達した時点で終了するようなアルゴリズムにすることで求めることが可能である。
【００８１】
例えば、付与部１２は、全頂点の数をｎとした場合、求めた各中間経路にｎ＋１から順に中間経路番号を付与し、各中間経路と対応付けて、中間経路表Ｐ１及びＰ２に登録する。なお、中間経路表Ｐ１及びＰ２のサイズを小さくするため、中間経路表Ｐ１のキー（ｉ，ｊ）は、ｉ＜ｊを満たすものとする。キー（ｊ，ｉ）に対応する中間経路であって、キー（ｉ，ｊ）に対応する中間経路の逆順の中間経路は、中間経路表Ｐ１に格納しない。始点をｊ、終点をｉとする中間経路については、Ｐ１［（ｉ，ｊ）］を利用する。同様に、中間経路表Ｐ２についても、中間経路番号ｕｎｏの中間経路を［ｉ１，ｉ２，・・・，ｉｈ］とした場合、ｉ１＜ｉｈを満たす中間経路のみを格納する。［ｉｈ，ｉｈ−１，・・・，ｉ１］については、Ｐ２［ｕｎｏ］＝［ｉ１，ｉ２，・・・，ｉｈ］の順序を逆転させて利用する。なお、逆転したものであることを示すために、後述のように中間経路番号ｕｎｏを反転した値を最短経路行列の値として用いる。
【００８２】
生成部１４は、中間経路表Ｐ１で管理されている中間経路を用いて、参考例における生成部１４Ｒと同様に、最短経路行列Ｓを生成する。
【００８３】
ここで、本実施形態における最短経路行列の生成方式は、既存の全頂点から全頂点への最短経路を求めるアルゴリズム、具体的には、幅優先探索アルゴリズムに修正を加えたものである。そのため、本実施形態における最短経路行列の生成方式の理解を容易にするために、まず、幅優先探索アルゴリズムによる最短経路行列の生成について説明する。この方式では、最短経路行列の要素には、親の頂点番号が格納される。
【００８４】
まず、頂点ｊ毎に、その頂点に隣接する頂点の頂点番号のリスト（以下、「隣接頂点リスト」という）Ａ［ｊ］が与えられているものとする。例えば、頂点ｊに隣接する頂点がｋ１及びｋ２であれば、Ａ［ｊ］＝［ｋ１，ｋ２］である。そして、図９に示す幅優先探索アルゴリズムで詳述するように、頂点ｊからの距離が０、１、２、・・・である頂点を同心円状に順に求めていく。この同心円的な振る舞いの様子を図１０に示す。図１０は、頂点１、頂点２、頂点３、頂点４、及び頂点５を含むグラフで、頂点１を根とした場合の例である。なお、図１０に示すグラフにおいて、実線で示す辺は、幅優先探索アルゴリズムで最短経路として辿った辺であり、破線で示す辺は最短経路として辿らなかった辺を示している。
【００８５】
具体的には、図９に示す幅優先探索アルゴリズムのＳ１００１で、ｎ行ｎ列の空の最短経路行列Ｓを用意し、最短経路行列Ｓにおける処理対象の列、すなわち、求める最短経路の終点を特定するための変数ｊに１を設定する。
【００８６】
次に、ステップＳ１００２で、ｊがグラフに含まれる頂点の個数ｎ以下か否かを判定する。ｊ≦ｎの場合には、ステップＳ１００３で、頂点ｊからの距離を示す変数ｄに０を設定し、頂点ｊからの距離がｄの同心円上に存在する頂点のリストＲ［ｄ］にｊを格納する。また、求める最短経路の始点を特定するための変数ｉに１を設定する。
【００８７】
次に、ステップＳ１００４で、ｉがｎ以下か否かを判定する。ｉ≦ｎの場合には、ステップＳ１００５で、Ｓ［ｉ，ｊ］に初期値として「Ｉ」を格納する。最短経路行列Ｓの要素Ｓ［ｉ，ｊ］には、頂点ｉから頂点ｊへの最短経路における頂点ｉの親の頂点番号を格納していくが、初期値としては、最短経路の探索において、頂点ｉが未だ辿られていないことを示す値Ｉ（Initialの意）を格納しておくものである。
【００８８】
次に、ステップＳ１００６で、ｉを１インクリメントしてステップＳ１００４に戻る。ステップＳ１００４で、ｉ＞ｎと判定されると、ステップＳ１００７で、Ｓ［ｊ，ｊ］に最短経路の終点を示す値（ここでは、「Ｅ」）を設定する。
【００８９】
次に、ステップＳ１００８で、Ｒ［ｄ］が空か否かを判定し、空ではない場合には、ステップＳ１００９へ移行する。ステップＳ１００９では、ｄを１インクリメントし、Ｒ［ｄ］を空のリスト（［  ］）で初期化する。
【００９０】
次に、ステップＳ１０１０で、Ｒ［ｄ−１］に本ステップ以降の処理が未処理の頂点ｉが存在するか否かを判定する。未処理の頂点ｉが存在する場合には、ステップＳ１０１１へ移行し、未処理の頂点ｉが存在しない場合には、ステップＳ１００８に戻る。
【００９１】
ステップＳ１０１１では、Ｒ［ｄ−１］から未処理の頂点ｉを１つ選択し、その頂点ｉの隣接頂点リストＡ［ｉ］に本ステップ以降の処理が未処理の頂点ｋが存在するか否かを判定する。未処理の頂点ｋが存在する場合には、処理はステップＳ１０１２へ移行し、未処理の頂点ｋが存在しない場合には、処理はステップＳ１０１０に戻る。
【００９２】
ステップＳ１０１２では、Ａ［ｉ］から未処理の頂点ｋを１つ選択し、Ｓ［ｋ，ｊ］がＩ、すなわち初期値か否かを判定する。Ｓ［ｋ，ｊ］＝Ｉの場合には、ステップＳ１０１３へ移行し、Ｓ［ｋ，ｊ］≠Ｉの場合には、ステップＳ１０１１に戻る。
【００９３】
ステップＳ１０１３では、最短経路行列ＳのＳ［ｋ，ｊ］に、上記ステップＳ１０１１で選択した頂点の頂点番号ｉを格納する。また、Ｒ［ｄ］に、上記ステップＳ１０１２で選択した頂点の頂点番号ｋを追加する。すなわち、頂点ｊから距離ｄの位置にある頂点であることが判明した頂点の頂点番号を、Ｒ［ｄ］（ｄ＝０，１，２，・・・）に格納していく。そして、ステップＳ１０１１に戻る。
【００９４】
上記ステップＳ１００８で、Ｒ［ｄ］が空であると判定されると、ステップＳ１０１４で、ｊを１インクリメントして、ステップＳ１００２に戻る。そして、ｊ＞ｎと判定されると、幅優先探索アルゴリズムは終了する。
【００９５】
上記の処理を、図１０に示すグラフを例に、より具体的に説明する。
【００９６】
ｊ＝１の場合において、ステップＳ１００２〜Ｓ１００７の処理までが終了すると、最短経路行列Ｓは、図１１のＳ−１に示すように、ｊ＝１についての初期状態となる。このとき、Ｒ［ｄ＝０］＝［１］であるので、ステップＳ１００９に進み、Ｒ［ｄ＝０＋１］＝［  ］となる。Ｒ［ｄ−１＝０］には「１」が格納されており、Ａ［ｉ＝１］＝［ｋ＝２，３］である。まず、ステップＳ１０１２で、ｋ＝２が選択されたとすると、ステップＳ１０１３で、Ｓ［ｋ＝２，ｊ＝１］＝１が格納され、Ｒ［ｄ＝１］＝［２］となる。そして、ステップＳ１０１１に戻って、ｋ＝３が選択され、ステップＳ１０１３で、Ｓ［ｋ＝３，ｊ＝１］＝１が格納され、Ｒ［ｄ＝１］＝［２，３］となる。
【００９７】
この段階で、Ａ［ｉ］に未処理の頂点ｋが存在しなくなり、また、Ｒ［ｄ−１］に未処理の頂点ｉが存在しなくなるため、ステップＳ１００８に戻る。このとき、Ｒ［ｄ＝１］＝［２，３］であるので、ステップＳ１００９に進み、Ｒ［ｄ＝１＋１］＝［  ］となる。Ｒ［ｄ−１＝１］には２及び３が格納されている。まず、ステップＳ１０１１で、ｉ＝２が選択されたとすると、Ａ［ｉ＝２］＝［ｋ＝１，３，４，５］である。まず、ステップＳ１０１２で、ｋ＝１が選択されたとすると、Ｓ［ｋ＝１，ｊ＝１］＝Ｅ≠Ｉであるため、ステップＳ１０１１に戻る。次に、ｋ＝３が選択されたとすると、Ｓ［ｋ＝３，ｊ＝１］＝１≠Ｉであるため、ステップＳ１０１１に戻る。次に、ｋ＝４が選択されたとすると、Ｓ［ｋ＝４、ｊ＝１］＝Ｉであるため、ステップＳ１０１３で、Ｓ［ｋ＝４，ｊ＝１］＝２が格納され、Ｒ［ｄ＝２］＝［４］となる。そして、ステップＳ１０１１に戻って、ｋ＝５が選択され、ステップＳ１０１３で、同様にＳ［ｋ＝５，ｊ＝１］＝２が格納され、Ｒ［ｄ＝２］＝［４，５］となる。
【００９８】
次に、ステップＳ１０１０に戻って、Ｒ［ｄ−１］に未処理の頂点３が存在するため、ステップＳ１０１１で、ｉ＝３が選択される。Ａ［ｉ＝３］＝［ｋ＝１，２］であり、ステップＳ１０１２で、ｋ＝１，２のいずれが選択された場合も、Ｓ［ｋ＝１ｏｒ２，ｊ＝１］≠Ｉであるため、ステップＳ１０１０を経由してステップＳ１００８に戻る。
【００９９】
このとき、Ｒ［ｄ＝２］＝［４，５］であるので、ステップＳ１００９に進み、Ｒ［ｄ＝２＋１］＝［  ］となる。Ｒ［ｄ−１＝２］には４及び５が格納されており、まず、ステップＳ１０１１で、ｉ＝４が選択されたとすると、Ａ［ｉ＝４］＝［ｋ＝２，５］である。ステップＳ１０１２で、ｋ＝２，５のいずれが選択された場合も、Ｓ［ｋ＝２ｏｒ５，ｊ＝１］≠Ｉであるため、ステップＳ１０１０に戻る。ステップＳ１０１１で、ｉ＝５が選択され、Ａ［ｉ＝５］＝［ｋ＝２，４］である。ステップＳ１０１２で、ｋ＝２，４のいずれが選択された場合も、Ｓ［ｋ＝２ｏｒ４，ｊ＝１］≠Ｉであるため、ステップＳ１０１０を経由してステップＳ１００８に戻る。
【０１００】
このとき、Ｒ［ｄ＝３］は空であるため、ｊ＝１についての処理は終了する。この段階での最短経路行列Ｓは、図１１のＳ−２に示す状態となる。ｊ＝２，３，４，５についても同様に処理し、ｊ＝５についての処理終了時には、最短経路行列Ｓは、図１１のＳ−３に示す状態となる。
【０１０１】
上記の幅探索アルゴリズムを踏まえて、本実施形態における最短経路行列の生成について説明する。本実施形態における最短経路行列の生成では、上記の幅優先探索アルゴリズムに、次のように変更を加える。
【０１０２】
幅優先探索アルゴリズムにおいて、頂点ｊから距離ｄの位置にある頂点の頂点番号ｉが格納されるリストＲ［ｄ］について、Ｒ［ｄ］に格納される要素として、頂点番号ｉだけでなく、頂点ｉの状態に関する情報ｍを格納する。すなわち、本実施形態では、Ｒ［ｄ］は、タプル（ｉ，ｍ）のリストである。ここでいう頂点ｉの状態に関する情報ｍとは、頂点ｉから頂点ｊへの最短経路上の中間経路を見つける過程における頂点ｉの状態を示す情報である。
【０１０３】
本実施形態では、ｍをｍ＝（ｓｔａｔｅ，ｕｎｏ，ｌｅｎ）という３つの要素からなるタプルとして定義する。ｓｔａｔｅ、ｕｎｏ、及びｌｅｎの各要素は、それぞれｍ．ｓｔａｔｅ、ｍ．ｕｎｏ、及びｍ．ｌｅｎで参照可能であるとする。ｍ．ｓｔａｔｅは、頂点ｉの状態を表す（詳細は後述）。ｍ．ｕｎｏは、中間経路の終点となる切断点の頂点番号、又は中間経路の中間経路番号である。ｍ．ｌｅｎは、中間経路の長さを表す。ｍ．ｓｔａｔｅは、辿ってきた経路の現時点での状態を番号で表すものである。ｍ．ｓｔａｔｅに用いられる番号と、その意味とを以下に示す。
【０１０４】
ＮＰ：頂点ｉが最短経路探索の出発点と同じクラスタ内にいて、未だ中間経路に遭遇していない。
ＩＰ：頂点ｉが最短経路探索の出発点と別のクラスタ内にいて、未完結の中間経路又は中間経路になる可能性のある経路に遭遇。
ＣＰ：長さが最小中間経路長Ｌｍｉｎ以上の完結した中間経路に遭遇。
【０１０５】
中間経路が完結とは、最短経路の探索が、経路が長さがＬｍｉｎ以上の中間経路を経由して、その中間経路とは別のクラスタに移り、その中間経路がさらに延長されないことが確定したことを意味する。逆に、未完結とは、経路上で中間経路には遭遇しているが、その中間経路があるクラスタから他のクラスタに移っていないため、その中間経路が完結していなくて、さらに伸びる可能性があることを意味する。
【０１０６】
ｍ．ｓｔａｔｅの値としては、例えば、ＮＰ、ＩＰ、及びＣＰの各々に、ＮＰ＜ＩＰ＜ＣＰとなる番号、例えば、０、１、２を割り当てる。なお、ＮＰはNo Path、ＩＰはIncomplete Path、ＣＰはComplete Pathの略である。以下では、説明を分かり易くするため、０、１、２等の番号ではなく、ＮＰ、ＩＰ、及びＣＰの記号を用いて説明する。
【０１０７】
ｍの各要素は、ｍ．ｓｔａｔｅの値に応じて、以下に示す値をとる。
ＮＰの場合  （ＮＰ，Ｎｏｎｅ，Ｎｏｎｅ）
ＩＰの場合  （ＩＰ，ｕ，ｌｅｎ）
ＣＰの場合  （ＣＰ，ｕ，ｌｅｎ）
【０１０８】
Ｎｏｎｅはオブジェクトがないことを意味する定数である。ＩＰの場合、ｕは中間経路になる可能性のある経路の終点の頂点番号、ｌｅｎはその経路の頂点ｉから終点ｕまでの長さである。ＣＰの場合、ｕは完結した中間経路の中間経路番号、ｌｅｎはその中間経路の長さであり、Ｌｍｉｎ≦ｌｅｎである。
【０１０９】
生成部１４は、上記のｍを更新しながら幅優先探索により最短経路を求め、その最短経路上で経由する頂点の頂点番号、又は中間経路の中間経路番号を最短経路行列の対応する要素に格納することにより、最短経路行列Ｓを生成する。生成部１４は、生成した最短経路行列Ｓを、付与部１２が生成した中間経路表Ｐ２と共に圧縮して行列ＤＢ３０に格納する。
【０１１０】
復元部２２は、始点及び終点を指定した最短経路の問い合わせを受け付けると、行列ＤＢ３０に格納された最短経路行列Ｓ及び中間経路表Ｐ２を用いて、指定された始点及び終点に対応する頂点間の最短経路を復元する。
【０１１１】
情報処理装置１００は、例えば図１２に示すコンピュータ４０で実現することができる。コンピュータ４０は、Central Processing Unit（ＣＰＵ）４１、一時記憶領域としてのメモリ４２、及び不揮発性の記憶部４３を備える。また、コンピュータ４０は、入出力装置４４、記憶媒体４９に対するデータの読み込み及び書き込みを制御するRead/Write（Ｒ／Ｗ）部４５、及びインターネット等のネットワークに接続される通信interface（Ｉ／Ｆ）４６を備える。ＣＰＵ４１、メモリ４２、記憶部４３、入出力装置４４、Ｒ／Ｗ部４５、及び通信Ｉ／Ｆ４６は、バス４７を介して互いに接続される。
【０１１２】
記憶部４３はHard Disk Drive（ＨＤＤ）、Solid State Drive（ＳＳＤ）、フラッシュメモリ等によって実現できる。記憶媒体としての記憶部４３には、コンピュータ４０を情報処理装置１００として機能させるための最短経路行列生成プログラム５０及び最短経路復元プログラム６０が記憶される。最短経路行列生成プログラム５０は、付与プロセス５２と、生成プロセス５４とを有する。最短経路復元プログラム６０は、復元プロセス６２を有する。また、記憶部４３は、行列ＤＢ３０を構成する情報が記憶される情報記憶領域７０を有する。
【０１１３】
ＣＰＵ４１は、最短経路行列生成プログラム５０及び最短経路復元プログラム６０の各々を記憶部４３から読み出してメモリ４２に展開し、最短経路行列生成プログラム５０及び最短経路復元プログラム６０が有するプロセスを順次実行する。
【０１１４】
ＣＰＵ４１は、付与プロセス５２を実行することで、図８に示す付与部１２として動作する。また、ＣＰＵ４１は、生成プロセス５４を実行することで、図８に示す生成部１４として動作する。また、ＣＰＵ４１は、復元プロセス６２を実行することで、図８に示す復元部２２として動作する。また、ＣＰＵ４１は、情報記憶領域７０から情報を読み出して、例えば、行列ＤＢ３０の必要な情報をメモリ４２に展開すると共に、メモリ４２の必要な情報を情報記憶領域７０に書き出す。これにより、最短経路行列生成プログラム５０及び最短経路復元プログラム６０の各々を実行したコンピュータ４０が、情報処理装置１００として機能することになる。なお、プログラムを実行するＣＰＵ４１はハードウェアである。
【０１１５】
なお、最短経路行列生成プログラム５０及び最短経路復元プログラム６０により実現される機能は、例えば半導体集積回路、より詳しくはApplication Specific Integrated Circuit（ＡＳＩＣ）等で実現することも可能である。
【０１１６】
次に、本実施形態に係る情報処理装置１００の作用について説明する。まず、情報処理装置１００にグラフＧ（Ｇ＝（Ｖ，Ｅ））が入力され、最短経路行列の生成が指示されると、情報処理装置１００の最短経路行列生成部１０において、図１３に示す最短経路行列生成処理が実行される。最短経路行列生成処理は、開示の技術の最短経路行列生成方法の一例である。そして、最短経路行列が生成されて行列ＤＢ３０に格納された状態で、最短経路σ［ｉ，ｊ］の問い合わせを受け付けると、情報処理装置１００の最短経路復元部２０において、図２１に示す最短経路復元処理が実行される。以下、本実施形態における最短経路行列生成処理及び最短経路復元処理の各々について詳述する。
【０１１７】
まず、図１３に示す最短経路行列生成処理のステップＳ１０で、付与部１２が、１）各Ｖｉに含まれる頂点の数は均等、及び、２）切断辺の数が少ない、という制約下で、グラフＧをｐ個にクラスタリングする。
【０１１８】
次に、ステップＳ２０で、表生成処理が実行される。ここで、図１４を参照して、表生成処理について詳述する。
【０１１９】
ステップＳ２１で、付与部１２が、クラスタの番号を示す変数ｋに１を設定する。また、付与部１２が、初期状態の頂点クラスタ対応表Ｃとして、空のインデクス付表を作成する。
【０１２０】
次に、ステップＳ２２で、付与部１２が、ｋが、上記ステップＳ１０で分割されたクラスタ数ｐ以下か否かを判定する。ｋ≦ｐの場合には、処理はステップＳ２３へ移行する。
【０１２１】
ステップＳ２３では、付与部１２が、クラスタＧｋに本ステップ以降の処理が未処理の頂点ｉが含まれるか否かを判定する。未処理の頂点ｉが含まれる場合には、処理はステップＳ２４へ移行する。
【０１２２】
ステップＳ２４では、付与部１２が、未処理の頂点ｉを１つ選択して、頂点クラスタ対応表のＣ［ｉ］の値としてｋを格納して、処理はステップＳ２３に戻る。クラスタＧｋに未処理の頂点が存在しなくなると、処理はステップＳ２５へ移行し、付与部１２が、ｋを１インクリメントして、処理はステップＳ２２に戻る。ステップＳ２２で、ｋ＞ｐと判定されると、処理はステップＳ２６へ移行する。
【０１２３】
ステップＳ２６では、付与部１２が、中間経路番号を示す変数ｕに、頂点の個数（頂点番号の最大値）ｎを設定する。また、付与部１２が、初期状態の中間経路表Ｐ１、Ｐ２の各々として、空のインデクス付表を作成する。さらに、付与部１２が、クラスタの番号を示す変数ｋに１を設定する。
【０１２４】
次に、ステップＳ２７で、付与部１２が、ｋがクラスタ数ｐ以下か否かを判定する。ｋ≦ｐの場合は、処理はステップＳ２８へ移行する。ステップＳ２８では、付与部１２が、クラスタＧｋの切断点を始点及び終点とし、クラスタＧｋに含まれる頂点のみを通る最短経路を中間経路として求め、中間経路の集合Ｐを生成する。なお、中間経路の始点をｉ１、終点をｉｈとした場合、ｉ１＜ｉｈを満たす中間経路のみを生成する。中間経路となる最短経路の求め方としては、例えば、上述した幅優先探索アルゴリズムを用いることができる。
【０１２５】
次に、ステップＳ２９で、付与部１２が、中間経路の集合Ｐに、本ステップ以降の処理が未処理の中間経路［ｉ１，ｉ２，・・・，ｉｈ］が存在するか否かを判定する。未処理の中間経路が存在する場合には、処理はステップＳ３０へ移行する。
【０１２６】
ステップＳ３０では、付与部１２が、ｕを１インクリメントし、中間経路表Ｐ１のＰ１［（ｉ１，ｉｈ）］の値としてｕを格納し、中間経路表Ｐ２のＰ２［ｕ］の値として［ｉ１，ｉ２，・・・，ｉｈ］を格納して、処理はステップＳ２９に戻る。中間経路の集合Ｐに未処理の中間経路が存在しなくなると、処理はステップＳ３１へ移行し、付与部１２が、ｋを１インクリメントして、処理はステップＳ２７に戻る。ステップＳ２７で、ｋ＞ｐと判定されると、表生成処理は終了し、最短経路行列生成処理（図１３）に戻る。
【０１２７】
次に、最短経路行列生成処理のステップＳ４０で、行列生成処理が実行される。ここで、図１５を参照して、行列生成処理について詳述する。
【０１２８】
ステップＳ４１で、生成部１４が、ｎ行ｎ列の空の最短経路行列Ｓを用意し、最短経路行列Ｓにおける処理対象の列、すなわち、求める最短経路の終点を特定するための変数ｊに１を設定する。
【０１２９】
次に、ステップＳ４２で、生成部１４が、ｊがグラフに含まれる頂点の個数ｎ以下か否かを判定する。ｊ≦ｎの場合には、ステップＳ４３で、生成部１４が、頂点クラスタ対応表ＣからＣ［ｊ］の値を取得して、変数ｃに設定し、頂点ｊからの距離を示す変数ｄに０を設定する。また、生成部１４が、頂点ｊからの距離がｄの同心円上に存在する頂点の頂点番号ｉ、及び頂点ｉの状態を示す情報ｍのタプル（ｉ，ｍ）のリストＲ［ｄ］に（ｊ，（ＮＰ，Ｎｏｎｅ，Ｎｏｎｅ））を格納する。さらに、生成部１４が、求める最短経路の始点を特定するための変数ｉに１を設定する。
【０１３０】
次に、ステップＳ４４〜Ｓ４７で、上述の幅優先探索アルゴリズム（図９）のステップＳ１００４〜Ｓ１００７と同様に、最短経路行列Ｓの要素Ｓ［ｉ，ｊ］（ｉ＝１，２，・・・，ｎ）に初期値「Ｉ」、Ｓ［ｊ，ｊ］に終点を示す値「Ｅ」を設定する。
【０１３１】
次に、ステップＳ４８で、生成部１４が、Ｒ［ｄ］が空か否かを判定し、空ではない場合には、ステップＳ４９へ移行する。ステップＳ４９では、生成部１４が、ｄを１インクリメントし、Ｒ［ｄ］を空のリスト（［  ］）で初期化する。
【０１３２】
次に、ステップＳ５０で、生成部１４が、Ｒ［ｄ−１］に本ステップ以降の処理が未処理のタプル（ｉ，ｍ）が存在するか否かを判定する。未処理のタプル（ｉ，ｍ）が存在する場合には、処理はステップＳ５１へ移行し、未処理のタプル（ｉ，ｍ）が存在しない場合には、処理はステップＳ４８に戻る。
【０１３３】
ステップＳ５１では、生成部１４が、Ｒ［ｄ−１］から未処理のタプル（ｉ，ｍ）を１つ選択し、頂点ｉの隣接頂点リストＡ［ｉ］に本ステップ以降の処理が未処理の頂点ｋが存在するか否かを判定する。未処理の頂点ｋが存在する場合には、処理はステップＳ５２へ移行し、未処理の頂点ｋが存在しない場合には、処理はステップＳ５０に戻る。
【０１３４】
ステップＳ５２では、生成部１４が、Ａ［ｉ］から未処理の頂点ｋを１つ選択し、Ｓ［ｋ，ｊ］がＩ、すなわち初期値か否かを判定する。Ｓ［ｋ，ｊ］＝Ｉの場合には、ステップＳ６０へ移行し、Ｓ［ｋ，ｊ］≠Ｉの場合には、ステップＳ５１に戻る。
【０１３５】
ステップＳ６０では、生成部１４が、最短経路を頂点ｉから頂点ｋに辿った場合における頂点ｋとその状態を示す情報ｍ’のタプル（ｋ，ｍ’）を取得するための（ｋ，ｍ’）取得処理を実行する。ここで、図１６を参照して、（ｋ，ｍ’）取得処理について説明する。
【０１３６】
ステップＳ６１で、生成部１４が、上記ステップＳ５１で選択したタプル（ｉ，ｍ）のｍ．ｓｔａｔｅがＮＰか否かを判定する。ｍ．ｓｔａｔｅ＝ＮＰの場合には、処理はステップＳ６２へ移行し、ｍ．ｓｔａｔｅ≠ＮＰの場合には、処理はステップＳ６５へ移行する。
【０１３７】
ステップＳ６２では、生成部１４が、頂点クラスタ対応表ＣのＣ［ｋ］の値が、上記ステップＳ４３で設定したｃの値と同じか否かを判定する。すなわち、生成部１４は、頂点ｋが属するクラスタが、頂点ｊが属するクラスタと同じか否かを判定する。Ｃ［ｋ］＝ｃの場合には、生成部１４は、頂点ｋは、最短経路探索の出発点である頂点ｊと同じクラスタに存在しており、未だ中間経路表Ｐ１で管理されている中間経路に遭遇していないと判断する。そこで、処理はステップＳ６３へ移行し、生成部１４が、上記ステップＳ５１で選択したタプル（ｉ，ｍ）のｍを、ｍ’に設定し、処理はステップＳ７６へ移行する。
【０１３８】
一方、Ｃ［ｋ］≠ｃの場合には、生成部１４は、頂点ｋは、頂点ｊが属するクラスタとは別のクラスタに移ったと判断する。すなわち、頂点ｋは、別のクラスタの切断点であり、中間経路となり得る経路の終点である。そこで、処理はステップＳ６４へ移行し、生成部１４が、ｍ’に（ＩＰ，ｋ，０）を設定し、処理はステップＳ７６へ移行する。
【０１３９】
ステップＳ６５では、生成部１４が、上記ステップＳ５１で選択したタプル（ｉ，ｍ）のｍ．ｓｔａｔｅがＩＰか否かを判定する。ｍ．ｓｔａｔｅ＝ＩＰの場合には、処理はステップＳ６６へ移行し、ｍ．ｓｔａｔｅ≠ＩＰの場合には、生成部１４は、ｍ．ｓｔａｔｅはＣＰであると判断し、処理はステップＳ６３へ移行する。
【０１４０】
ステップＳ６６では、生成部１４が、頂点クラスタ対応表ＣのＣ［ｋ］の値が、Ｃ［ｍ．ｕｎｏ］の値と同じか否かを判定する。ｍ．ｕｎｏは、上記ステップＳ５１で選択されたタプル（ｉ，ｍ）のｍ．ｕｎｏの要素である。Ｃ［ｋ］＝Ｃ［ｍ．ｕｎｏ］の場合には、処理はステップＳ６７へ移行する。
【０１４１】
ステップＳ６７では、生成部１４が、頂点ｋは頂点ｉと同じクラスタ内に存在すると判断し、ｍ’を、ｍが表す頂点ｉの状態から、中間経路長を１延長させた値に変更する。すなわち、生成部１４は、ｍ’に（ＩＰ，ｍ．ｕｎｏ，ｍ．ｌｅｎ＋１）を設定し、処理はステップＳ７６へ移行する。
【０１４２】
上記ステップＳ６６で、Ｃ［ｋ］≠Ｃ［ｍ．ｕｎｏ］と判定される場合、頂点ｋは、頂点ｉとは異なるクラスタへ移ったこと、すなわち、ｍ．ｕｎｏを終点とする中間経路が頂点ｉを始点として完結したことを表す。そこで、処理はステップＳ６８へ移行し、生成部１４が、頂点ｉと頂点ｍ．ｕｎｏ間の中間経路長ｍ．ｌｅｎが最小中間経路長Ｌｍｉｎ以上か否かを判定する。Ｌｍｉｎ≦ｍ．ｌｅｎの場合には、処理はステップＳ６９へ移行する。
【０１４３】
ステップＳ６９では、生成部１４が、ｉがｍ．ｕｎｏよりも小さいか否かを判定する。ｉ＜ｍ．ｕｎｏの場合には、処理はステップＳ７０へ移行し、生成部１４が、中間経路表Ｐ１からＰ１［（ｉ，ｍ．ｕｎｏ）］の値、すなわち、始点がｉ、終点がｍ．ｕｎｏである中間経路の中間経路番号を取得し、その値を変数ｕｎｏに設定する。一方、ｉ≧ｍ．ｕｎｏの場合には、処理はステップＳ７１へ移行し、生成部１４が、中間経路表Ｐ１からＰ１［（ｍ．ｕｎｏ，ｉ）］の値を取得して、その値の符号を反転させる。すなわち、生成部１４は、始点がｍ．ｕｎｏ、終点がｉである中間経路の中間経路番号にマイナスを付与した値を、始点がｉ、終点がｍ．ｕｎｏの中間経路の中間経路番号とし、変数ｕｎｏに設定する。
【０１４４】
次に、ステップＳ７２で、生成部１４が、ｍ’を、頂点ｉで中間経路が完結したことを表す値に変更する。すなわち、生成部１４は、ｍ’に（ＣＰ，ｕｎｏ，ｍ．ｌｅｎ）を設定し、処理はステップＳ７６へ移行する。
【０１４５】
一方、上記ステップＳ６８で、Ｌｍｉｎ＞ｍ．ｌｅｎと判定された場合には、生成部１４は、完結した中間経路は、中間経路表Ｐ１で管理されている中間経路ではないため、未だ中間経路に遭遇していない状態であるとみなし、処理はステップＳ７３へ移行する。
【０１４６】
ステップＳ７３では、生成部１４が、Ｃ［ｋ］＝ｃか否かを判定する。Ｃ［ｋ］＝ｃの場合には、生成部１４は、頂点ｋは、最短経路探索の出発点である頂点ｊと同じクラスタに存在しており、未だ中間経路表Ｐ１で管理されている中間経路に遭遇していないと判断する。そこで、処理はステップＳ７４へ移行し、生成部１４が、ｍ’に（ＮＰ，Ｎｏｎｅ，Ｎｏｎｅ）を設定し、処理はステップＳ７６へ移行する。
【０１４７】
一方、Ｃ［ｋ］≠ｃの場合には、処理はステップＳ７５へ移行し、生成部１４は、上記ステップＳ６４と同様に、ｍ’に（ＩＰ，ｋ，０）を設定し、処理はステップＳ７６へ移行する。
【０１４８】
ステップＳ７６では、生成部１４が、ｍ’．ｓｔａｔｅがＣＰか否かを判定する。ｍ’．ｓｔａｔｅ＝ＣＰの場合、頂点ｋの状態は、ＩＰからＣＰへ変わったか、又は元々ＣＰであったことを表す。そこで、処理はステップＳ７７へ移行し、ステップＳ７７で、生成部１４が、Ｓ［ｋ，ｊ］の値にｍ’．ｕｎｏ、すなわち、上記ステップＳ７０又はＳ７１で取得した中間経路番号を格納する。
【０１４９】
一方、ｍ’．ｓｔａｔｅ≠ＣＰの場合には、処理はステップＳ７８へ移行し、生成部１４が、Ｓ［ｋ，ｊ］の値に、頂点ｋの親の頂点番号ｉを格納する。そして、生成部１４は、タプル（ｋ，ｍ’）を返し、処理は行列生成処理（図１５）に戻る。
【０１５０】
次に、ステップＳ８０で、生成部１４が、（ｋ，ｍ’）取得処理から返されたタプル（ｋ，ｍ’）をリストＲ［ｄ］に追加し、処理はステップＳ５１に戻る。
【０１５１】
上記ステップＳ４８で、Ｒ［ｄ］が空であると判定されると、処理はステップＳ８１へ移行し、生成部１４が、ｊを１インクリメントして、処理はステップＳ４２に戻る。そして、ステップＳ４２で、ｊ＞ｎと判定されると、行列生成終了は終了し、処理は最短行列生成処理（図１３）に戻る。
【０１５２】
次に、ステップＳ９０で、参考例における最短経路行列生成処理（図６）のステップＳ３と同様に、生成した最短経路行列Ｓ、及び付与部１２が生成した中間経路表Ｐ２を圧縮し、行列ＤＢ３０に格納して、所定の記憶領域に記憶する。そして、最短経路行列生成処理は終了する。
【０１５３】
上記の最短経路行列生成処理について、特に行列生成処理を中心に、図１７に示す単純な線状のグラフを用いて、具体的に説明する。
【０１５４】
図１７に示すグラフに含まれる頂点の個数ｎは、ｎ＝１０である。分割数（クラスタ数）ｐ＝４として、例えば、図１８に示すようにグラフがクラスタリングされたものとする。なお、図１８において、破線で示す辺が切断辺である。すなわち、頂点の集合Ｖは次のように分割される。
【０１５５】
Ｖ１＝［１，２］、  Ｖ２＝［３，４，５］、  
Ｖ３＝［６，７，８］、  Ｖ４＝［９，１０］
【０１５６】
Ｖ１、Ｖ２、Ｖ３、及びＶ４はそれぞれクラスタ（連結部分グラフ）Ｇ１、Ｇ２、Ｇ３、及びＧ４に含まれる。Ｇ１とＧ２との間の切断辺は（２，３）であり、Ｇ２とＧ３との間の切断辺は（５，６）であり、Ｇ３とＧ４との間の切断辺は（８，９）であり、切断点は２、３、５、６、８、及び９である。したがって、頂点クラスタ対応表Ｃは、次のように生成される。
【０１５７】
Ｃ［１］＝１、  Ｃ［２］＝１、  
Ｃ［３］＝２、  Ｃ［４］＝２、  Ｃ［５］＝２、
Ｃ［６］＝３、  Ｃ［７］＝３、  Ｃ［８］＝３、
Ｃ［９］＝４、  Ｃ［１０］＝４
【０１５８】
また、中間経路表Ｐ１、及び中間経路表Ｐ２は、次のように生成される。
【０１５９】
Ｐ１［（３，５）］＝１１、  Ｐ１［（６，８）］＝１２
Ｐ２［１１］＝［３，４，５］、  Ｐ２［１２］＝［６，７，８］
【０１６０】
次に、図１５に示す行列生成処理の動作について具体的に説明する。以下、求める最短経路の終点をｊとして、各頂点から終点ｊ（ｊ＝１，２，・・・，１０）までの最短経路を求める場合について説明する。
【０１６１】
ｊ＝１の場合、ステップＳ４３で、Ｃ［ｊ＝１］＝１であるので、ｃ＝１となる。また、Ｒ［ｄ＝０］＝［（ｊ＝１，（ＮＰ，Ｎｏｎｅ，Ｎｏｎｅ））］が設定される。
【０１６２】
ステップＳ４４〜Ｓ４７の処理が実行されると、最短経路行列Ｓは、図１９のＳ−１１に示すように、ｊ＝１についての初期状態となる。このとき、Ｒ［ｄ＝０］にはタプルが１つ格納されているため、ステップＳ４９に進み、Ｒ［ｄ＝０＋１］＝［  ］となる。Ｒ［ｄ−１＝０］にはタプル（１，（ＮＰ，Ｎｏｎｅ，Ｎｏｎｅ））が格納されており、ステップＳ５１で、このタプルが未処理のタプル（ｉ，ｍ）として取り出される。すなわち、ｉ＝１、ｍ＝（ＮＰ，Ｎｏｎｅ，Ｎｏｎｅ）である。Ａ［ｉ＝１］＝［２］であるので、ステップＳ５２で、ｋ＝２が選択され、Ｓ［ｋ＝２、ｊ＝１］＝Ｉであるので、図１６に示す（ｋ、ｍ’）取得処理が実行される。
【０１６３】
ｍ．ｓｔａｔｅ＝ＮＰ、Ｃ［ｋ］＝１＝ｃ（＝１）であるので、ステップＳ６３で、ｍ’＝ｍとする。ｍ’ ．ｓｔａｔｅ＝ＮＰであるので、ステップＳ７８で、Ｓ［ｋ＝２，ｊ＝１］＝ｉ（＝１）を格納し、（ｋ＝２，ｍ’＝（ＮＰ，Ｎｏｎｅ，Ｎｏｎｅ））を返す。これにより、Ｒ［１］＝［（２，（ＮＰ，Ｎｏｎｅ，Ｎｏｎｅ））］となる。
【０１６４】
この段階で、Ａ［ｉ］に未処理の頂点ｋが存在しなくなり、また、Ｒ［ｄ−１］に未処理のタプル（ｉ，ｍ）が存在しなくなるため、ステップＳ４８に戻る。このとき、Ｒ［ｄ＝１］＝［（２，（ＮＰ，Ｎｏｎｅ，Ｎｏｎｅ））］であるので、ステップＳ４９に進み、Ｒ［ｄ＝１＋１］＝［  ］となる。このとき、Ｒ［ｄ−１＝１］にはタプル（２，（ＮＰ，Ｎｏｎｅ，Ｎｏｎｅ））が格納されており、ステップＳ５１で、このタプルが未処理のタプル（ｉ，ｍ）として取り出される。すなわち、ｉ＝２、ｍ＝（ＮＰ，Ｎｏｎｅ，Ｎｏｎｅ）である。Ａ［ｉ＝２］＝［１，３］であるので、ステップＳ５２で、まず、ｋ＝１が選択されたとすると、Ｓ［ｋ＝１、ｊ＝１］≠Ｉであるので、ステップＳ５１に戻る。
【０１６５】
次に、ｋ＝３が選択され、Ｓ［ｋ＝３、ｊ＝１］＝Ｉであるので、図１６に示す（ｋ、ｍ’）取得処理が実行される。ｍ．ｓｔａｔｅ＝ＮＰ、Ｃ［ｋ］＝２≠ｃ（＝１）であるので、ステップＳ６４で、ｍ’＝（ＩＰ，ｋ＝３，０）とする。ｍ’ ．ｓｔａｔｅ＝ＩＰであるので、ステップＳ７８で、Ｓ［ｋ＝３，ｊ＝１］＝ｉ（＝２）を格納し、（ｋ＝３，ｍ’＝（ＩＰ，ｋ＝３，０））を返す。これにより、Ｒ［２］＝［（３，（ＩＰ，３，０））］となる。
【０１６６】
この段階で、Ａ［ｉ］に未処理の頂点ｋが存在しなくなり、また、Ｒ［ｄ−１］に未処理のタプル（ｉ，ｍ）が存在しなくなるため、ステップＳ４８に戻る。このとき、Ｒ［ｄ＝２］＝［（３，（ＩＰ，３，０））］であるので、ステップＳ４９に進み、Ｒ［ｄ＝２＋１］＝［  ］となる。このとき、Ｒ［ｄ−１＝２］にはタプル（３，（ＩＰ，３，０））が格納されており、ステップＳ５１で、このタプルが未処理のタプル（ｉ，ｍ）として取り出される。すなわち、ｉ＝３、ｍ＝（ＩＰ，３，０）である。Ａ［ｉ＝３］＝［２，４］であるので、ステップＳ５２で、まず、ｋ＝２が選択されたとすると、Ｓ［ｋ＝３、ｊ＝１］≠Ｉであるので、ステップＳ５１に戻る。
【０１６７】
次に、ｋ＝４が選択され、Ｓ［ｋ＝４、ｊ＝１］＝Ｉであるので、図１６に示す（ｋ、ｍ’）取得処理が実行される。ｍ．ｓｔａｔｅ＝ＩＰ、Ｃ［ｋ］＝２＝Ｃ［ｍ．ｕｎｏ＝３］（＝２）であるので、ステップＳ６７で、ｍ’＝（ＩＰ，ｍ．ｕｎｏ＝３，ｍ．ｌｅｎ＋１＝１）とする。ｍ’．ｓｔａｔｅ＝ＩＰであるので、ステップＳ７８で、Ｓ［ｋ＝４，ｊ＝１］＝ｉ（＝３）を格納し、（ｋ＝４，ｍ’＝（ＩＰ，３，１））を返す。これにより、Ｒ［３］＝［（４，（ＩＰ，３，１））］となる。
【０１６８】
この段階で、Ａ［ｉ］に未処理の頂点ｋが存在しなくなり、また、Ｒ［ｄ−１］に未処理のタプル（ｉ，ｍ）が存在しなくなるため、ステップＳ４８に戻る。このとき、Ｒ［ｄ＝３］＝［（４，（ＩＰ，３，１））］であるので、ステップＳ４９に進み、Ｒ［ｄ＝３＋１］＝［  ］となる。このとき、Ｒ［ｄ−１＝３］にはタプル（４，（ＩＰ，３，１））が格納されており、ステップＳ５１で、このタプルが未処理のタプル（ｉ，ｍ）として取り出される。すなわち、ｉ＝４、ｍ＝（ＩＰ，３，１）である。Ａ［ｉ＝４］＝［３，５］であるので、ステップＳ５２で、まず、ｋ＝３が選択されたとすると、Ｓ［ｋ＝３、ｊ＝１］≠Ｉであるので、ステップＳ５１に戻る。
【０１６９】
次に、ｋ＝５が選択され、Ｓ［ｋ＝５、ｊ＝１］＝Ｉであるので、図１６に示す（ｋ、ｍ’）取得処理が実行される。ｍ．ｓｔａｔｅ＝ＩＰ、Ｃ［ｋ］＝２＝Ｃ［ｍ．ｕｎｏ＝３］（＝２）であるので、ステップＳ６７で、ｍ’＝（ＩＰ，ｍ．ｕｎｏ＝３，ｍ．ｌｅｎ＋１＝２）とする。ｍ’ ．ｓｔａｔｅ＝ＩＰであるので、ステップＳ７８で、Ｓ［ｋ＝５，ｊ＝１］＝ｉ（＝４）を格納し、（ｋ＝５，ｍ’＝（ＩＰ，３，２））を返す。これにより、Ｒ［４］＝［（５，（ＩＰ，３，２））］となる。
【０１７０】
この段階で、Ａ［ｉ］に未処理の頂点ｋが存在しなくなり、また、Ｒ［ｄ−１］に未処理のタプル（ｉ，ｍ）が存在しなくなるため、ステップＳ４８に戻る。このとき、Ｒ［ｄ＝４］＝［（５，（ＩＰ，３，２））］であるので、ステップＳ４９に進み、Ｒ［ｄ＝４＋１］＝［  ］となる。このとき、Ｒ［ｄ−１＝４］にはタプル（５，（ＩＰ，３，２）））が格納されており、ステップＳ５１で、このタプルが未処理のタプル（ｉ，ｍ）として取り出される。すなわち、ｉ＝５、ｍ＝（ＩＰ，３，２）である。Ａ［ｉ＝５］＝［４，６］であるので、ステップＳ５２で、まず、ｋ＝４が選択されたとすると、Ｓ［ｋ＝４、ｊ＝１］≠Ｉであるので、ステップＳ５１に戻る。
【０１７１】
次に、ｋ＝６が選択され、Ｓ［ｋ＝６、ｊ＝１］＝Ｉであるので、図１６に示す（ｋ、ｍ’）取得処理が実行される。ｍ．ｓｔａｔｅ＝ＩＰ、Ｃ［ｋ］＝３≠Ｃ［ｍ．ｕｎｏ＝３］（＝２）、Ｌｍｉｎ（＝２）≦ｍ．ｌｅｎ＝２、ｉ＝５＞ｍ．ｕｎｏ＝３であるので、ステップＳ７１で、Ｐ１［ｍ．ｕｎｏ＝３，ｉ＝５］＝１１を取得し、符号を反転し、ｕｎｏ＝−１１とする。そして、ステップＳ７２で、ｍ’＝（ＣＰ，ｕｎｏ＝−１１，ｍ．ｌｅｎ＝２）とする。ｍ’ ．ｓｔａｔｅ＝ＣＰであるので、ステップＳ７７で、Ｓ［ｋ＝６，ｊ＝１］＝ｍ’．ｕｎｏ（＝−１１）を格納し、（ｋ＝６，ｍ’＝（ＣＰ，−１１，２））を返す。これにより、Ｒ［５］＝［（６，（ＣＰ，−１１，２））］となる。
【０１７２】
この段階で、Ａ［ｉ］に未処理の頂点ｋが存在しなくなり、また、Ｒ［ｄ−１］に未処理のタプル（ｉ，ｍ）が存在しなくなるため、ステップＳ４８に戻る。このとき、Ｒ［ｄ＝５］＝［（６，（ＣＰ，−１１，２））］であるので、ステップＳ４９に進み、Ｒ［ｄ＝５＋１］＝［  ］となる。このとき、Ｒ［ｄ−１＝５］にはタプル（６，（ＣＰ，−１１，２））が格納されており、ステップＳ５１で、このタプルが未処理のタプル（ｉ，ｍ）として取り出される。すなわち、ｉ＝６、ｍ＝（ＣＰ，−１１，２）である。Ａ［ｉ＝６］＝［５，７］であるので、ステップＳ５２で、まず、ｋ＝５が選択されたとすると、Ｓ［ｋ＝５、ｊ＝１］≠Ｉであるので、ステップＳ５１に戻る。
【０１７３】
次に、ｋ＝７が選択され、Ｓ［ｋ＝７、ｊ＝１］＝Ｉであるので、図１６に示す（ｋ、ｍ’）取得処理が実行される。ｍ．ｓｔａｔｅ＝ＣＰであるので、ステップＳ６３で、ｍ’＝ｍとなる。ｍ’．ｓｔａｔｅ＝ＣＰであるので、ステップＳ７７で、Ｓ［ｋ＝７，ｊ＝１］＝ｍ’．ｕｎｏ（＝−１１）を格納し、（ｋ＝７，ｍ’＝（ＣＰ，−１１，２））を返す。これにより、Ｒ［６］＝［（７，（ＣＰ，−１１，２））］となる。
【０１７４】
一旦ｍ．ｓｔａｔｅ＝ＣＰとなると、以降同様の処理となるため、Ｓ［ｋ＝８，ｊ＝１］＝Ｓ［ｋ＝９，ｊ＝１］＝Ｓ［ｋ＝１０，ｊ＝１］＝−１１である。したがって、ｊ＝１の終了時には、最短経路行列Ｓは、図１９のＳ−１２に示す状態となる。ｊ＝２，・・・，１０についても同様に処理し、ｊ＝１０についての処理終了時には、最短経路行列Ｓは、図２０のＳ−１３に示す状態となる。
【０１７５】
次に、図２１に示す最短経路復元処理について説明する。
【０１７６】
ステップＳ１０１で、復元部２２が、受け付けた最短経路σ［ｉ，ｊ］の問い合わせについて、ｉ＝ｊか否かを判定する。ｉ≠ｊの場合には、処理はステップＳ１０２へ移行し、ｉ＝ｊの場合には、処理はステップＳ１１０へ移行する。
【０１７７】
ステップＳ１０２では、復元部２２が、行列ＤＢ３０に格納された最短経路行列Ｓにアクセスし、Ｓ［ｉ，ｊ］の値ｋを取得する。この際、最短経路行列Ｓのデータを伸長した上で、Ｓ［ｉ，ｊ］の値ｋを取得する。
【０１７８】
次に、ステップＳ１０３で、復元部２２が、上記ステップＳ１０２で取得した値ｋが、グラフＧの頂点の数（頂点番号の最大値）ｎより大きいか否かを判定する。ｎ＜ｋの場合には、ｋは中間経路番号であることを表しているため、処理はステップＳ１０４へ移行し、復元部２２が、伸長した中間経路表Ｐ２からＰ２［ｋ］に対応付けられた中間経路を取得し、変数ｉｐａｔｈに設定する。また、復元部２２は、ｉｐａｔｈの始点を変数ｋ１、終点を変数ｋ２に設定する。
【０１７９】
次に、ステップＳ１０５で、復元部２２が、以下に示すように最短経路を復元する。
ｐａｔｈ＝σ［ｉ，ｋ１］  ＋  ｉｐａｔｈ  ＋  σ［ｋ２，ｊ］
【０１８０】
一方、上記ステップＳ１０３で、ｎ≧ｋと判定された場合には、処理はステップＳ１０６へ移行し、復元部２２が、ｋが−ｎより小さい否かを判定する。ｋ＜−ｎの場合には、ｋは中間経路番号の符号を反転した値であることを表しているため、処理はステップＳ１０７へ移行し、復元部２２が、中間経路表Ｐ２からＰ２［−ｋ］に対応付けられた中間経路を取得し、変数ｉｐａｔｈに設定する。また、復元部２２は、ｉｐａｔｈの終点を変数ｋ１、始点を変数ｋ２に設定する。
【０１８１】
次に、ステップＳ１０８で、復元部２２が、以下に示すように最短経路を復元する。
ｐａｔｈ＝σ［ｉ，ｋ１］
＋  ｒｅｖｅｒｓｅ（ｉｐａｔｈ）  ＋  σ［ｋ２，ｊ］
【０１８２】
ここで、ｒｅｖｅｒｓｅ（ｉｐａｔｈ）は、ｉｐａｔｈが示す頂点列を逆順にすることを表す。
【０１８３】
また、上記ステップＳ１０３及びＳ１０６が否定判定になる場合は、ｋは頂点ｉの親の頂点番号であることを表している。そこで、処理はステップＳ１０９へ移行し、復元部２２が、以下に示すように最短経路を復元する。
ｐａｔｈ＝［ｉ，ｋ］  ＋  σ［ｋ，ｊ］
【０１８４】
なお、上記ステップＳ１０５及びＳ１０８におけるσ［ｉ，ｋ１］及びσ［ｋ２，ｊ］、並びに上記ステップＳ１０９におけるσ［ｋ，ｊ］については、本最短経路復元処理のステップＳ１０１〜Ｓ１１０を再帰的に実行することにより求める。
【０１８５】
また、上記ステップＳ１０１で、ｉ＝ｊと判定された場合には、最短経路行列Ｓにアクセスすることなく、ステップＳ１１０で、復元部２２が、ｐａｔｈ＝［ｉ］とする。
【０１８６】
次に、ステップＳ１１１で、復元部２２が、最短経路σ［ｉ，ｊ］の問い合わせに対して、ｐａｔｈを出力し、最短経路復元処理は終了する。
【０１８７】
以上説明したように、本実施形態に係る情報処理装置によれば、最短経路行列生成部が、グラフに含まれる各頂点間の最短経路を表す最短経路行列の各要素の値として、最短経路上の長さ２以上の中間経路の識別情報を用いる。これにより、最短経路行列から最短経路を復元する際の最短経路行列へのアクセス回数を削減することができ、最短経路を高速に復元することができる。
【０１８８】
なお、上記実施形態では、最短経路行列から最短経路を復元する際に、最短経路行列に親の頂点番号のみを用いる場合には不要である中間経路表Ｐ２へのアクセスが必要にはなるが、以下で説明するように、その影響は少ないと考えられる。
【０１８９】
図２２に示すように、線状にｎ個の頂点が並んでいるグラフの左端にある始点から右端にある終点までの最短経路におけるアクセス回数を考える。両端にそれぞれ、ｍ／２個の頂点からなるクラスタと、それらの間にあるそれぞれｍ個の頂点からなる１０個のクラスタ、計１２個のクラスタに分割されていて、各クラスタ間は切断辺で結ばれているものとする。すなわち、ｎ＝１１ｍが成り立っている。
【０１９０】
この始点から終点までのアクセス回数を、最短経路行列に親の頂点番号のみを用いる方式（以下、「比較方式」という）と上記実施形態の方式（以下、「本方式」という）とで比較した結果を図２３に示す。最短経路行列へのアクセス回数は比較方式ではｎ−１回、本方式では、ｍ＋１９（＝ｍ／２×２＋１９）回である。また、中間経路表Ｐ２へのアクセス回数は、比較方式では中間経路表Ｐ２を用いないため０回であり、本方式では、途中で通過するクラスタ１０個に対応して、１０回である。
【０１９１】
上述のように最短経路行列へのアクセスと、中間経路表Ｐ２へのアクセスでは処理負荷が異なる可能性があるが、大きくは変わらないと想定して、ここでは処理負荷が同じものとして、合計アクセス回数を計算している。したがって、合計アクセス回数は、比較方式の場合がｎ−１回、本方式の場合がｍ＋２９回となる。そして、合計アクセス回数は、ｎ＝１１０の場合は、比較方式に比べ本方式が約１／２．８で済み、ｎ＝１１００の場合は、約１／８．５で済むことを示している。
【０１９２】
また、上記実施形態では、グラフの分割数ｐを調整することで、中間経路表Ｐ２のサイズと、最短経路行列及び中間経路表Ｐ２へのアクセス回数とのバランスを取ることができる。
【０１９３】
図２４に、１７個の頂点からなるグラフにおいて、分割数ｐを１から４まで変化させた場合のクラスタリングの例を示す。ｐ＝１の場合は、分割した結果のクラスタの数が１個である場合、すなわち、分割していない元のグラフを表している。
【０１９４】
図２５に、ｐの値毎に、中間経路表Ｐ２のサイズと、最短経路行列及び中間経路表Ｐ２への平均アクセス回数と、それらの合計とを示す。中間経路表Ｐ２は通常ディスクに格納される。ただし、ここでは、サイズが小さいため、中間経路表Ｐ２は主記憶上にあることを仮定した。また、中間経路表Ｐ２のサイズを計算するに当たっては、中間経路表Ｐ２がハッシュ表であり、ハッシュバケットの数が要素数に等しいこと、要素毎にネクストポインタを持つこと、経路を記憶するためにその長さも記憶しておくことが必要なことを仮定した。また、平均アクセス回数は、頂点２から１７、３から１１、９から１７、及び３から１５の４つの最短経路の平均アクセス回数をもとに計算した。
【０１９５】
中間経路表Ｐ２のサイズが１０までしか許容できないのであれば、ｐ＝１又はｐ＝２を選択することになるが、平均合計アクセス回数はともに７．２５で同じであるため、どちらを選んでもよい。一方、中間経路表Ｐ２のサイズが２０まで許容できるのであれば、より平均合計アクセス回数が少ないｐ＝３を選択する。さらに、中間経路表Ｐ２のサイズが４０まで許容できたとしても、ｐ＝４の場合、中間経路表Ｐ２のサイズがさらに増えるにも関わらず、平均合計アクセス回数は６．５回とかえって増えてしまうため、やはりｐ＝３を選ぶことになる。なお、ｐ＝２の場合、２つのクラスタに分割されるが、それぞれ切断点を１つしか有しないため、中間経路表に登録される中間経路は存在しない。
【０１９６】
この例ではグラフが小さい（頂点数が少ない）ため、中間経路を使わない比較方式に相当する場合（ｐ＝１，２）と、中間経路を使う場合（ｐ＝３，４）との差や、中間経路を使う場合でのｐ＝３とｐ＝４との差が少ない。しかし、大きなグラフ（頂点数が多いグラフ）では、この差が大きくなることが想定される。
【０１９７】
なお、上記実施形態では、重みなし無向グラフに含まれる頂点間の最短経路を表す最短経路行列を生成する場合について説明したが、開示の技術は、その他の態様のグラフにも適用することができる。
【０１９８】
具体的には、上記実施形態で説明した重みなしの無向グラフのクラスタリングを重みありグラフへ適用する場合、重みがないものとみなして、又は重みが全て１であるものとみなして、上記実施形態と同様の方法でクラスタリングすればよい。また、有向グラフへ適用する場合は、有向グラフを無向グラフとみなして、上記実施形態と同様の方法でクラスタリングすればよい。
【０１９９】
また、上記実施形態における中間経路表の生成を重みありグラフへ適用する場合、切断点間の最短経路、すなわち中間経路を求める際に、重みありグラフに適した手法を用いればよい。例えば、実施形態のように幅優先探索ではなく、重みありグラフの最短経路を求めるアルゴリズムとしてよく知られているＤｉｊｋｓｔｒａの方法を用いることで対応することができる。
【０２００】
また、上記実施形態における中間経路表の生成を有向グラフへ適用する場合、無向グラフの場合と異なり、全ての切断点間の最短経路が存在するとは限らない。例えば、切断点ｋ１からｋ２への中間経路が存在しても、ｋ２からｋ１への中間経路が存在するとは限らない。ただし、この点は、上記実施形態における中間経路表の生成において問題とならない。２つの中間経路表のいずれも、辿れる経路だけが参照されるため、辿れない経路を登録する必要はないからである。なお、無向グラフでは、スペースの節約のため、ｋ１＜ｋ２となる中間経路だけを格納した。上記のことから、有向グラフでは、ｋ１＞ｋ２でｋ１からｋ２への中間経路が存在するが、ｋ２からｋ１への中間経路が存在しない場合には、ｋ１からｋ２への中間経路を格納する必要がある。
【０２０１】
また、上記実施形態における中間経路番号を用いた最短経路行列の生成を重みありグラフへ適用する場合、上述のＤｉｊｋｓｔｒａ法に、上記実施形態のような改造を加えることで対応することが可能である。具体的には、Ｄｉｊｋｓｔｒａ法では、頂点を長さと共に優先度付キューで管理するが、その際に、上記のｍの値も同時に管理するようにすることで、実現可能となる。
【０２０２】
また、上記実施形態における中間経路番号を用いた最短経路行列の生成を有向グラフへ適用する場合、強連結でない限り、ある頂点ｉからある頂点ｊへの最短経路が存在しないということが起きる。すなわち、各頂点ｉから終点であるｊまでの最短経路を求める際に、有向グラフの場合は、到達できないｊが存在する可能性がある。したがって、その到達できていないｊに関しては、アルゴリズムの処理が終わった時点でＳ［ｉ，ｊ］の値が初期値であるＩのままになっている。このＩをｉからｊへは到達できないことを意味するものと読み替えることで、有向グラフにも対応することが可能である。
【０２０３】
また、上記実施形態を非連結なグラフに適用する場合、以下のように対応することが可能である。なお、無向グラフの場合、連結でない場合、そのグラフは非連結であるということにする。また、有向グラフの場合、辺の向きを無視して無向グラフとみなしたときに連結でない場合、そのグラフは非連結であるということにする。
【０２０４】
まず、既存の方法を用いてグラフＧを連結部分グラフに分割する。ここで、ｑ個の連結部分グラフＧ１，Ｇ２，・・・，Ｇｑに分割されたものとする。また、各Ｇｉは、Ｇｉ＝（Ｖｉ，Ｅｉ）であるものとする。この際、後述の行列の合成を簡易にするため、Ｖの頂点に付与されている１からｎまでの番号を、ｉ＜ｊとして、Ｖｉの頂点番号の方がＶｊの頂点番号よりも小さくなるように付与し直すものとする。
【０２０５】
そして、１≦ｉ≦ｑとして、各連結部分グラフＧｉに対し、上記実施形態で述べた方法を用いて、それぞれの最短経路行列Ｓｉ及び中間経路表Ｐ２，ｉを生成する。中間経路番号は、ｎ＋１から始めて、ｑ個の連結部分グラフに渡って一意に付与するものとする。そして、こうして求められたｑ個の最短経路行列と中間経路表を次のように合成する。
【０２０６】
まず、最短経路行列の合成について説明する。ｑ個の最短経路行列Ｓ１，Ｓ２，・・・，Ｓｑを、図２６に示すように合成して、最終的な最短経路行列Ｓを生成する。図２６中の網掛け部分の要素には、有向グラフの場合にＩが経路がないことを意味したのと同様に、経路がない（親がない）ことを示す意味でＩを格納する。
【０２０７】
次に、中間経路表の合成について説明する。合成の結果を格納する中間経路表をＰ２とする。そして、Ｐ２，ｉ（１≦ｉ≦ｑ）の要素を順にＰ２に格納し直す。すなわち、中間経路［ｉ１，ｉ２，・・・，ｉｈ］に対する統合番号がｕｎｏであり、Ｐ２，ｉ［ｕｎｏ］＝［ｉ１，ｉ２，・・・，ｉｈ］の場合、Ｐ２［ｕｎｏ］＝［ｉ１，ｉ２，・・・，ｉｈ］となるようにする。
【０２０８】
また、上記実施形態では、中間経路表を、最短経路行列を生成する前に生成する場合について説明したが、これに限定されない。前もって中間経路表を生成するのではなく、最短経路行列を生成する際に、中間経路表を生成してもよい。具体的には以下のとおりである。
【０２０９】
１）  空の中間経路表Ｐ１を準備する。
２）  最短経路行列を生成中に、切断点間の中間経路に遭遇した際に、その中間経路が中間経路表Ｐ１に登録されているか否かをチェックする。登録されていなければ、この時点で登録する。
３）  中間経路表Ｐ２も中間経路表Ｐ１に登録された中間経路に限って生成する。
【０２１０】
以上を実現するために、最短経路中の中間経路や、中間経路を見つける過程における状態に関する情報を記憶するｍに、切断点以降の経路も記憶しておく。この改善を加えることで、切断点間の最短経路を前もって求める処理が省略され、中間経路表Ｐ１、Ｐ２に登録する中間経路を必要最小限に絞ることができる。
【０２１１】
なお、上記実施形態では、最短経路行列生成プログラム５０、及び最短経路復元プログラム６０が記憶部４３に予め記憶（インストール）されている態様を説明したが、これに限定されない。ＣＤ−ＲＯＭやＤＶＤ−ＲＯＭ等の記憶媒体に記録された形態で提供することも可能である。
【０２１２】
以上の実施形態に関し、更に以下の付記を開示する。
【０２１３】
（付記１）
複数の頂点と頂点間を接続する辺とで表されたグラフにおける各頂点間の最短経路上の２以上の辺を含む中間経路の各々に識別情報を付与し、
前記グラフに含まれる全頂点から全頂点への最短経路を表す行列の各要素の値として、前記各要素に対応する行及び列に対応する頂点間の最短経路上の中間経路の識別情報を用いて最短経路行列を生成する
ことを含む処理をコンピュータに実行させるための最短経路行列生成プログラム。
【０２１４】
（付記２）
前記グラフを、指定された数の部分グラフに分割し、各部分グラフについて、前記部分グラフに含まれる頂点を用いて表され、かつ他の部分グラフと辺で接続された頂点を始点及び終点とする経路を、前記中間経路とする付記１に記載の最短経路行列生成プログラム。
【０２１５】
（付記３）
前記中間経路と、前記中間経路の識別情報とを対応付けた中間経路表を生成し、
前記最短経路行列の各要素の値として前記中間経路の識別情報を用いる際、前記中間経路表を参照する
付記１又は付記２に記載の最短経路行列生成プログラム。
【０２１６】
（付記４）
前記中間経路表として、インデックス付表を用いる付記３に記載の最短経路行列生成プログラム。
【０２１７】
（付記５）
付記３又は付記４に記載の最短経路行列生成プログラムにより生成された前記最短経路行列及び前記中間経路表を用いて、指定された頂点間の最短経路を復元する処理をコンピュータに実行させるための最短経路復元プログラム。
【０２１８】
（付記６）
複数の頂点と頂点間を接続する辺とで表されたグラフにおける各頂点間の最短経路上の２以上の辺を含む中間経路の各々に識別情報を付与する付与部と、
前記グラフに含まれる全頂点から全頂点への最短経路を表す行列の各要素の値として、前記各要素に対応する行及び列に対応する頂点間の最短経路上の中間経路の識別情報を用いて最短経路行列を生成する生成部と、
を含む最短経路行列生成装置。
【０２１９】
（付記７）
前記付与部は、前記グラフを、指定された数の部分グラフに分割し、各部分グラフについて、前記部分グラフに含まれる頂点を用いて表され、かつ他の部分グラフと辺で接続された頂点を始点及び終点とする経路を、前記中間経路とする付記６に記載の最短経路行列生成装置。
【０２２０】
（付記８）
前記付与部は、前記中間経路と、前記中間経路の識別情報とを対応付けた中間経路表を生成し、
前記生成部は、前記最短経路行列の各要素の値として前記中間経路の識別情報を用いる際、前記中間経路表を参照する
付記６又は付記７に記載の最短経路行列生成装置。
【０２２１】
（付記９）
前記付与部は、前記中間経路表として、インデックス付表を用いる付記８に記載の最短経路行列生成装置。
【０２２２】
（付記１０）
【０２２３】
最短経路行列生成装置により生成された前記最短経路行列及び前記中間経路表を用いて、指定された頂点間の最短経路を復元する復元部
を含む最短経路復元装置。
【０２２４】
（付記１１）
複数の頂点と頂点間を接続する辺とで表されたグラフにおける各頂点間の最短経路上の２以上の辺を含む中間経路の各々に識別情報を付与し、
前記グラフに含まれる全頂点から全頂点への最短経路を表す行列の各要素の値として、前記各要素に対応する行及び列に対応する頂点間の最短経路上の中間経路の識別情報を用いて最短経路行列を生成する
ことを含む処理をコンピュータが実行する最短経路行列生成方法。
【０２２５】
（付記１２）
前記グラフを、指定された数の部分グラフに分割し、各部分グラフについて、前記部分グラフに含まれる頂点を用いて表され、かつ他の部分グラフと辺で接続された頂点を始点及び終点とする経路を、前記中間経路とする付記１１に記載の最短経路行列生成方法。
【０２２６】
（付記１３）
前記中間経路と、前記中間経路の識別情報とを対応付けた中間経路表を生成し、
前記最短経路行列の各要素の値として前記中間経路の識別情報を用いる際、前記中間経路表を参照する
付記１１又は付記１２に記載の最短経路行列生成方法。
【０２２７】
（付記１４）
前記中間経路表として、インデックス付表を用いる付記３に記載の最短経路行列生成方法。
【０２２８】
（付記１５）
付記１３又は付記１４に記載の最短経路行列生成方法により生成された前記最短経路行列及び前記中間経路表を用いて、指定された頂点間の最短経路を復元する処理をコンピュータが実行する最短経路復元方法。
【０２２９】
（付記１６）
複数の頂点と頂点間を接続する辺とで表されたグラフにおける各頂点間の最短経路上の２以上の辺を含む中間経路の各々に識別情報を付与し、
前記グラフに含まれる全頂点から全頂点への最短経路を表す行列の各要素の値として、前記各要素に対応する行及び列に対応する頂点間の最短経路上の中間経路の識別情報を用いて最短経路行列を生成する
ことを含む処理をコンピュータに実行させるための最短経路行列生成プログラムを記憶した記憶媒体。
【符号の説明】
【０２３０】
１０   最短経路行列生成部
１２   付与部
１４   生成部
２０   最短経路復元部
２２   復元部
３０   行列データベース
４０   コンピュータ
４１   ＣＰＵ
４２   メモリ
４３   記憶部
４９   記憶媒体
５０   最短経路行列生成プログラム
６０   最短経路復元プログラム
１００ 情報処理装置
【図１】
2019139576.tif 000003
【図２】
2019139576.tif 000004
【図３】
2019139576.tif 000005
【図４】
2019139576.tif 000006
【図５】
2019139576.tif 000007
【図６】
2019139576.tif 000008
【図７】
2019139576.tif 000009
【図８】
2019139576.tif 000010
【図９】
2019139576.tif 000011
【図１０】
2019139576.tif 000012
【図１１】
2019139576.tif 000013
【図１２】
2019139576.tif 000014
【図１３】
2019139576.tif 000015
【図１４】
2019139576.tif 000016
【図１５】
2019139576.tif 000017
【図１６】
2019139576.tif 000018
【図１７】
2019139576.tif 000019
【図１８】
2019139576.tif 000020
【図１９】
2019139576.tif 000021
【図２０】
2019139576.tif 000022
【図２１】
2019139576.tif 000023
【図２２】
2019139576.tif 000024
【図２３】
2019139576.tif 000025
【図２４】
2019139576.tif 000026
【図２５】
2019139576.tif 000027
【図２６】
2019139576.tif 000028