다익스트라(Dijkstra) 알고리즘이란? 최단 경로를 구하는 알고리즘 중 하나. 단일 소스(하나의 노드)로부터 출발하여 나머지 노드까지 가는 데 최단 경로를 구하는 방법이다. 단, 음수 가중치가 있을 경우에는 사용 불가 알고리즘 동작 방식 다익스트라 알고리즘은 하나의 노드에서 그 노드와 가장 가까운 경로를 fix하는 데서 출발한다. 최소 신장 트리를 찾는 알고리즘 중 prim 알고리즘과 유사한데, 차이점이 있다면 prim은 현재 노드에서 가중치가 적은 노드를 찾는 반면 다익스트라는 시작 노드로부터 가중치가 적은 경로의 노드를 골라야 한다는 데에 있다. 좀 더 쉬운 이해를 위해 예시를 보도록 하자. 0 1 2 3 4 5 6 0 4 2 1 INF INF INF 시작노드 0을 기준으로 나머지 노드로의 가중치..