Практикум по дисциплине «Дискретная математика»


Алгоритм Форда-Беллмана нахождения минимального пути в нагруженном ориентированном графе



бет17/25
Дата10.01.2020
өлшемі0,98 Mb.
#55624
түріПрактикум
1   ...   13   14   15   16   17   18   19   20   ...   25
Байланысты:
[ZHitnikova N.I.] Teoriya grafov. Praktikum(z-lib.org)

Алгоритм Форда-Беллмана нахождения минимального пути в нагруженном ориентированном графе D из vнач в vкон.( vначvкон)
записываем в виде матрицы, i- строка, k-столбец.

  1. Составляем таблицу , i=1,…,n, k=0,…,n-1. Если , то пути из vнач в vкон нет. Конец алгоритма.

  2. Если то это число выражает длину любого минимального пути из vнач в vкон. Найдем минимальное k11, при котором . По определению получим, что k1- минимальное число дуг в пути среди всех минимальных путей из vнач в vкон.

  3. Затем определяем номера i2,…, такие, что

,

,



,

то есть, восстанавливаем по составленной таблице и матрице стоимости искомый минимальный путь из vнач в vкон.





Достарыңызбен бөлісу:
1   ...   13   14   15   16   17   18   19   20   ...   25




©engime.org 2024
әкімшілігінің қараңыз

    Басты бет