著者

井口 貴志 高藤 大介 田岡 智志 渡邉 敏正

出版者

一般社団法人電子情報通信学会

雑誌

電子情報通信学会技術研究報告. CAS, 回路とシステム (ISSN:09135685)

巻号頁・発行日

vol.105, no.387, pp.41-46, 2005-11-03

---

辺重み付き有向グラフをネットワークと呼び, 辺重みの増減という辺操作を考える.なお辺重みを無限から有限に減少(それぞれ, 有限から無限に増加)させることは, 辺の追加(辺の削除)に対応する.動的最短経路問題(DSPPと略記)は次のように定義される: "任意のネットワーク, ソースと呼ばれる指定頂点s, 任意の辺操作系列が与えられたとき, 各辺操作の実行後のネットワークにおける最短経路木を再構成せよ".DSPPの応用として, OSPFやIS-ISのようなリンクステート・アルゴリズムに基づいたルーティングプロトコルにおいて, DSPPを効率良く解くことが必要となる.大規模なネットワークと非常に長い辺操作系列に対する実験結果では, Narvaez(2000年)らがで提案したNST(BF)が, 我々が試した現在の10種類の解法の中で最も高速に解を求めることを示した.また, DSPPを解くには, 静的な解法を繰り返して解くよりも, 動的な解法の方が高速に解を求めることも示した.