2019-12-29

알고리즘 문제풀이 스터디 2019-12-29

다익스트라, 벨만 포드, 플로이드, 다익스트라 응용

다익스트라는 음의 사이클 뿐 아니라 음의 간선이 있으면 안 되고, 벨만포드는 사이클만 없으면 가능하다는 듯.

벨만 포드는 N-1번까지 업데이트하면서 가장 긴 경로까지 각 정점에 대해 경로 길이 업데이트가 있는지 확인하고, N번째까지 돌려서 만약 업데이트가 있다면 음의 사이클이 있는 것 (이미 가장 긴 경로에 대해서까지 확인되었어야 하므로)

플로이드 와셜 : all to all, 다른 정점을 거쳐서 더 짧은 경로가 있는지 반복해서 확인해나감

다익스트라 응용 1 - 최단경로에 속하는 경로인지 여부 : 다익스트라를 돌려 최단경로 길이를 알아낸 다음, 다시 거꾸로 bfs를 돌리면서 각 정점들에 대해 찾아놓은 최단경로 길이와 각 간선들의 길이 정보를 이용하여 각 간선이 최단경로에 속하는 간선인지 확인할 수 있다.

다익스트라 응용 2 - all to one 탐색 : 다익스트라는 기본적으로 one to all 경로를 찾는다. 즉 한 점에서 ‘시작’하여 다른 모든 점까지의 최소거리를 찾는다. 그런데 만약 “단방향”그래프에서 모든 점에서 한 점까지의 최단 경로들을 찾고 싶은데, 정점 수가 많다고 하자. 그러면 모든 정점들에서 다익스트라를 돌릴 수는 없다.

이 때, 뒤집기 기술이 나온다. 그래프의 방향들을 뒤집어 저장하고, 목적지로부터 다른 모든 점까지의 경로를 찾으면 그게 all to one 최단경로들이다.