그래프에서 두 번째 최단 경로 찾기 (역 추적 사용)

Question

그래프에서 두 번째로 짧은 경로를 노드 1에서 노드 n으로 찾는 것이 문제가되는 LightOJ에서 문제가 발견되었습니다 (1에서 표시된 그래프에 n 개의 노드가 있음). ~ n). 이제, 문제는 내가 두 번째로 짧은 경로를 찾기 위해 역 추적 할 수 있다고 말했습니다. 샘플 사례 중 하나가이 같다 :

• 에지 노드 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? 이 문제에서는 가장자리를 두 번 사용할 수 있으므로 내 질문이 다릅니다. 노드 1에서 2로 한 번 이동 한 다음 다시 1로 돌아갑니다.이 에지 1-> 2를 두 번 사용합니다.

Answer 1

더 나은 해결책이 있다고 생각합니다. 먼저 최단 경로를 찾습니다. 이 최단 경로에 k 개의 모서리가 있다고 가정 해 봅시다.

i = 1에서 k까지 루프가 있고, 그 다음에는 매번 경로의 i 번째 가장자리 값을 무한대로 설정하십시오. 그런 다음 최단 경로 알고리즘을 실행하십시오. 그리고 당신이 얻는 모든 k 개의 새로운 최단 경로를 통해 최소값을 반환하십시오.

정확히 하나의 가장자리를 무한대로 설정합니다. 왜이게 효과가 있니? 한 모서리에서 원본과 다른 가장 짧은 경로를 얻을 것이기 때문입니다.

그러나 두 번째로 짧은 경로는 엄격하게 높은 비용을 갖는 다음 최단 경로를 의미하기 때문에 질문이 약간 모호합니다. 아니면 두 개의 다른 최단 경로를 찾는 것일 수도 있습니다. 나는 대답에 후자의 경우를 가정했다.