Bellman-Ford algorithm computes single-source shortest paths in a weighted graph (where some of the edge weights may be negative). Dijkstra's algorithm accomplishes the same problem with a lower running time, but requires edges to be non-negative. Thus, Bellman-Ford is usually used only when there are negative edge weights.
Bellman Ford runs in O(VE) time, where V and E are the number of vertices and edges. Hi Mama
Here is a sample algorithm of Bellman-Ford
BF(G,w,s) // G = Graph, w = weight, s=source
Determine Single Source(G,s);
set Distance(s) = 0; Predecessor(s) = nil;
for each vertex v in G other than s,
set Distance(v) = infinity, Predecessor(v) = nil;
for i <- 1 to |V(G)| - 1 do //|V(G)| Number of vertices in the graph
for each edge (u,v) in G do
if Distance(v) > Distance(u) + w(u,v) then
set Distance(v) = Distance(u) + w(u,v), Predecessor(v) = u;
for each edge (u,r) in G do
if Distance(r) > Distance(u) + w(u,r);
return false; //This means that the graph contains a cycle of negative weight
//and the shortest paths are not well defined
return true; //Lengths of shortest paths are in Distance array
Proof of correctness
The correctness of the algorithm can be shown by induction. The precise statement shown by induction is:
Lemma. After i repetitions of for cycle:
- If Distance(u) is not infinity, it is equal to the length of some path from s to u;
- If there is a path from s to u with at most i edges, then Distance(u) is at most the length of the shortest path from s to u with at most i edges.
Proof. For the base case of induction, consider i=0 and the moment before for cycle is executed for the first time. Then, for vertex s, Distance(s)=0 which is correct. For other vertices, Distance(u)=infinity which is also correct because there is no path from s to u with 0 edges.
For the inductive case, we first prove the first part. Consider a moment when Distance is updated by Distance(v) = Distance(u) + w(u,v) step. By inductive assumption, Distance(u) is the length of some path from s to u. Then, Distance(u) + w(u,v) is the length of the path from s to v that first goes from s to u and then from u to v.
For the second part, consider the shortest path from s to u with at most i edges. Let v be the last vertex before u on this path. Then, the part of the path from s to v is the shortest path between s to v with i-1 edges. By inductive assumption, Distance(v) after i-1 cycles is at most the length of this path. Therefore, Distance(v)+w(u,v) is at most the length of the path from s to u. In the ith cycle, Distance(u) gets compared with Distance(v)+w(u,v) and set equal to it, if Distance(v)+w(u,v) was smaller. Therefore, after i cycles Distance(u) is at most the length of the path from s to u.
End of proof.
The correctness of the algorithm follows from the lemma together with the observation that shortest path between any two vertices must contain at most V(G)-1 edges. (If a path contained more than V(G)-1 edges, it must contain some vertex v twice. Then, it can be shortened by removing the part between the first occurrence of v and the second occurrence. This means that it was not the shortest path.)
Implementations
/****************************************/
/*Author: Chiam Jia-Han a.k.a JellyWorld*/
/*Copyright: This code is distributed */
/*unconditionally. You may use it */
/*without author acknowledgement. */
/****************************************/
#define INFINITY ((int) pow(2, sizeof(int)*8-2)-1)
typedef struct
{
int source;
int dest;
int weight;
}Edge;
void BellmanFord(Edge edges[], size_t edgecount, size_t nodecount, size_t source)
{
int* distance = (int*) malloc(nodecount*sizeof(int));
for(int i = 0; i < nodecount; i++)
{
if(i == source) distance[i] = 0;
else distance[i] = INFINITY;
}
for(int i = 0; i < nodecount; i++)
{
for(int j = 0; j < edgecount; j++)
{
if(distance[edges[j].dest] > distance[edges[j].source] + edges[j].weight)
{
distance[edges[j].dest] = distance[edges[j].source] + edges[j].weight;
}
}
}
for(int i = 0; i < edgecount; i++)
{
if(distance[edges[i].dest] > distance[edges[i].source] + edges[i].weight)
{
printf("Error occurred. Negative edge weight cycles detected");
break;
}
}
for(int i = 0; i < nodecount; i++)
{
printf("The shortest distance between nodes %i and %i is %i", source, i, distance[i]);
}
}
Program written by Chiam Jia-Han a.k.a JellyWorld
segment .model
segment .stack
segment .data
INFINITY dd 1
format_string1 db "Error occurred. Negative edge weight cycles detected", 0
format_string2 db "The shortest distance between nodes %i and %i is %i", 0
extern _printf
extern _malloc
extern _exit
segment .bss
distance resd 1
segment .text
global _BellmanFord
_BellmanFord: ;Function takes in same parameters as C function above
mov eax, INFINITY ;Load Infinity into register eax
shl eax, 29 ;Shift register 29 bits left
mov dword [INFINITY], eax ;Define INFINITY as 2^29
push ebp ;Store ebp register in stack
mov ebp, esp ;Fix ebp to stack pointer
mov eax, [ebp+16] ;Store third parameter in eax
shl eax, 2 ;Bitshift it
push eax ;Push it onto stack as parameter for malloc
call _malloc ;Call malloc
pop edx ;Pop it back off the stack
shl eax, 2 ;Multiply return value by 4
mov dword [distance], eax ;Store pointer returned in distance
mov ecx, [ebp+16] ;Store nodecount in ecx
sub ecx, 1 ;Subtract one
loopend1: ;Start of loop
shl ecx, 2 ;Multiply by 4
lea eax, [distance+ecx] ;Store pointer in eax
shr ecx, 2 ;Divide by 4
cmp ecx, [ebp+20] ;Check for equality with source node
jnz dinf ;Jump to"else" clause if equality not detected
mov dword [eax], 0 ;Change value at pointer to 0
jmp end1 ;Go to end of loop
dinf: ;Else Clause
mov edx, [INFINITY] ;Store value in edx
mov dword [eax], edx ;Set value to infinity
end1: ;End of loop label
loop loopend1 ;Return to front of loop
mov ecx, [ebp+16] ;Reload nodecount into register eax
dec ecx ;Decrement ecx
loopend2: ;Start of loop label
mov ebx, 0 ;Set ebx to 0
innerloop1: ;Inner Loop label
mov edx, [ebp+12] ;Store edgecount variable in edx
cmp edx, ebx ;Compare for equality
jz end2 ;Skip to loop end if they are equal
mov eax, ebx ;Store ebx in eax
add eax, edx ;Add the registers
mov edx, [ebp+8] ;Load edge array into edx
push edx ;Store edx on the stack temporarily (mul instruction modifies edx)
push 12 ;Push 12 onto the stack
mul dword [esp] ;Multiply 12 with eax
add esp, 4 ;Pop 12 off the stack
pop edx ;Push it back off the stack
mov edx, eax ;Set edx to eax
add edx, 4 ;Point to dest member
mov eax, [edx] ;Load into eax
shl eax, 2 ;Multiple by 4
lea eax, [distance+eax] ;Access member of distance array
push dword [eax] ;Push eax
push eax ;Push eax pointer
sub edx, 4 ;Point edx to source member
mov eax, [edx] ;Store value at edx in eax
shl eax, 2 ;Multiply by 4
lea eax, [distance+eax] ;Access member of distance array
push dword [eax] ;Store on stack
push eax ;Push eax onto stack
add edx, 8 ;Point to weight member
push dword [edx] ;Push onto stack
push edx ;Push edx onto stack
mov eax, [esp+4] ;Take value off top of stack and store in eax
add eax, [esp+12] ;Add top two dwords on stack
cmp eax, [esp+20] ;Compare with first
jz after ;Jump to label after if eax = [esp+20]
jns label1 ;Looks complicated
jmp label2 ;but is basically
label1: ;the same as
jo after ;the C/C++ equivalent of
jmp start2 ;if(eax < [esp+20])
label2: ;{
jno after ; //Bla bla bla
start2: ;}
mov edx, [esp+16] ;Edx = [esp+16]
mov dword [edx], eax ;Set [edx] = eax
after: ;Label after if clause
add esp, 24 ;Push EVERYTHING off the stack
inc ebx ;Increment loop counter
jmp innerloop1 ;Jump to start of inner loop
end2: ;End of loop label
cmp ecx, 0 ;Check if 0
jz outside ;Break loop
dec ecx ;Decrement ecx
jmp loopend2 ;Jump to start of outer loop
outside:
mov eax, 0 ;Reset the registers
mov ebx, 0 ;Reset the registers
mov ecx, 0 ;Reset the registers
mov edx, 0 ;Reset the registers
mov ecx, [ebp+12] ;Load nodecount parameter
dec ecx ;Decrement ecx
loopstart2: ;Start of loop
mov edx, [ebp+8] ;Load into edx
add edx, ecx ;Add edx and ecx
push edx ;Temporarily store edx on stack
push 12 ;Store multiplier on stack
mov eax, edx ;Store edx in eax
mul dword [esp] ;Multiply eax (ie. edx) by 12
add esp, 4 ;Pop off 12
pop edx ;Pop edx back off
mov edx, eax ;Move the result in eax into edx
add edx, 4 ;Add 4 to access dest member
mov eax, [edx] ;Move value of dest member into eax
shl eax, 2 ;Multiply by 4
add eax, distance ;Make it point to index in distance array
push dword [eax] ;Store on stack
sub edx, 4 ;Access source member
mov eax, [edx] ;Move value of source member into eax
shl eax, 2 ;Multiply by 4
add eax, distance ;Make it point to index in distance array
push dword [eax] ;Store value on stack
add edx, 8 ;Point to weight member
push dword [edx] ;Push onto stack
mov eax, [esp] ;Store in eax
add eax, [esp+4] ;Add to previous stack value
cmp eax, [esp+8] ;Compare two values
jz cafter ;Jump to label after if eax = [esp+20]
jns clabel1 ;Looks complicated
jmp clabel2 ;but is basically
clabel1: ;the same as
jo cafter ;the C/C++ equivalent of
jmp cstart2 ;if(eax < [esp+8])
clabel2: ;{
jno cafter ; //Bla bla bla
cstart2: ;}
add esp, 8 ;Pop those values off
push format_string1 ;Push format string onto the stack
call _printf ;Call printf()
add esp, 4 ;Pop format string off
push 1 ;Push one onto stack
call _exit ;Quit program
cafter: ;cafter label
cmp ecx, 0 ;Check if ecx is 0
jz exitloop ;If it is, break the loop
dec ecx ;Decrement ecx
jmp loopstart2 ;Jump to the front
exitloop:
mov eax, 0 ;Reset the registers
mov ebx, 0 ;Reset the registers
mov ecx, 0 ;Reset the registers
mov edx, 0 ;Reset the registers
loopstart3: ;Loop label
mov ecx, eax ;Move ecx into eax
shl eax, 2 ;Multiply by 4
add eax, distance ;Add distance to eax
push dword [eax] ;Push onto stack
push ecx ;Push onto stack
push dword [ebp+20] ;Push source onto stack
push format_string2 ;Push format string onto stack
call _printf ;Call printf
add esp, 12 ;Pop parameters off the stack
inc ecx ;Increment ecx
cmp ecx, [ebp+16] ;Compare with nodecount
jz outside3 ;Quit if equal
jnz loopstart3 ;Loop to front
outside3:
xor eax,eax ;Normal, no error, return value
ret ;Return
Applications in routing
A distributed variant of Bellman-Ford algorithm is used in the Routing Information Protocol (RIP). The algorithm is distributed because it involves a number of nodes (routers) within an Autonomous system, a collection of IP networks typically owned by an ISP. It consists of the following steps:
- Each node calculates the distances between itself and all other nodes within the AS and stores this information as a table.
- Each node sends its table to all neighbouring nodes.
- When a node receives distance tables from its neighbours, it calculates the shortest routes to all other nodes and updates its own table to reflect any changes.
The main disadvantages of Bellman-Ford algorithm in this setting are
- Does not scale well
- Changes in network topology are not reflected quickly since updates are spread node-by-node.
- Counting to infinity
See also: List of algorithms