ps:단일_출발지_최단_경로
목차
단일 출발지 최단 경로 (Single Source Shortest Path)
- 위키피디아 참고
- 그래프의 종류에 따라서 어떤 알고리즘을 써야하는지는 아래 순서대로 결정하면 된다
- 트리이면 ⇒ 최단 경로 이전에, 그냥 경로가 하나밖에 없다. BFS든 DFS든 아무거나 쓰면 된다 O(V+E)
- 가중치 없는 그래프의 경우 ⇒ BFS로 돌린다. O(V+E)
- DAG이면 ⇒ 위상정렬에 기반한 방법을 적용 가능. O(V+E)
- 가중치 있는 그래프의 경우
- 가중치가 0 또는 1만 있으면 ⇒ 0-1 BFS O(V+E)
- 가중치가 양수이면 ⇒ 다익스트라. O(ElogV) 또는 O(V^2)
- 가중치가 음수도 있으면 ⇒ 벨만-포드 또는 SPFA가 가능한데 SPFA를 쓰자. O(VE)
- 무향 그래프인 경우는 BFS + 다익스트라로 해결 가능하다.
가중치가 없는 그래프
- 너비우선탐색 (BFS) 을 사용한다.
- 모든 엣지와 모든 노드를 한번씩 방문하니까 O(V+E)이다
- dense 그래프에서는 좀 더 효율적일 수 있는 구현법으로 다음 방법도 있다. 노드마다 연결된 모든 엣지를 방문해보고 unvisited 노드들에 대해서만 처리하는 것이 아니라, unvisited 노드들의 셋을 만들어 유지하면서 unvisited 셋에 있는 노드 중에서 엣지가 존재하는 노드들을 방문하는 식으로 구현하는 방식이다.
가중치가 0 또는 1인 그래프
- 0-1 BFS를 사용하자. 데이크스트라 알고리즘 (Dijkstra's algorithm)에 비해서 빠르게 구할수 있는 방법이다.
- https://justicehui.github.io/medium-algorithm/2018/08/30/01BFS/ 을 참고하자. 자료구조로 덱을 사용해서, add연산을 할때 웨이트가 0일때는 push-front로, 웨이트가 1일때는 push-back으로 해주는 방법이다. 이렇게 해도 덱이 정렬된 상태로 유지되므로 extract-min을 pop-front로 처리할수 있다. 총 시간복잡도는 O(V+E)
- 코드
- 특성상, 스태틱한 그래프에서 적용하는 경우는 별로 없고, 대부분 상태 그래프에서 적용하게 되므로, search 라이브러리에만 구현하고 graph 라이브러리에는 구현하지 않았다.
- 관련 문제
가중치가 양수인 그래프
- 데이크스트라 알고리즘 (Dijkstra's algorithm) 을 사용하면 된다.
- O(ElogV) 또는 O(V^2)
가중치가 양수 또는 음수인 그래프
- 음수 사이클이 있으면 사이클을 빙빙 돌면 되므로 최단 경로가 -INF 가 된다.
- 벨만-포드 알고리즘이나 Shortest Path Faster Algorithm (SPFA) 을 사용하면,
- 음수 사이클이 없는 그래프에서 최단 경로를 찾거나
- 그래프 안에 음수 사이클이 존재하는지를 체크할 수 있다.
- 벨만-포드의 시간복잡도는 O(VE)이다.
- Shortest Path Faster Algorithm (SPFA) 도 최악 O(VE)지만, 평균속도는 더 빠르다고 한다. 벨만-포드 대신에 항상 SFPA를 사용하자
- 무향 그래프인 경우에는, 음수 엣지가 존재하기만 하면 자체로 사이클이 된다. 따라서, 출발점에서 도착 가능한 음수 엣지가 있기만 하다면, 출발점에서 도착가능한 모든 노드까지의 거리는 -inf가 된다. 따라서 알고리즘은 간단하게
- 1) 도착 가능한 엣지들 중에서 음수 엣지가 있는지 찾는다 (BFS)
- 2-1) 도착 가능한 음수 엣지가 있으면 도착가능한 모든 노드까지의 거리는 -inf가 된다. 끝
- 2-2) 도착 가능한 음수 엣지가 없으면, 그냥 양수 가중치 그래프이므로, 다익스트라 알고리즘을 돌려서 거리를 구하면 된다.
- (BFS랑 다익스트라를 따로따로 돌리는 대신 다익스트라를 조금 수정해서 한번만 돌려서 해결하는것도 가능하다)
- 관련문제: 자취방 정하기
그 외의 알고리즘
- D´Esopo-Pape algorithm은 음수 엣지에도 적용할수 있고, 대부분 경우에 다익스트라보다도 빠르다고 한다. 그러나 최악 케이스에는 exponential 시간 복잡도가 된다고 하니.. 굳이 쓸일은 없을것 같다
ps/단일_출발지_최단_경로.txt · 마지막으로 수정됨: 2022/11/25 17:19 저자 teferi
토론