Поиск второго кратчайшего пути в графике (с обратным трассированием)

Question

Я нашел проблему в LightOJ, где проблема заключалась в том, чтобы найти второй самый короткий путь в графе от узла 1 до узла n (На графике, отмеченном с 1, есть n узлов к n). Теперь проблема заключалась в том, что я могу отступить, чтобы найти второй самый короткий путь. Один из образцов случаев, как это:

• Край от узла 1 до 2, стоимость 100.
• края от узла 2 до 3, стоимость 300.
• края от узла 1 до 3, стоимость 50 .

Ответ на этот тест - 150, для этого пути 1-> 2-> 1-> 3. Я знаю об алгоритме Дейкстры. Но я не мог найти ничего о том, как это сделать. Прошу прощения, если это и старая тема, но я, когда я искал ее, ничего не нашел.

Обновление: я прочитал этот вопрос. Which algorithm can I use to find the next to shortest path in a graph? Мой вопрос отличается от этого, потому что в этой проблеме я могу использовать ребро дважды. Я перехожу от узла 1 к 2 один раз, а затем возвращаюсь к 1. Это использование края 1-> 2 дважды.

Answer 1

Я думаю, что для этого есть лучшее решение. Сначала найдите кратчайший путь. Скажем, этот короткий путь имеет к краям.

Имейте петлю от i = 1 до k, а затем каждый раз установите значение i_th края пути на бесконечность. После этого запустите алгоритм кратчайшего пути. И верните минимум по всем k новым самым коротким путям, которые вы получите.

Обратите внимание, что каждый из них устанавливает ровно один край в бесконечность. Почему это работает? Потому что вы получите кратчайший путь, который отличается от оригинала одним краем.

Однако ваш вопрос немного неоднозначен, потому что второй самый короткий путь означает, что следующий короткий путь, который имеет более высокую стоимость. Или это может означать просто найти два разных кратчайших пути. Я принял последний случай в своем ответе.