Алгоритм Форда-Беллмана. Реализация на С++

Алгоритм Форда-Беллмана применяется для нахождения кратчайшего пути от одной вершины до всех остальных во взвешенном графе.
Главное его преимущество перед алгоритмом Дейкстры в том, что он способен работать с отрицательными весами, НО имеет главный минус в производительности-работает за O(|V| × |E|), так как инициализация матрицы занимает время O(V) и на каждый проход надо V(E).

Случай 1: Граф без отрицательного цикла.
Для начала реализуем простейшую реализацию для графа без отрицательных весов, этот случай будет рассмотрен в другой статье. Увы, эта реализация будет бесконечно делать релаксацию, так как при суммарном весе цикла меньше 0, при обходе сколько угодно раз, длина кратчайшего пути будет выражаться большим по модулю отрицательным числом.

Итак, все действующие лица:

• Переменная numOfVertices обозначает количество вершин в графе.
• Переменная start нужна для обозначения номера начальной вершины.
• Вектор расстояний d[numOfVertices] который имеет размер такой же как и количество вершин в графе (numOfVertices), он хранит в себе ВСЕ КРАТЧАЙШИЕ РАССТОЯНИЯ от нашей стартовой вершины до ВСЕХ ДРУГИХ.
• Структура Edge (Ребро) для описания ребра, ясно, что ребро связывает вершину u с вершиной v и имеет вес w.

struct Edge {

 unsigned int u;

 unsigned int v;

 double w;

};

•  Будем использовать вектор для хранения ребер vector<Edge>EdgeList, так как к вектору удобно обращаться по индексу;
•  Переменная const double INFINITY=1E+10 для инициализации расстояний в начале работы функции.
• Введем функцию релаксации ребер Relax (unsigned int index, vector <double> &d) для того, чтобы алгоритм был более понятен, какой кусок кода за что отвечает. index-индекс текущего ребра, d - вектор расстояний.

void Relax (unsigned int index, vector <double> &d){

 if (d[EdgeList[index].v]>d[EdgeList[index].u]+EdgeList[index].w){

d[EdgeList[index].v]=d[EdgeList[index].u]+EdgeList[index].w;

}

}

          Процесс релаксации ребра заключается в проверке ребра на то, можно ли улучшить путь из вершины u в v.
Примеры с картиночками можно почитать у Кормена на странице 670.

Сам алгоритм состоит в том, чтобы:

1. Cначала инициализируем все расстояния бесконечными величинами, а расстояние стартовой вершины нулем.
2. Цикл for для каждой вершины
1. Вложенный цикл где для каждого ребра идет процесс релаксации
3. Вывод расстояний

Простейшая неоптимизированная реализация:

void Bellman_Ford_Shortest_Path(double start, unsigned int numOfVertices){

 vector<double> d (numOfVertices, INFINITY);

 d[start]=0;

 for (unsigned int i=0; i<numOfVertices-1; i++){

  for (unsigned int j=0; j<EdgeList.size();j++){

   Relax(j,d);//РЕЛАКСАЦИЯ РЕБРА

  }

 }

 for (int i=0; i<d.size(); i++){

  if (d[i]<INFINITY){ //ЕСЛИ ЕСТЬ ПУТЬ

   cout<<"vertex "<< i+1 <<") "<<d[i]<<endl;

  }

  else cout<<"vertex "<< i+1 <<") "<<"No way to this vertex"<<endl;

 }

}

Брр. тега <code> На блогспоте не вижу, очень неудобно внедрять код.

Posted in: Алгоритмы, Графы, CPP