벨만-포드 (Bellman-Ford)

https://4legs-study.tistory.com/26

벨만포드는 음수간선이 있을때 시작 노드에서 다른 노드까지의 최단거리를 구하는 알고리즘이다.

 

시간복잡도 : O(VE)

 

Edge( [u, v, cost] .... )

 

dist[처음 시작 노드] = 0 나머지 INF

 

for( i  노드 개수 V )

   for( j 간선 개수 E )

      출발 노드 = Edge[j][0]  -> u

      도착 노드 = Edge[j][1]  -> v

      비용 = Edge[E][2]  -> cost

      if ( dist[출발노드] == 무한 ) continue;

      if ( dist[도착노드] > dist[출발노드] + cost )

         dist[도착노드] = dist[출발노드] + cost

         ***********중요***********

         if ( i == V - 1 )  음수 사이클 존재