🍀 Knowledge/알고리즘
[알고리즘] 최단 경로 알고리즘 - Dijkstra, Bellman-Ford, Floyd-Warshall 알고리즘
Dijkstra 알고리즘 최단 경로(Shortest Path) 찾기는 주어진 가중치 그래프에서 출발점에서 도착점까지의 최단 경로를 찾는 알고리즘이다. 이 최단 경로를 찾는 알고리즘 중 많이 사용하는 것이 바로 Dijkstra 알고리즘이다. Dijkstra 알고리즘은 출발점에서 각 정점까지의 최단 거리 및 경로를 구하는 알고리즘으로 이전에 배웠던 Prim의 MST 알고리즘과 유사하다. 어떤 점이 차이가 있냐하면, Prim 알고리즘은 임의의 점에서부터 시작을 하지만, Dijkstra 알고리즘은 출발 지점이 있다. 또한 Prim 알고리즘에서는 배열 D에 간선의 가중치를 저장했지만, Dijkstra 알고리즘은 배열 D에 출발점에서 각 정점까지의 거리를 저장한다. Prim 알고리즘에 관해 궁금하다면, 아래 포스팅..
