凸関数により重みを変換した際の最短路問題に関する一考察

スポンサーリンク

概要

論文の詳細を見る
最短路問題は、始点と終点の選び方によって3種類ほどに分類されるが、いずれも始点から終点への方向性を持って接続関係を求める辺重視の問題である。一方、最小木問題は、与えられたすべての頂点に対して接続関係のみを求める、方向性を考慮する必要がない頂点重視の問題である。両者の問題は、採択された辺(路あるいは枝)に関して、それらの重みの総和を最小とすることを共に目的としている。さらに、ある頂点を始点、他のすべての頂点を終点とする最短路問題では、いずれかの終点の最短路の部分路になる辺の総数は、最小木の枝の総数に等しく、特別な場合には、それらの辺と枝が完全に一致する。本稿では、各辺に付加された重みが非負なネットワークに関して、特定の頂点を始点、他の頂点を終点とする最短路問題と最小木問題との積極的な関連づけを試みる。
1989-03-15

著者

加藤常員
岡山理科大学

関連論文

スポンサーリンク