개요 최소 이동 비용을 구하는 머리 아픈 알고리즘으로 특정 노드에서 연결된 다른 노드로 이동하며 비용을 구한다 네트워크에서 라우터나 게임에서 길 찾기 알고리즘 등, 여러 곳에서 사용되는 유명한 알고리즘이다. 에츠허르 다익스트라가 고안했다.
개인적인 생각이지만 막상 구현해 보면 BFS를 통해 각 정점까지의 거리를 구하는 것과 크게 다를 것 없는 것 같다. 아무래도 그래프를 기반으로 하니 그런 것 같고, 가장 큰 차이는 비용을 갱신한다는 점이다.
알고리즘 자체는 이중 배열로도 구현 가능하지만, 효율성을 우선하여 웬만하면 우선순위 큐를 함께 사용한다. 코드 구현 간선 (Edge)를 구조체로 구현하고 우선순위 큐를 사용하기 위해 연산자 오버 로딩도 함께 구현해 줬다. struct way { int idx; int dis; bool operator()(way& a, way& b) { return a.dis > b.dis; } }; 각 정점별로 비용을 저장할 int 배열, cost와 그래프를 ...
원문 링크 : 다익스트라 (Dijkstra)
