cloge 이야기

Codeforces TopCoder AtCoder SundayCoding Usaco 차근차근 작성할 예정이다.

Floyd-Warshall 플로이드 워셜 알고리즘(흔히 플로이드라고 부른다)은 그래프에서 모든 정점 사이의 최단경로 및 최단거리를 구하는 알고리즘이다. Bellman-Ford, Dijkstra와는 다르게 한 정점으로부터 나머지 모든 정점으로의 최단경로가 아닌 모든 정점 사이의 최단경로를 구할 수 있으며, 음수 사이클이 없는 그래프라면 음수 가중치가 있어도 동작한다. 플로이드 알고리즘은 다음과 같은 점화식에 기반하고 있다. 정점의 수가 V인 그래프에서 플로이드의 점화식 D[i][j] = (정점 i로부터 정점 j로의 최단거리)D[i][j] = min(D[i][j], D[i][k] + D[k][j]) (1

Bellman-Ford 벨만 포드 알고리즘은 음수 가중치가 있고, 음수 사이클이 없는 그래프에서 한 정점으로부터 다른 모든 정점으로의 최단경로 및 거리를 구하는 알고리즘이다. 다익스트라와는 달리 간선에 음수 가중치가 있어도 본래의 시간복잡도를 가지고 동작하며(단, 이 때에는 무방향 그래프가 아니어야 한다), 음수 사이클이 있는 경우는 무한히 사이클을 루프할 수 있다는 점에서 최단경로를 구할 수 없다. 단, 벨만 포드 알고리즘의 장점은 그래프 내에 음수 사이클이 있을 경우, 음수 사이클이 있음은 판단할 수 있다. 벨만 포드는 다음과 같이 동작한다. 시작점을 제외한 모든 정점으로의 최단거리를 무한으로 설정한다(시작점은 0). 이후 다음 수행을 반복한다. 1. 그래프 내에 모든 간선에 대해 2번을 시행한다. ..