2.3. Минимальный путь в нагруженном ориентированном графе
Найти минимальный путь в нагруженном ориентированном графе из вершины  в вершину  по методу Форда-Беллмана.
Рассмотрим сначала общую задачу – нахождения минимального пути из вершины vнач в vкон.
Пусть D=(V,X) – нагруженный ориентированный граф, V={v1,…,vn}, n>1. Введем величины  , где i=1,…,n, k=0,1,2,…,n–1.
Для каждого фиксированного i и k величина равна длине минимального пути среди путей из vнач в vi содержащих не более k дуг. Если путей нет, то  .
Положим также  .
Составляем матрицу длин дуг C(D)=[cij] порядка n:
Утверждение. При i=2,…,n, k0 выполняется равенство
 . (3.1)
Достарыңызбен бөлісу: |
