천천히 빛나는

전보 통로 = 방향성이 있는 간선 일정 시간 = 간선 가중치 핵심 아이디어 : 한 도시에서 다른 도시까지의 최단 거리 문제 N과 M의 범위가 충분히 크기 때문에 우선순위 큐를 활용한 다익스트라 알고리즘을 구현해야 한다. import java.util.*; class Node implements Comparable { private int index; private int distance; public Node(int index, int distance) { this.index = index; this.distance = distance; } public int getIndex() { return this.index; } public int getDistance() { return this.distance..

다익스트라 최단 경로 알고리즘 최단 경로 알고리즘은 가장 짧은 경로를 찾는 알고리즘을 의미한다. 최단 경로 알고리즘 중 다익스트라 알고리즘은 다음과 같은 특징을 가지고 있다. 특정한 노드에서 출발하여 다른 모든 노드로 가는 최단 경로를 계산한다 다익스트라 최단 경로 알고리즘은 음의 간선이 없을 때 사용할 수 있다 다익스트라 최단 경로 알고리즘은 그리디 알고리즘 중 하나이다. 매 상황에서 가장 비용이 적게 드는 노드를 선택하기 때문이다. 다음은 다익스트라 최단 경로 알고리즘의 동작 과정을 간단히 서술한 내용이다. 출발 노드를 설정한다. 최단 거리 테이블을 초기화한다. 이 때, 다른 노드까지의 거리를 무한으로 설정하고 자기 자신까지의 거리는 0으로 설정한다. 방문하지 않은 노드 중에서 최단 거리가 가장 짧은..