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


Минимальный путь в нагруженном ориентированном графе



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

2.3. Минимальный путь в нагруженном ориентированном графе

Найти минимальный путь в нагруженном ориентированном графе из вершины в вершину по методу Форда-Беллмана.

Рассмотрим сначала общую задачу – нахождения минимального пути из вершины vнач в vкон.



Пусть D=(V,X) – нагруженный ориентированный граф, V={v1,…,vn}, n>1. Введем величины , где i=1,…,n, k=0,1,2,…,n1.

Для каждого фиксированного i и k величина равна длине минимального пути среди путей из vнач в vi содержащих не более k дуг. Если путей нет, то .

Положим также .

Составляем матрицу длин дуг C(D)=[cij] порядка n:





Утверждение. При i=2,…,n, k0 выполняется равенство

. (3.1)



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




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

    Басты бет