벨먼-포드 알고리즘(Bellman-Ford algorithm)

벨먼-포드 알고리즘(Bellman-Ford algorithm)

- 가중치 그래프에서 시작점에서 목표점까지의 최단 경로를 찾는 알고리즘이다.

- 다익스트라 알고리즘과 흡사하지만, 다익스트라보다 조금 더 느리다.

 + 음수 가중치를 판단할 수 없는 다익스트라에 비해 조금 더 유연하다.

동작 원리

(1) 시작점을 제외한 모든 점의 거리를 무한으로 초기화한다. ( 시작점의 거리는 0 )

(2) 모든 점의 수 만큼 반복적으로 가중치가 있는 모든 선분을 검사한다.

(3) 갱신 가능한 거리가 있으면 최단거리를 갱신한다.

(4) 음수 싸이클이 있는지 검사하고, 검사 결과를 반환한다.

[ Fig. 1 ] process of bellmanford. cite : introduction to algorithm 3/E

함수 설명

bellmanford() : 알고리즘의 메인 부분으로 동작원리 (1), (2), (4)의 기능을 수행한다.

relax() : 최단 거리를 갱신하는 부분으로 동작원리 (3)에 해당한다.

함수 구현

 

 

#include <stdio.h> #define MAX     10 #define EDGEMAX 20 #define UNDEF   -1 #define INF     9999 struct edge{     int s;     int d;     int w; }e[EDGEMAX]; int d[MAX]; int pre[MAX]; int bellmanford( int, int, int); void relax( struct edge); int main( void) {     int t, tc;     int i;     int from, to;     int vc, ec, s;     freopen("input.txt", "r", stdin);     scanf("%d", &tc);     for( t = 0 ; t < tc ; t ++)     {         // input the number of vertices         // and the position of starting point.         scanf("%d%d", &vc, &s);         // input the number of edges.         scanf("%d", &ec);         for( i = 0 ; i < ec ; i ++)         {             // input each vertices that you want to input the weight.             // input the weight between S.P and D.             scanf("%d%d", &from, &to);             e[i].s  = from - 1;             e[i].d  = to - 1;             scanf("%d", &e[i].w);         }         // if have detected error.         if( bellmanford( s-1, vc, ec))         {             printf("Error occured. Negative edge weight cycles detected\n");         }         for( i = 0 ; i < vc ; i ++)         {             printf("Vertex %d. %d\n", i+1, d[i]);         }     }     return 0; } /* Bellmanford algorithm It is similar to Dijkstra. there is some differences. - this algorithm can find negative. but it is slower than Dijkstra. */ int bellmanford( int s, int vc, int ec) {     int i, j;     // initialize the distances and previous routes.     for( i = 0 ; i < vc ; i ++)     {         d[i]    = INF;         pre[i]  = UNDEF;     }     // set the distance of starting point.     d[s]    = 0;     // repeat as much as the number of vertices.     for( i = 0 ; i < vc-1 ; i ++)     {         // examine all edges.         for( j = 0 ; j < ec ; j ++)         {             relax( e[j]);         }     }     // to detect negative cycles,     // examine all edges again.     for( i = 0 ; i < ec ; i ++)     {         // if error occur.         if( d[e[i].d] > d[e[i].s] + e[i].w)         {             return -1;         }     }     return 0; } /* relax( int, int) this function updates distances between U and V. */ void relax( struct edge v) {     // if current distance is bigger than new distance.     if( d[v.d] > d[v.s] + v.w)     {         d[v.d]      = d[v.s] + v.w;         pre[v.d]    = v.s;     } }

 

 

실행 결과

Fig. 1의 그림을 토대로 실행한 결과 다음과 같다.

음수 사이클이 없기 때문에 아무런 에러가 발견되지 않았다.

임의로, 5번 꼭지점에 음수 사이클을 만들어서 실행한 결과는 다음과 같다.

음수 사이클이 발견되었다고 메시지를 출력한다.