최단 경로 알고리즘

가중치 그래프에서 가중치의 합이 최소가 되는 경로 찾는 알고리즘

https://jina-developer.tistory.com/118

https://ratsgo.github.io/data%20structure&algorithm/2017/11/25/shortestpath/

https://techblog-history-younghunjo1.tistory.com/247

https://4legs-study.tistory.com/26

https://cantcoding.tistory.com/8

https://yabmoons.tistory.com/365

벨만 포드 알고리즘 포스팅(문제)

플로이드 워셜 알고리즘

다익스트라와 벨만 포드 차이점

1. 다익스트라는 현재 노드에서 다음 탐색 노드를 고를 때, 방문하지 않은 노드중 시작 노드로부터 가장 거리가 짧은 노드를 골라 방문한다. 이는 곧 한 번 방문한 노드는 다시 방문하지 않는다는(재갱신하는 경우가 없다는) 뜻이다.

   한편 벨만 포드는 모든 노드에 대해, 그 노드와 연결된 모든 노드들을 반드시 방문한다. 즉, 이미 방문했던 노드도 또 방문할 수 있고, 갱신 역시 또 될 수도 있는 것이다.

2. 다익스트라는 현재 노드에 대해, 인접 노드와의 간선만 체크한다.

   벨만 포드는 그래프에 존재하는 모든 간선을 싹 다 체크한다.

   이 동작을 둘 다 V-1번 수행한다.

3. 벨만 포드 알고리즘에서, 모든 간선에 대해 갱신을 수행하는 것을 왜 "V-1"번 수행하는 것일까?

   벨만 포드 알고리즘은 "어떤 노드에서 어떤 노드까지 최단 거리로 갈 때, 많아봐야 최대 V-1번 이동한다" 라는 생각이 기본 토대이다.

   따라서, 모든 간선에 대해 edge relaxation을 수행하는데, 한 번 수행할 때 어떤 특정 노드에 대하여 다른 특정 노드로 한 번 이동하는 셈이기 때문에, 어떤 임의의 그래프에 대해서는 특정 노드에서 모든 노드를 거쳐서, 즉 V-1번 갱신해서 최종 목표로 도달하는 것이 최단 경로인 케이스가 있을 수 있기 때문에 모든 간선에 대해 edge relaxation 하는 것을 V-1 세트 반복하는 것이다. 다르게 말해보자면, 1번 노드에서 10번 노드까지 갈 때, 최악의 경우 1에서 4까지 한 칸이 최단 경로고, 4에서 7까지 한 칸이 최단, 7에서 2까지가 최단, 이런 식으로 한 칸 한 칸이 최단인 경우에는 V-1번, 총 9번을 이동하는 것이 최단 경로인 케이스가 있을 수 있다.

   만약 음의 사이클이 존재한다면, V-1 세트 수행 후 더 수행해도 계속 갱신이 된다. 벨만 포드 알고리즘에서는, 음의 사이클이 없을 때 최단경로가 반드시 V-1번 세트 수행 하에 확정되기 때문에, 음의 사이클이 있는 경우는 최단 경로를 확정지을 수 없다고 결론짓는다. 따라서 V번째 세트를 수행했을 때 갱신이 발생한다면 음의 사이클이 존재하는 것임을 확인할 수 있다.

4. 벨만 포드 알고리즘의 규칙 중 하나는, 어떤 간선의 출발 노드가 한 번이라도 갱신 된(탐색한) 노드여야만 도착 노드를 갱신시킬 수 있다는 것이다.

   이 때, V-1번 모든 간선 탐색을 수행할 때, 순서는 상관이 없다. 왜냐하면 구현할 때 출발 노드가 INF인 간선의 경우 continue를 해주기 때문이고,

   만약 1 -> 2 -> 3 -> 4 이런 그래프가 있다고 치면, 안 좋은 순서로 탐색한다고 치면 3->4, 2->3, 1->2 순서로 첫 세트를 돌면 2의 최단거리 하나만 갱신이 된다. 이런 식으로, 최악의 순서로 탐색했을 때 출발 노드 1로부터 모든 노드까지의 최단 거리가 다 구해지려면 3번 탐색해야한다. 즉, 4-1 = 3번 돌면 최적해를 반드시 구할 수 있다. 물론 음의 사이클이 있는 경우는 예외다.