bellman-ford (1) 썸네일형 리스트형 116. Bellman-Ford 벨만-포드 알고리즘(Bellman-Ford Algorithm)은 한 정점에서 모든 정점까지의 최단 경로를 구하는 알고리즘이다. 이 알고리즘은 그래프의 정점의 수가 $n$, 간선의 수가 $m$일 때 시간복잡도가 $\Theta(nm)$으로 다익스트라 알고리즘에 비해 느리지만, 가중치가 음수인 간선이 존재할 경우에도 최단 경로를 찾을 수 있다. 가중치가 음수인 간선이 존재하는 그래프를 다루기 때문에, 무향 그래프는 사실상 등장하지 않으며 무향 그래프에서의 최단 경로를 다루게 된다. 벨만-포드 알고리즘은 다음과 같은 방식으로 작동한다. 1. 시작 정점은 $k$, 정점 $k$로부터 정점 $i$까지의 최단 거리를 $d_i$라고 한다. 2. 정점 $x$에서 정점 $y$로 가는 가중치 $z$인 간선이 존재할.. 이전 1 다음
