다익스트라 알고리즘

다익스트라 알고리즘다익스트라 알고리즘은 최단거리를 구하는 알고리즘입니다.다익스트라 알고리즘을 사용하면, 하나의 노드로부터 최단 거리에 있는 다른 노드를 탐색할 수 있습니다.목적지와 가중치를 저장하여 가장 적은 가중치의 경로를 탐색할 수 있으며, 지하철 노선 탐색을 예로 들 수 있습니다.최단 거리를 구할 노드로부터 거리가 입력된 노드를 돌아가면서 더 거리가 짧은 값이 나오면 값을 새로 갱신합니다. 알고리즘 구성 각 노드까지의 거리를 최대값으로 초기화하고, 해당 노드로 이동할 수 있는 더 작은 값일 나올 때 값을 갱신합니다.INF = 1e8distance = [INF] * (n+1) INF는 정수의 최대값이며, 1~n까지의 거리값을 저장하기 위해서 n+1로 초기화합니다. 다음으로는 도착 노드와 가중치 값을 ..