K番目の最短路問題にたいする新しい方法

概要

論文の詳細を見る
Kthバス問題は、バスとしてループを含むことを認める場合と認めない場合、さらに負の距離を考える場合と考えない場合などに、分類される。それらの解法も、最短路からなるツリーを利用する方法、最短路アルゴリズムを繰返し適用する方法、DPによる方法そして経路代数による方法など、いくつか存在する。しかしそのほとんどが、パスとしてループを含むことを認めるものであり、J、Yenの最短路アルゴリズムを繰返し利用する方法が現在唯一のループを含まないパスを求める方法と考えられる。ここでクラブ理論でよく知られている結果、P_1を始点_sから終点_tまでのループを含まないパスをするとき、s、t間のループを含まないパスの集合{P}は{P}=min{P_1[○!+]E;E∈{E}}によって表わされる(Eはオイラーグラフ)、を利用することにより、非負の距離を仮定したグラフ内の任意の2点間のループを含まないKthパスを求めるアルゴリズムを提案する。(ただしK番目パスの長さはK-1番目のパスの長さに等しくてもよいとしている)まず最短路アルゴリズムにより、最短路からなるツリーをつくり、そのツリーを利用してツリーに含まれない枝を正確に一本含むサーキット、C_1、C_2、…、C_<m-n+1>をつくる(m、nはそれぞれグラフ内の枝と点の数)。R_1={P_1}、Q_1=P_1として、一般にk〓2にたいしR_k=(R<k-1>-{Q<k-1>})∪{Q<k-1>[○!+]C_i}となる集合R_kをつくる。ここでC_iはQ<k-1>をつくるために使われていないものとする。次にR_kの中で最小の長さをもつサブグラフの1つをとり出しQ_kとする。このようにして順にQ_1、Q_2、…Q_k、…を求め、この中でパスとなるものを順次取出すことによりK番目のパスを求める。この方法はグラフの構造により効率が大きく変化するが、鉄道のネットワークなどには実用性が確かめられた。
社団法人日本オペレーションズ・リサーチ学会の論文

K番目の最短路問題にたいする新しい方法

スポンサーリンク

概要

著者

関連論文

スポンサーリンク