생각정리

다익스트라 최단경로 알고리즘은 특정 노드에서 출발해서 다른 노드로 가는 각각의 최단 경로를 모두 구할 수 있는 알고리즘이다. (다만, 이번 글에서는 최단 경로의 거리만 구할 수 있는 알고리즘을 공부한다. 추후에 경로까지 구하는 알고리즘을 업데이트 하도록 하겠습니다) 다익스트라 알고리즘의 조건) 방향/무방향 그래프 모두에서 사용할 수 있으며, 간선 간에 음의 간선이 없어야 함. 음의 간선이 문제에서 주어질 일은 거의 없기 때문에 크게 신경쓰지 않아도 되는 조건임. 실제로 다익스트라 알고리즘은 현실 세계의 gps sw의 기본 알고리즘으로 쓰인다고 한다. 다익스트라 최단 경로 알고리즘의 분류: 그리디 알고리즘으로 분류됨. 즉, 매 순간에 최선(가장 비용이 적은 간선으로 갈 수 있는 노드)의 선택을 하기 때문이..