グラフの2番目に短いパスを見つける（バックトラッキングあり）

Question

LightOJの問題点は、ノード1からノードnまでのグラフの中で2番目に短いパスを見つけることでした。 〜n）。今、問題は、私が第2の最短経路を見つけるために後退することができると述べました。サンプルのいずれかの場合、このようなものです：、

• エッジノード1から2〜3ノード2から100
• エッジを要し、3ノード1から300
• エッジを要し、50費用

このテストの回答は、このパス1-> 2-> 1-> 3です。 私はDijkstraアルゴリズムを知っています。しかし、私はこれを行う方法について何も見つけることができませんでした。これが古いトピックであれば申し訳ありませんが、私はそれを見つけたとき何も見つけられませんでした。

更新：私はこの質問を読んでいます。 Which algorithm can I use to find the next to shortest path in a graph? 私の質問はこの問題とは違うので、私はエッジを2回使うことができます。私はノード1からノード2に一度戻ってから1に戻ります。これは、エッジ1 - > 2を2回使用しています。

Answer 1

私はそこにもっと良い解決策があると思います。最初に最短経路を見つける。この最短経路にk個のエッジがあるとします。

i = 1からkまでのループを持ち、毎回pathのi番目のエッジの値を無限大に設定します。その後、最短経路アルゴリズムを実行します。そして、あなたが得るすべてのkの新しい最短経路に最小値を返します。

それぞれ1つのエッジが無限に正確に設定されていることに注意してください。なぜこれは機能しますか？ 1つのエッジで元のものと異なる最短パスを取得するためです。

しかし、2番目に短いパスとは、厳密に高いコストを持つ次の最短パスを意味するため、少し曖昧です。または、2つの異なる最短経路を見つけることを意味する可能性があります。私は私の答えで後者の場合を想定した。