Алгоритъм на Белман-Форд
(Bellman–Ford Algorithm code: c++)

   Алгоритъмът на Белман-Форд се използва за намиране на най-къс път в ориентиран граф от начален връх до всички останали, но теглото на дъгите (ребрата) може да бъде както положително, така и отрицателно число. Алгоритъмът извежда най-краткия път и теглото му. Използва се и за намиране на отрицателни цикли в графа, когато намери отрицателен цикъл алгоритъмът се прекратява и извежда съобщение, че няма решение. По-бавен от алгоритъмът на Дейкстра.
Негови създатели са Лестър Рандолф Форд (1956 г.) - американски математик и мрежов специалист, Ричард Ернест Белман (1958 г.) - американски математик и американския професор по математика и компютърни науки Едуард Форест Мур (1957 г.). Понякога се нарича: Белман-Форд-Мур.
   Алгоритъмът се използва в протоколите за динамична маршрутизизация като: RIP (Routing Information Protocol) и подобрения RIPv2; IGRP и подобрения EIGRP. Използва за маршрутизация на така наречения метод "вектор на разстоянието" (distance vector) – маршрутизаторите обменят информация за топологията на цялата мрежа само със своите съседи.

Приемаме,че имаме претеглен граф G=(V,E) V - брой върхове, Е – брой ребра от типа:

site
site



    За съхранение на стойностите се използва квадратна матрица graph[][3] . Пише се направлението от връх u към връх v с тегло w в примера съответно от точка (връх) 0-- > 1, тегло 7 {0,1,7}, от 0-- > 2 тегло 9 { 0, 2, 9 } и т.н.
Първоначално се инициализират всички стойности с безкрайност максимално допустимата стойност за с++ (INT_MAX) , след това се изчисляват и започват да намаляват. Само първият връх е равен на 0, защото започваме от него.
Създаваме цикъл v-1 (брой на върховете -1) защото търсим най-кратъкия път между тези върхове. Броя на свързващите ги ребра е равен на v-1. На всяка стъпка се включва нов връх, проверява теглото (разстоянието) през всеки връх и съхранява най-малкото рзстояние (релаксационен метод).
Използваме масив dis[] .
graph[j][2] – двойката означава третата колона, а в нея се съдържа дължината на реброто.
gaph[0][2] =7, graph[1][2] =9, graph[2][2] =14 и т.н.
graph[j][1]] – текущо разглеждания връх;
dis[graph[j][1]] - съдържа най-малкото разстояние;
dis[graph[j][0]] – съдържа стойността на разстоянието от предхождащият го връх.
Обяснение:
    Върха който разглеждаме graph[j][1]], съдържа някаква стойност на разтоянието dis[graph[j][1]] до него , проверяваме дали стойността на разстоянието от предхождащият го връх dis[graph[j][0]] + теглото (разстоянието) на реброто graph[j][2] е по-малка от тази в dis[graph[j][1]] и ако е по-малка съответно я запазваме в dis[graph[j][1]] . По този начин запазваме най-малката стойност (най-краткия път). Всичко това се повтаря V-1 пъти.
for (int i = 0; i < V - 1; i++) {
   for (int j = 0; j < E; j++) {
     if (dis[graph[j][0]] + graph[j][2] < dis[graph[j][1]])
      dis[graph[j][1]] = dis[graph[j][0]] + graph[j][2];
      }
   }
Ако добавим този ред (програмата го съдържа като комемтарен) в програмата:
cout<< dis[graph[j][0]]<< "--"<< dis[graph[j][1]]<< ", ";
Ще забележим че стойността (10) от b към c я няма. Това е така защото 10 е по-голямо от 9 и е запаметена 9-ката (7 -->9). Фактически за връх с 9 е най-малкото разстояние.
Седмицата (7 --> 9) е най-малкото разстояние до предхождащият го връх.

Пример: (Bellman–Ford Algorithm)

#include <iostream> //for Code Blocks
#include <limits.h>
using namespace std;
int main()
{
int V = 6; // Number of vertices in graph
int E = 9; // Number of edges in graph
int s=0;
int graph[][3] = { { 0, 1, 7 },
      { 0, 2, 9 },
      { 0, 5, 14 },
      { 1, 2, 10 },
      { 1, 3, 15 },
      { 2, 3, 11 },
      { 2, 5, 2 },
      { 3, 4, 6 },
      { 5, 4, 9} };
// Initialize distance of all vertices as 0.
int dis[V];
for (int i = 0; i < V; i++)
dis[i] = INT_MAX;
// initialize distance of source as 0
dis[s] = 0;
for (int i = 0; i < V - 1; i++) {
for (int j = 0; j < E; j++) {
if (dis[graph[j][0]] + graph[j][2] < dis[graph[j][1]])
dis[graph[j][1]] = dis[graph[j][0]] + graph[j][2];
//cout<< dis[graph[j][0]]<<"--"<< dis[graph[j][1]]<<", ";
}
// cout<< endl;
}
// check for negative-weight cycles.
bool a=1;
for (int i = 0; i < E; i++) {
if ( dis[graph[i][0]]!= INT_MAX && dis[graph[i][0]]
+ graph[i][2] < dis[graph[i][1]])
{cout << "This graph contains negative edge cycle\n";
a=0;}
}
if(a)
{
cout << "Vertex Distance from Source" << endl;
for (int i = 0; i < V; i++)
cout << i << " ---> " << dis[i] << endl;}
return 0;
}



Ако желаем да проверим програмата за отрицателния цикъл на снимката от по-горе.
Трябва да заменим този ред:
      { 1, 3, 15 },
с този:
      { 3, 1, -22 },
т.е. променяме посоката от 3 -->1 и теглото w= -22.






                          Използвана литература:

                 1.   GeeksforGeeks.org
                 2.   Видео урок - руски език.
                 3.   Видео урок - английски език.





Благодаря за вниманието Ви !