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

벨먼-포드 알고리즘(영어: Bellman-Ford algorithm)은 가중 유향 그래프에서 최단 경로 문제를 푸는 알고리즘이다. 이때 변의 가중치는 음수일 수도 있다. 다익스트라 알고리즘은 벨먼-포드 알고리즘과 동일한 작업을 수행하고 실행속도도 더 빠르다. 하지만 다익스트라 알고리즘은 가중치가 음수인 경우는 처리할 수 없으므로, 이런 경우에는 벨먼-포드 알고리즘을 사용한다.

V와 E가 각각 그래프에서 꼭짓점과 변의 개수라고 한다면, 벨먼-포드 알고리즘의 실행시간은 O(VE)이다.

<C코드>

#define INFINITY ((1 << (sizeof(int)*8-2))-1)

typedef struct {
 
 int weight;
}Edge;

void main{
 for(i = 0; i < nodecount; i++) {
  if(i == source) distance[i] = 0;
  else distance[i] = INFINITY;
 }
 for(i = 0; i < nodecount; i++) {
  for(j = 0; j < edgecount; j++) {
   /*
    * Note that INFINITY is actually a finite number in this code, so because of overflow
    * "distance[edges[j].source] + edges[j].weight" can be a very small number,
    * in fact smaller than "distance[edges[j].dest]".
    *
    * One solution is to skip the following if-statement,
    * if "distance[edges[j].source]" == INFINITY
    */
   if(distance[edges[j].dest] > distance[edges[j].source] + edges[j].weight) {
    distance[edges[j].dest] = distance[edges[j].source] + edges[j].weight;
   }
  }
 }
 for(i = 0; i < edgecount; i++) {
  if(distance[edges[i].dest] > distance[edges[i].source] + edges[i].weight) {
   printf("Error occured. Negative edge weight cycles detected");
   break;
  }
 }
 for(i = 0; i < nodecount; i++) {
  printf("The shortest distance between nodes %i and %i is %i\n", source, i, distance[i]);
 }
}