初歩的なグラフの問題 (ID:72930)

名前

ホームページ(ブログ、Twitterなど)のURL (省略可)

本文 うーんちょっと考えてみたのですが、ワーシャルフロイド法をそのままでは駄目でした。 ダイクストラ法はいわゆる負閉路に引っかかってしまうのでたぶん駄目。 ワーシャルフロイド法に2地点間を結ぶ最短経路全ての点を記録しておいて、これを使って制限を設ければ上手くいくような気もします。 3重ループの中で2点ABを中継点Cを介して結ぶとき、AC,CBを最短で結ぶ2つの経路に共通する部分があればABを辺でなげないという制限を設ければ同じ地点は2度通らないということは実現できそうな気もするのですが。 上手くいかなさそうな気もします。 答えはワーシャルフロイド法で検討するルートに制限をかけたサブセットだろうというイメージはあるのですがなかなか難しいです。 もしNP困難だとしたら最適解はあきらめるしかないですよね。