소프트웨어
-
[알고리즘] 다익스트라 알고리즘 (최단 경로 알고리즘) - 이론편IT 발자취.../알고리즘 2019. 7. 24. 21:50
다익스트라 알고리즘은 가장 유명한 그래프 알고리즘 중 하나입니다. 그래프에서 정점끼리의 최단 경로를 찾는 경우가 여러 가지가 있습니다. 1. 하나의 정점에서 다른 하나의 정점까지의 최단 거리 ( Single source and Single destination shortest path ) 2. 하나의 정점에서 다른 모든 정점까지의 최단 거리 ( Single source shortest path ) 3. 하나의 목적지로 가는 모든 최단 거리 ( Single destination shortest path ) 4, 모든 최단 거리 ( All pairs shortest path ) 다익스트라 알고리즘은 여기서 2번째인 시작 정점 s에서 다른 정점들까지의 최단 거리를 계산합니다. 다익스트라 알고리즘은 너비 우선 ..