bellman_ford(1)

소개

bellmanford 에대해서, 벨만포드에 관한 설명, c로 구현한 알고리즘

목차

1. Dijskstra (이하 딕스트라) 알고리즘
2. Bellmann Ford

본문내용

Bellman Ford & Dijkstra Algorithm

1. Dijskstra (이하 딕스트라) 알고리즘

Dijskstra 알고리즘은 각각의 점 v에 대해 s에서 v까지의 최단 거리 d[v]를 저장하면서 작동한다. 알고리즘의 시작 시에 이 값은 s에 대해서는 0이고, (d[s]=0) 다른 모든 점에 대해서는 무한대(∞) 값으로 놓아 다른 점에 대해서는 아직 최단 경로를 모른다는 사실을 표시한다. 알고리즘이 종료되었을 때 d[v]는 s에서 v까지의 최단 경로의 거리를 나타내게 되고, 만약 경로가 존재하지 않으면 거리는 여전히 무한대로 남는다.
Dijskstra 알고리즘은 간선 경감(edge relaxation)이라고 불리는 기본 연산을 바탕으로 한다. s에서 u까지의 최단 경로(d[u])를 이미 알고 있고, u에서 v까지의 링크 (u, v)가 존재할 때, s에서 v까지의 최단경로는 u까지의 최단경로에 링크 (u, v)를 연장함으로써 얻을 수 있다. 이 경로의 비용은 d[u]+w(u, v)가 되며, 이 비용이 현재의 d[v] 값보다 낮으면 d[v]를 새로운 값으로 바꾼다.
경감 연산은 모든 간선 (u, v)에 대해 한번씩 경감이 적용되어 모든 d[v]가 최단 경로의 비용을 나타내게 되었을 때 끝난다.
알고리즘은 과정이 끝날 때까지 점의 집합 S와 Q를 저장한다. S는 d[v]가 최단 경로의 비용임이 이미 알려진 점 v의 집합이고 Q는 나머지 점들의 집합을 가리킨다. S는 공집합에서 시작하여 매 단계마다 Q에서 S로 점들이 하나씩 옮겨 오며, 이때 옮겨 오는 점들은 d[u]가 가장 낮은 값을 갖는 점 u로 정해진다. u가 S로 옮겨 오면, 알고리즘은 u에서 시작하는 모든 간선에 대해 경감 연산을 행한다.

참고자료

· 없음