Bellmana-Forda algoritms
Vikipēdijas raksts
Bellmana-Forda algoritms ir algoritms īsākā ceļa meklēšanai starp doto pārējām virsotnēm svērtos grafos. Atšķirībā no Dijkstras 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.
Satura rādītājs |
[izmainīt šo sadaļu] Algoritma apraksts
Dots svērts grafs G = (V,E) ar šķautņu svaru funkciju w un sākuma virsotni s.
Izveidojams matricas Aij, kas saturēs īsāko ceļu no s uz virsotni i caur j šķautnēm un Pij, 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 As0 = 0. Visu pārējo ceļu sākotnējās vērtības ir .
Algoritms ir sekojošs:
for for to | V | − 1 do for to | V | − 1 do for if Avi > Au,i − 1 + w(u,v) then
Algoritma rezultātā matrica Aij 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
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 | V | − 1 do for return d
Šī algoritma rezultātā masīva d elements d[i] saturēs īsākā ceļa garumu starp virsotnēm s un i.
[izmainīt šo sadaļu] Koda piemēri
Bellmana-Forda algorirma 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; }
[izmainīt šo sadaļu] 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ā.