Студопедия

КАТЕГОРИИ:

АстрономияБиологияГеографияДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРиторикаСоциологияСпортСтроительствоТехнологияФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника


Нахождение минимального пути в нагруженном орграфе




Существует несколько алгоритмов нахождения кратчайшего маршрута в нагруженном графе:

Алгоритм Форда – Беллмана.

Алгоритм Дейкстры.

Пусть Д=(V,X) – нагруженный орграф. V={v1,…,vn}.

C(Д)nxn=[cij] – матрица длин дуг нагруженного орграфа.

Величина li(k), где i=1,…,n; k=1,2,… , равна длине минимального пути среди путей из v1 в vi, содержащих не более k дуг. Если таких путей нет, то li(k)=¥. l1(0) =0, li(0)=¥, i=2,…,n.

Утверждение:

При i=2,…,n, k≥0:

При i=1, k≥0:

Число дуг в простой цепи не превосходит n-1. Следовательно,
li(k)= li(n-1) i=2,..,n,k≥n-1.

Если li(n-1)=¥ (i Î {2,..,n}), то vi не достижима из v1, а если li(n-1)<¥, то vi достижима из v1 и при этом li(n-1) –длина минимального пути из v1 в vi.

Таким образом, по li(n-1) можно судить о достижимости вершин vi (i=2,…,n) из v1, а также определить длины минимальных путей из v1 в достижимые вершины.

Алгоритм Форда-Беллмана нахождения минимального пути в нагруженном орграфе из v1 в vi1 (i1≠1)

Шаг 1: Пусть таблица величин li(k)(i=1,2,…,n;k=0,1,…,n-1) составлена. Если , то вершина не достижима из . В этом случае работа алгоритма заканчивается.

Шаг 2: Пусть . Тогда число выражает длину любого минимального пути из в в нагруженном орграфе Д.

Определим минимальное число k1≥1, при котором выполняется равенство . По определению чисел li(k) получаем, что k1 – минимальное число дуг в пути среди всех минимальных путей из в в нагруженном орграфе Д.

Шаг 3: Последовательно определяем номера такие, что:

(*)

Из (*) с учетом того, что ,имеем Þ

(1)

Складывая равенства (*) и учитывая (1) получаем: , т.е. - искомый минимальный путь из в в нагруженном орграфе Д.

В этом пути ровно k1 дуг. Следовательно, мы определили путь с минимальным числом дуг среди всех минимальных путей из в в нагруженном орграфе Д.


Поделиться:

Дата добавления: 2015-01-29; просмотров: 255; Мы поможем в написании вашей работы!; Нарушение авторских прав





lektsii.com - Лекции.Ком - 2014-2024 год. (0.007 сек.) Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав
Главная страница Случайная страница Контакты