[알고리즘] Bellman-Ford 알고리즘

 노드들을 반복해서 bellman-ford를 만들 수 있는 것에서 아무 에지나 릴렉스하지 않고 특별한 조건을 만족하는 relax에만 만족합니다. 그것이 dijkstra 알고리즘입니다.

 

초기화는 똑같습니다. 출발 노드만 distance estimator가 0이고 출발을 해서 첫번째 round에서 relax 할 때 distance 값이 최소인 노드를 찾습니다. 최소인 노드로부터 나가는 edge들만 relax합니다. 두번째 round에서는 다시 distance가 최소인 애를 찾는데 dijkstra 알고리즘은 이미 이전 round에서 선택이 되어서 edge들을 두번 선택할 필요는 없습니다.

 

이 노드의 최단 경로는 현재 노드가 가지고 있는 d[s] = 델타[s,s]입니다.

dijkstra는 s만 0이고 나머지는 무한대이므로 s가 선정됩니다.

 

v에서 되므로 처음 나가는 노드들은 400 200 100 50이 될 것입니다. 

 

• 음수 가중치가 없다고 가정
• s로부터의 최단 경로의 길이ㅡㄹ 이미 알아낸 노드들의 집합 s를 유지. 맨 처음엔 S= {s}.
• Loop invariant:
  • u S안에 포함되지 않는 각 노드 u에 대해서 d(u)는 이미 S에 속한 노드들만 거쳐서 s로부터 u까지 가는 최단경로의 길이

모든 노드들에 대해서 distance 무한대, 파이는 NIL, 세팅한 다음 진행해줍니다. 노드를 선택해서 하나씩 선택해서 모든 노드들이 집합에 선택되면 알고리즘을 종료합니다. 

 

모든 노드들이 포함될 떄까지 반복하는데 최소인 노드를 u라고 한다면 d[u]는 델타(s,u)이며 출발점으로부터 노드로 가는 최단 경로로 가는 것이며 이 u는 s에 포함시키며 다음 노드들의 distance 또한 갱신해야하는데 금방 노드가 u라면 edge들에 대해 나가는 것에 relax를 해주어야 합니다.

 

각각의 노드 v에 대해서 s에 속하지 않는 노드 v에 대해서는 relax 현재 distance가 u의 distance + w(u,v) 그 값으로 갱신하고 파이가 u가 되고 그 노드들에 대해서 relax하면 된다는 것이고 dijkstra의 알고리즘입니다.

 

시간복잡도는 초기화하는 부분은 o(n)이고 while문은 정확히 n번 반복할 것입니다. 모든 노드들이 속해야 하니 n번 반복되는데  d[u]가 최소가 되는 값을 찾는 것은 o(n)을 넘진 않습니다. 다음 for문이 들어가는데 for문의 반복 횟수가 인접한 각각의 노드 u의 degreement 어떤 노드의 degree는 n-1번을 넘지 않기에 for문의 반복 횟수는 o(n)이라고 할 수 있습니다. 

 

전체 시간복잡도는 while이 n번돌고 for문이 n번 o(n)이므로 시간복잡도는 o(n^2)입니다. 

 

시간복잡도

• prim의 알고리즘과 동일함
• 우선순위 큐를 사용하지 않고 단순하게 구현할 경우 o(n^2)
• 이진힙을 우선순위 큐로 사용할 경우 o(nlogn+mlogn)
• fibonacci heap 사용하면 o(nlogn+m)에 구현 가능