Dijkstra Algorithm
최단 경로
최단 경로 정의
: 간선의 가중치가 있는 그래프에서 두 정점 사이의 경로들 중에 간선의 가중치의 합이 최소인 경로
하나의 시작 정점에서 끝 정점까지의 최단 경로 (one to all)
다익스트라 (dijkstra) 알고리즘
음의 가중치를 허용하지 않음
벨만-포드 (Bellman-Ford) 알고리즘
음의 가중치 허용
모든 정점들에 대한 최단 경로
플로이드-워샬 (Floyd-Warshall) 알고리즘
Dijkstra Algorithm
시작 정점에서 거리가 최소인 정점을 선택해 나가면서 최단 경로를 구하는 방식
시작 정점 (s)에서 끝 정점 (t) 까지의 최단 경로에 정점 x가 존재한다
이때, 최단 경로는 s에서 x까지의 최단 경로와 x 에서 t 까지의 최단 경로로 구성된다
탐욕 (greedy) 기법을 사용한 알고리즘으로 MST의
Prim Algorithm
과 유사하다인접 행렬 그래프와 시작 정점이 주어졌을 때, 다익스트라 알고리즘을 사용하면 시작 정점에서 모든 정점으로 가는 최단 거리를 구할 수 있다
시간 복잡도
시간 복잡도
: O(logN)
구현 해보기
Dijkstra + 인접리스트
Last updated