Atvērt galveno izvēlni

Belmana—Forda algoritms ir algoritms īsākā ceļa meklēšanai starp doto un pārējām virsotnēm svērtos grafos. Atšķirībā no Deikstras algoritma Belmana—Forda algoritms pieļauj negatīvus šķautņu svarus, bet ir lēnāks, tāpēc parasti tiek izmantots, ja grafā ir šķautnes ar negatīviem svariem.

Algoritma aprakstsLabot

Dots svērts grafs   ar šķautņu svaru funkciju   un sākuma virsotni  .

Izveidojams matricas  , kas saturēs īsāko ceļu no   uz virsotni   caur   šķautnēm un  , kas satur iepriekšējo virsotni šādā ceļā. Matricā   vienīgais ceļš no  , kas satur 0 šķautnes ir tikai līdz pašai   un tā garums ir 0. Tādējādi  . Visu pārējo ceļu sākotnējās vērtības ir  .

Algoritms ir sekojošs:

for  
  for   to  
    do  
 
for   to  
  do for  
    if  
      then  
            

Algoritma rezultātā matrica   satur īsākos ceļus no   uz virsotni   caur dažādiem šķautņu skaitiem  . Pats īsākais ceļš starp   un   ir īsākais no tiem. Kad noskaidrots pats īsākais ceļš caur   šķautnēm, pilnu ceļu masīvā   var iegūt šādi:

while  
  
  
  
return p

Ja nepieciešams noskaidrot tikai īsākā ceļa garumu un nav nepieciešams zināt visu ceļu izmantojams šāds algoritms:

for  
 do  
 
for   to  
 do for  
   
return  

Šī algoritma rezultātā masīva   elements   saturēs īsākā ceļa garumu starp virsotnēm   un  .

Koda piemēriLabot

Belmana—Forda algoritma realizācija C

/* Bellman-Ford Implementation */
 #include <limits.h>
 #include <stdio.h>
 #include <stdlib.h>
 
 /* Let INFINITY be an integer value not likely to be
   confused with a real weight, even a negative one. */
 #define INFINITY ((cin << 14)-1)
 
 typedef struct {
    int source;
    int dest;
    int weight;
 } Edge;
 
 void BellmanFord(Edge edges[], int edgecount, int nodecount, int source)
 {
    int *distance = (int*) malloc(nodecount * sizeof(*distance));
    int i, j;
    for (i=0; i < nodecount; i++)
      distance[i] = INFINITY;
 
    /* The source node distance is set to zero. */
    distance[source] = 0;
 
    for (i=0; i < nodecount; i++) {
        for (j=0; j < edgecount; j++) {
            if (distance[edges[j].source] != INFINITY) {
                int new_distance = distance[edges[j].source] + edges[j].weight;
 
                if (new_distance < distance[edges[j].dest])
                  distance[edges[j].dest] = new_distance;
            }
        }
    }
 
    for (i=0; i < edgecount; i++) {
        if (distance[edges[i].dest] > distance[edges[i].source] + edges[i].weight) {
            puts("Negative edge weight cycles detected!");
            free(distance);
            return;
        }
    }
 
    for (i=0; i < nodecount; i++) {
        printf("The shortest distance between nodes %d and %d is %d\n",
            source, i, distance[i]);
    }
    free(distance);
    return;
 }
 
 int main(void)
 {
    /* This test case should produce the distances 2, 4, 7, -2, and 0. */
    Edge edges[10] = {{0,1, 5}, {0,2, 8}, {0,3, -4}, {1,0, -2},
                      {2,1, -3}, {2,3, 9}, {3,1, 7}, {3,4, 2},
                      {4,0, 6}, {4,2, 7}};
 
    BellmanFord(edges, 10, 5, 4);
 
    return 0;
 }

Pielietojums maršrutēšanāLabot

Distance-vector maršrutēšanas protokoli, piemēram, RIP izmanto dalīto (distributed) Belmana—Forda algoritmu. Par dalīto to sauc tāpēc, ka tajā iesaistīti vairāki maršrutētāju vienā autonomajā sistēmā. Algoritma realizācija ir šāda:

  • katrs mezgls aprēķina attālumus starp sevi un citiem mezgliem un saglabā rezultātus tabulā;
  • tabula tiek izsūtīta citiem mezgliem;
  • saņemot tabulu, mezgls aprēķina īsākos maršrutus starp sevi un citiem mezgliem un izdara izmaiņas tabulā.

Ārējās saitesLabot