다익스트라 알고리즘이란?
다이나믹 프로그래밍(DP,Dynamic Programming)을 활용한 대표적인 최단 경로 탐색 알고리즘으로, 음의 가중치가 없는 그래프의 한 정점에서 모든 정점까지의 최단거리를 각각 구하는 알고리즘이다.
다익스트라의 구현
- 해당 정점까지의 최단 거리를 저장
- 정점을 방문했는 지 저장
'Python > 최단경로' 카테고리의 다른 글
| [Algorithm] 프로그래머스 14938 서강그라운드 | 파이썬 (다익스트라) (1) | 2024.09.06 |
|---|---|
| [Algorithm] 프로그래머스 1238 파티 | 파이썬 (다익스트라) (0) | 2024.09.05 |
| [Algorithm] 프로그래머스 1753 최단경로 | 파이썬 (다익스트라) (0) | 2024.09.05 |
| [Algorithm] 벨만-포드 알고리즘(Bellman-Ford algorithm) (0) | 2024.01.05 |
| [Algorithm] 플로이드-워셜 알고리즘(Floyd-Warshall Algorithm) (1) | 2024.01.05 |
댓글