다익스트라 알고리즘 (Dijkstra's algorithm) 특정 노드에서 출발해 다른 모든 노드로 가는 최단 경로를 구해주는 알고리즘 다익스트라 알고리즘은 음의 간선이 있는 그래프에서는 사용이 불가능하지만 현실 세계에서는 음의 간선이 존재하지 않으므로 현실 세계에서 쓰기에 적합하다. 다익스트라는 그리디로 분류된다. 매상황 가장 비용이 적은 노드를 선택해 임의의 과정을 반복해준다. 동작 과정 1. 출발 노드를 설정해준다. 2. 최단거리 테이블을 초기화한다. 3. 방문하지 않은 노드 중 최단거리가 가장 짧은 노드를 선택한다. 4. 해당 노드에서 다른 노드로 가는 최단 거리 테이블을 갱신해준다. 5. 3번과 4번을 반복한다. 알고리즘 사례 위와 같은 그래프가 있다고 하자 출발점은 0이다. 이제부터 0번 노드..