정용이의 놀이동산

개요 모든 노드에서 모든 노드까지의 최단 경로를 계산하는 알고리즘이다. 알고리즘을 한 번 실행함으로써 모든 노드 간 최단 경로를 계산할 수 있다. 노드 간 거리를 저장하기 위해서 행렬을 사용한다. 행렬의 초깃값은 그래프의 인접 행렬과 같다. 매 라운드마다 각 경로에서 중간 노드로 사용할 노드를 선택하여 거리를 줄여나간다. 구현 3중 반복문으로 쉽게 구현할 수 있다. 가장 바깥쪽은 중간 노드이고, 2번째, 3번째는 경로를 계산할 대상 노드이다. 각 반복문은 그래프의 노드 개수만큼 수행되므로, 노드 개수 n에 대하여 시간복잡도는 O(n^3)이다. Java int INF = 무한, 알고리즘 구현 상 도출될 수 없는 큰 값으로 선언함. int [] [] adj; int [] [] dist; ... void fl..

개요 특정 노드에서 다른 모든 노드 간 최단 경로를 계산하는 알고리즘이다. 벨만-포드 알고리즘보다 효율적이다. 가중치에 음수가 없는 그래프에서만 사용할 수 있다. 벨만 포드처럼 각 노드까지의 거리를 INF로 초기화하고 탐색과정에서 값을 줄인다. 알고리즘의 각 단계에서는 아직 처리하지 않은 노드 중 거리가 가장 작은 노드를 먼저 선택하고, 해당 노드에서 시작하는 모든 간선을 보며 다른 노드까지의 거리를 줄일 수 있다면 줄인다. 음수 가중치가 없다고 전제하여 모든 간선을 단 한 번만 처리한다. 그래서 매우 효율적이다. 각 노드를 처리한 뒤에는 해당 노드까지의 거리가 절대 변하지 않는다. 음수 간선이 존재하면 사용할 수 없다. 구현 효율적인 구현을 위해서는 아직 처리하지 않은 노드 중 거리가 가장 짧은 노드를..

개요 시작 노드에서부터 다른 모든 노드로 가는 최단 경로를 계산하는 알고리즘이다. 길이가 '음수인 사이클'을 포함하지 않는 모든 그래프에서 최단 경로를 구할 수 있다. 음수인 사이클이 그래프에 존재하는지 파악할 수 있다. 구현 각 노드의 초깃값을 설정한다. 시작 노드는 0, 다른 모든 노드는 INF(무한대)이다. n-1번의 라운드를 돌며 매 라운드마다 모든 노드에 걸쳐 경로를 최소화한다. 라운드를 n회 돌아서 n회째에서도 경로 단축이 이뤄지면 음수 사이클이 존재한다고 판단한다. 해당 경로가 음수 사이클을 형성하고, 시작 노드가 INF이면 불가능한 경로의 계산이 진행되므로 주의해서 처리한다. n-1회의 라운드 동안 매회 m개의 간선을 처리하기 때문에 시간복잡도는 O(nm)이다. Java int INF = ..