|
|
Bellman-ford AlgorithmBellman-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. 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) distancei = 0; else distancei = INFINITY; } for(int i = 0; i < nodecount; i++) { for(int j = 0; j < edgecount; j++) { if(distanceedges[j.dest] > distanceedges[j.source] + edgesj.weight) { distanceedges[j.dest] = distanceedges[j.source] + edgesj.weight; } } } for(int i = 0; i < edgecount; i++) { if(distanceedges[i.dest] > distanceedges[i.source] + edgesi.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, distancei); } } 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
|
 |