목록플로이드워셜 (2)
천천히 빛나는
전보 통로 = 방향성이 있는 간선 일정 시간 = 간선 가중치 핵심 아이디어 : 한 도시에서 다른 도시까지의 최단 거리 문제 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..
플로이드 워셜 알고리즘 모든 노드에서 다른 모든 노드까지의 최단 경로를 모두 계산한다. 플로이드 워셜은 다익스트라 알고리즘과 마찬가지로 단계별로 거쳐가는 노드를 기준으로 알고리즘을 수행한다. 다익스트라 알고리즘이란? https://shine-slowly.tistory.com/85 알고리즘 : 다익스트라(Dijkstra) 최단 경로 알고리즘 (Java로 구현) 다익스트라 최단 경로 알고리즘 최단 경로 알고리즘은 가장 짧은 경로를 찾는 알고리즘을 의미한다. 최단 경로 알고리즘 중 다익스트라 알고리즘은 다음과 같은 특징을 가지고 있다. 특정한 노 shine-slowly.tistory.com 다익스트라 알고리즘과 다른게 매 단계마다 방문하지 않은 노드 중에서 최단 거리를 갖는 노드를 찾는 과정이 필요하지 않다...