최단 경로 문제 알고리즘
•
다양한 알고리즘이 존재하는데 가장 유명한 알고리즘은 다익스트라 알고리즘이다.
다익스트라 알고리즘
•
단일-쌍, 단일-출발, 단일-도착 최단 경로 문제를 풀 수 있다. 즉 하나의 정점에서 다른 모든 정점까지의 최단 경로를 구할 수 있다.
•
여자친구와 커피숍에서 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의 현재 간선)
