Dev On The Coffee Dev On The Coffee

# 벨만 포드 알고리즘 (Bellman-Ford Algorithm) 1. 벨만 포드 알고리즘 개요 벨만 포드 알고리즘(Bellman-Ford Algorithm)은 다익스트라 알고리즘과 거의 유사하다. 다만, 다익스트라 알고리즘과 달리 벨만 포드 알고리즘은 음의 값을 가지는 간선을 포함하여 알고리즘을 수행할 수 있다는 점이 큰 차이점이다. 위와 같이 5번 노드에서 2번 노드로 가는 간선의 비용이 -2인 그래프가 있다. 이 경우, 음의 간선이 존재하지만 얼마든지 오른쪽 테이블처럼 최소 비용을 계산해낼 수 있다. 그러나 음의 간선의 순환이 포함되어 있는 경우 최소 비용을 계산하는데 어려움이 생길 수 있다. 위 그래프는 음의 간선 비용이 -4인데 이 값이 상당히 작기 때문에 '3번 노드 -> 5번 노드 -> 2..

# 플로이드 워셜 알고리즘 (Floyd-Warshall Algorithm) 1. 플로이드 워셜 알고리즘 개요 플로이드 워셜 알고리즘(Floyd-Warshall Algorithm)은 최단 경로를 구하는 또 하나의 대표적 알고리즘이다. 다만, 다익스트라 알고리즘이 '한 지점에서 다른 특정 지점까지의 최단 경로를 구하는 경우'에 사용한다면, 플로이드 워셜 알고리즘은 '모든 지점에서 다른 모든 지점까지의 최단 경로를 모두 구하는 경우'에 사용한다. 플로이드 워셜은 다익스트라처럼 단계별로 거쳐가는 노드를 기준으로 알고리즘을 수행하지만 매 단계마다 방문하지 않은 노드 중에 최단 거리를 갖는 노드를 찾는 과정이 없다. 그리고 2차원 테이블에 모든 노드의 최단 거리 정보를 저장하며, 이를 점화식을 통해 갱신한다는 점에..