Search

[그래프] 최단 경로: 다익스트라 알고리즘

최단 경로 문제 알고리즘

다양한 알고리즘이 존재하는데 가장 유명한 알고리즘은 다익스트라 알고리즘이다.

다익스트라 알고리즘

단일-쌍, 단일-출발, 단일-도착 최단 경로 문제를 풀 수 있다. 즉 하나의 정점에서 다른 모든 정점까지의 최단 경로를 구할 수 있다.
여자친구와 커피숍에서 20분만에 고안해서 만든 알고리즘..?
노드 주변의 최단 경로만 택하기 때문에 그리디 알고리즘 중에 하나이다.
BFS를 활용한다.

DFS와 BFS의 차이

DFS : 혼자서 미로를 탐색하는 과정
BFS : 여러 명의 갈림길로 흩어져 길을 찾는 과정
실뭉치를 가지고 풀어놓았다가 되감으면서 길을 찾는다.
먼저 도착한 사람의 실뭉치를 사용

조건

무조건 양의 간선을 가져야 한다.

시간 복잡도

최초 구현으로 O(V^2)
현재는 BFS시 가장 가까운 순서를 찾을 때 우선순위 큐를 사용하므로 O((V+E)log V)이고 모든 정점이 출발지에서 도달이 가능하면 최종적으로 O(E log V)가 된다.

로직

[graph] key=정점, value=[도착정점, 간선(소요시간)]
[dist] key=정점, value=간선(소요시간) 모든 정점의 소요시간을 관리한다.
[pq] [정점, 간선] → 간선이 적은 순서
시작 정점을 힙에 넣는다. → 방문 표시를 한다.
힙이 비어있을 때까지 while문을 돌린다. (꺼낸 노드 V)
V에 대해 연결된 정점을 순회한다. (연결된 정점 nei)
방문하지 않은 정점을 pq에 넣는다. (nei정점, nei 간선 + V의 현재 간선)

참고 자료