BOBO's Note

Dijkstra's Algorithm 다익스트라 알고리즘은 한 vertex에서 다른 vertex들로 가는 최단 경로를 구하는 알고리즘이다. cf) A* 알고리즘: 다익스트라에 휴리스틱을 도입해 더 빠르다. 다익스트라 알고리즘은 한 가지 가정 하에 적용할 수 있다. 모든 edge의 가중치가 양수이다. 다익스트라 알고리즘에서 출발점으로부터 가까운 vertex부터 방문하는 이유는 해당 vertex까지의 거리가 더이상 업데이트될 수 없기 때문이다. 이때 음수 가중치가 허용된다면 이미 방문한 vertex일지라도 더 작은 값으로 업데이트될 수 있어 다익스트라 알고리즘이 제대로 작동하지 않는다. 다익스트라 알고리즘은 distance 벡터와 visited 벡터를 갖는다. distance 벡터는 inf로, visited..