|
計算量は悪いですがワーシャルフロイド法とプリム法を組み合わせる方法を考えつきましgた。 まずワーシャルフロイド法で、各地点iからjへの最短距離を求め、これをmap[i][j]とします。
地点と道路のグラフをgとします。 一端gの辺を全て削除します。 次に、map[i][j]を点iからjへまっすぐつながった線として解釈しなおし辺を引き直します。 すると全ての点が、他の点とつながったグラフが得られます。 このグラフをnewGとします。
電線の分岐点の集合をB={B1,B2,,,,Bm-1} 目的地の集合を M={M1,M2,,,,Mm} 発電所を Hとします。 とします。 注意点としてBi=BjやBi=Mj,Bi=Hという場合もあります。 Bi=BjならBjを削除し、Bi=Miや=HならBiを削除します。
あるBの組み合わせを考えた時、newGからB、M、Hの点とそれらをつなげる辺を無視します。 後はB,M、Hをつなげる線をプリム法で求めます。 これでBがある組み合わせになった時の電線の最小距離がで木構造が作られます。 Biが木の葉になった場合があるので、葉になるBiがある限りBiを削除します。 これがBがあるセットになった時の電線の最小距離がでます。
後はこれを全てのBの組み合わせで試せば最小距離が出ます。
しかしこれは私が自分で思いついた素朴な方法ですのでもっとましな方法があると思います。
|