티스토리 뷰
728x90
반응형
다익스트라 (Dijkstra)
- 단일 시작점에서 다른 모든 정점까지 최단 경로
- 음수 가중치, 사이클이 있는 그래프 불가
- 인접리스트, 우선순위큐 사용
- 정점에서 가까운 순으로 다음 정점 선택 (탐욕적)
- O((E+V)logn)
- 최단 경로 갱신 가능
728x90
반응형
'Algorithm' 카테고리의 다른 글
최단 경로 알고리즘 - Floyd Warshall (0) | 2020.04.05 |
---|---|
최단 경로 알고리즘 - Bellman Ford (0) | 2020.04.05 |
최단 경로 알고리즘 - 최소신장트리 (Minimum Spanning Tree) (0) | 2020.04.05 |
너비 우선 탐색 Breadth First Search (BFS) (0) | 2020.04.05 |
깊이 우선 탐색 Depth First Search (DFS) (0) | 2020.04.05 |
반응형
300x250