알고리즘을 보면서도... 문제를 풀면서도 이해가 잘 가지 않아 여러 블로그의 글들을 읽어보았다. 벨만-포드 알고리즘을 공부하면서 들었던 의문점을 정리해보았다.
벨만-포드 알고리즘은 다익스트라 알고리즘과 달리 간선의 가중치가 음수일때도 동작하는 SSP 알고리즘이다.
1. 왜 간선의 가중치가 음수일때도 잘 동작할까?
다익스트라 알고리즘은 그때그때의 상황에 최선의 선택을 하려는 그리디 알고리즘 기반이기 때문에 다음과 같은 상황에서는 통하지 않는다. 벨만-포드는 가능하다. 모든 경우의 수를 다 보기 때문.
2. 모든 경우의 수를 보려면 왜 V-1번 반복해야 할까
사실,방문 순서에 따라 우연히도(u, v)를 먼저 방문하고 dist[v]를 갱신하고 나서 (v, w)를 방문하면 한 번에 dist[w]까지 구해질 것이지만, 그 적절한 방문 순서를 알 방도가 없죠. 모르니까 우린 무식하게 가능한 경우를 다 따져보고 있는 것이구요.
따라서 최악의 사태를 대비하여 루프를 V-1번 돌리는 것이고, V-1번의 루프를 돌리면 아무리 운 나쁘게 갱신이 지연되어도 반드시 dist 값들이 모두 최단 거리를 담고 있게 됩니다.
(Ries 마법의 슈퍼마리오님 블로그에서)
3. V번째 반복에서도 값이 갱신되면 음수 사이클이 존재한다는 것을 알 수 있다. 왜 그럴까?
앞서 말했듯 V-1번의 루프를 돌면 노드의 방문순서에 상관없이 모든 경우의 수를 따져볼 수 있으므로 최단 경로를 구할 수 있다. 하지만 음수 사이클이 존재하면 이 사이클을 돌기만 하면 시간이 계속 줄어들 수 있다. V-1번의 루프 이후에도 값은 계속 줄어들 것이다.
참고) 모든 사이클이 문제가 되는 것은 아니다. 시작점부터 도착점까지의 경로에 포함되는 음수 사이클만 문제가 되는 것이다.
4. res[j] != INF 왜 INF가 아닌 부분만 업데이트 해야하는 걸까? 다익스트라에선 이런 부분이 없었는데.
구현에 따라서 둘 다 시작점에서 도달 불가능한 정점 u, v가 존재하고 (u, v) 가중치가 음수일 때
dist[u] = INF, dist[v] = INF-cost 꼴이 나올 수 있기 때문이다.
백준 타임머신 문제. 벨만-포드 알고리즘을 제대로 이해를 못한 채로 접했었기 때문에 "만약 1번 도시에서 출발해 어떤 도시로 가는 과정에서 시간을 무한히 오래 전으로 되돌릴 수 있다면 첫째 줄에 -1을 출력한다" 이 말도 제대로 이해를 못 했었다. 대강 음수 사이클을 의미하겠거니 했지만 정확히 이해는 못 했었는데, 음수 사이클을 돌기만 하면 최단 경로가 갱신되므로 '무한히 오래 전으로 되돌릴 수 있다' 라고 표현한 것이다.
보통 경로를 지났는데 시간은 덜 걸린다는게 이상해서 실제로 접하기엔 좀 어려운 유형이라고 한다. 타임머신이라는 주제부터가 그렇다.
출처:
'알고리즘 > Shortest Path' 카테고리의 다른 글
| [백준] 알고스팟_1261 (0) | 2020.02.08 |
|---|---|
| [백준] 파티_1238 (0) | 2020.02.06 |