Учебное пособие C#. Алгоритмы и структуры данных н. А. Тюкачев, В. Г. Хлебостроев издание третье, стереотипное 1 / 23

Листинг 5.34. Алгоритм Форда-Мура-Беллмана 
public void Bellmann(int from) 
// 
было ли на этом шаге изменено значение кратчайше-
го 
// 
пути хоть до одной вершины 
{ 
int N = Nodes.Length; 
bool Ok; 
for (int i = 0; i <= N - 1; i++) 
if (i == from) 
Nodes[i].dist = 0; 
else 
Nodes[i].dist = 0xFFFFF; 
do 
{// 
сохраняем значение кратчайшего пути на пре-
дыдущем шаге 
for (int i = 0; i <= N - 1; i++) 
Nodes[i].oldDist = Nodes[i].dist; 
Ok = false; 
for (int i = 0; i <= N - 1; i++) 
{ 
14 / 23

---

176 
int LL = 0; 
if (Nodes[i].Edge != null) 
{ 
LL = Nodes[i].Edge.Length; 
if (LL > 0) 
// 
просматриваем ребра, входящие в те-
кущую вершину 
for (int j = 0; j <= LL - 1; j++) 
{ 
Edge = Nodes[i].Edge[j]; 
if (Edge.A +
Nodes[Edge.numNode].oldDist <
Nodes[i].dist)
// 
если нашли путь короче 
{ 
Nodes[i].dist = Edge.A +
Nodes[Edge.numNode].oldDist;
// 
исправляем Dist 
Ok = true; // 
и ставим флаг 
} 
} 
} 
} 
while (Ok); // 
если очередная итерация прошла 
неуспешно 
} 
Этот алгоритм найдет решение за время O(N
3
). 
15 / 23

---

177 
5.5. Ц
ИКЛЫ НА ГРАФАХ
 
В пп. 5.1 было дано определение цикла как замкнутого маршрута без 
повторяющихся ребер. При отсутствии в нем повторяющихся вершин, кроме 
совпадающих первой и последней, цикл называется простым. Очевидно, что 
если в графе существует маршрут, ведущий из вершины v
0
в v
n
, то существу-
ет и простая цепь между этими вершинами. Действительно, такую простую 
цепь можно построить, удалив из маршрута все циклы.