Belmana—Forda algoritms

Vikipēdijas lapa
Pārlēkt uz: navigācija, meklēt

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 apraksts[labot šo sadaļu | labot pirmkodu]

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[labot šo sadaļu | labot pirmkodu]

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 šo sadaļu | labot pirmkodu]

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 saites[labot šo sadaļu | labot pirmkodu]