최단 경로 문제란?

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

정점(Vertex) - 교차로

간선(Edge) - 길

가중치(Weight) - 거리나 시간과 같은 이동 비용

그래프의 종류와 특성에 따라 다양한 최적화된 최단 경로 알고리즘이 존재한다. 가장 유명한 것이 다익스트라(Dijkstra) 알고리즘

다익스트라 알고리즘

항상 노드 주변의 최단 경로만을 택하는 대표적인 그리디 알고리즘 중 하나로, 단순할 뿐만 아니라 실행 속도 또한 빠르다. BFS를 이용하는 대표적 알고리즘

책에서 실로 비교한 것 → 길이의 가중치가 가장 짧은 경로를 탐색하는 것?

다익스트라 알고리즘은 가중치가 음수인 경우를 처리할 수 없다.

시간복잡도

최초 구현에서는 O(V^2) 이었으나 우선순위 큐를 적용하였을 때 O( ( V + E ) log V ), 모든 정점이 출발지에서 도달 가능할 때는 O( E logV )