Bellmana-Forda algoritms

Bellmana-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 Bellmana-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 apraksts

Dots svērts grafs $G = (V, E)$ ar šķautņu svaru funkciju $w$ un sākuma virsotni $s$.

Izveidojams matricas $A_{ij}$, kas saturēs īsāko ceļu no $s$ uz virsotni $i$ caur $j$ šķautnēm un $P_{ij}$, kas satur iepriekšējo virsotni šādā ceļā. Matricā $A$ vienīgais ceļš no $s$, kas satur 0 šķautnes ir tikai līdz pašai $s$ un tā garums ir 0. Tādējādi $A_{s0} = 0$. Visu pārējo ceļu sākotnējās vērtības ir $+\infty$.

Algoritms ir sekojošs:

for $v \in V$
  for $i \gets 0$ to $|V| - 1$
    do $A_{vi} \gets +\infty$
$A_{s0} \gets 0$
for $i \gets 1$ to $|V| - 1$
  do for $(u, v) \in E$
    if $A_{vi} > A_{u, i-1} + w(u, v)$
      then $A_{vi} \gets A_{u, i-1} + w(u, v)$
           $P_{vi} \gets u$

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

while $j > 0$
 $p[j] \gets i$
 $i \gets P_{ij}$
 $j \gets j - 1$
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 $v \in V$
 do $d[v] \gets +\infty$
$d[s] \gets 0$
for $i \gets 1$ to $|V| - 1$
 do for $(u, v) \in E$
  $d[v] \gets \min(d[v], d[u] + w(u, v))$
return $d$

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

Koda piemēri

Bellmana-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ā

Distance-vector maršrutēšanas protokoli, piemēram, RIP izmanto dalīto (distributed) Bellmana-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 saites

• Interaktīva grafu teotijas algoritmu demonstrācija (Java)