13장. 최단 경로 문제

최단 경로 문제는 각 간선의 가중치 합이 최소가 되는 두 정점(또는 노드)사이의 경로를 찾는 문제다.

• 최단 경로는 한 지점에서 다른 지점으로 갈 때 가장 빠른 길을 찾는 것과 비슷한 문제다.

• 그래프의 종류와 특성에 따라 각각 최적화된 다양한 최단 경로 알고리즘이 존재한다.

• 이 중 가장 유명한 것은 다익스트라(Dijkstra) 알고리즘이다.
• 항상 노드 주변의 최단 경로만을 택하는 대표적인 그리디 알고리즘 중 하나로, 단순할 뿐만 아니라 실행 속도 또한 빠르다.
• 다익스트라 알고리즘은 노드 주변을 탐색할 때 BFS를 이용하는 대표적인 알고리즘이다.
• DFS = 한사람이 미로를 찾아 헤매는 과정, BFS = 여러 사람이 각기 서로 다른 갈림 길로 흩어져 찾는 과정
• 다익스트라 알고리즘은 임의의 정점을 출발 집합에 더할 때, 그 정점까지의 최단거리는 계산이 끝났다는 확신을 가지고 더한다.
• 우선순위 큐 적용시 시간복잡도는 O((V+E)logV)
• 모든 정점이 출발지에서 도달 가능하다면→ O(E log V)

문제 리스트