АкушерствоАнатомияАнестезиологияВакцинопрофилактикаВалеологияВетеринарияГигиенаЗаболеванияИммунологияКардиологияНеврологияНефрологияОнкологияОториноларингологияОфтальмологияПаразитологияПедиатрияПервая помощьПсихиатрияПульмонологияРеанимацияРевматологияСтоматологияТерапияТоксикологияТравматологияУрологияФармакологияФармацевтикаФизиотерапияФтизиатрияХирургияЭндокринологияЭпидемиология

в орграфі методом Дейкстри.

Ленція 15

Знаходження мінімального шляху

в орграфі методом Дейкстри.

Розглянемо задачу пошуку мінімального шляху між заданими вершинами орграфа з використанням алгоритму Дейкстри.

Задана матриця ваги дуг між вершинами, де x_ij – відстань від i-ї вершини до j-ї вершини. Знайти мінімальний шлях від х₁ до інших вершин за алгоритмом Дейкстри:

Згідно матриці побудуємо орграф.

Впорядкуємо вершини орграфа.

Введемо позначки: d(x_i) – довжина шляху від вершини x₁ до вершини x_i.

Поступово біля вершин поставимо мітки на зразок х₃̅(12) – статус «постійна», тобто до вершини знайдено мінімальний шлях.

І ітерація: x₁₁ – відстань від 1-ї вершини до 1-ї вершини дорівнює 0, а шляхи до 1-ї вершини від інших вершин відсутні, то початкові значення приймемо як:

d(x₁) = 0; d(x₂) = d(x₃) = d(x₄) = d(x₅) = d(x₆) =∞.

Min(d(x₁), d(x₂), d(x₃), d(x₄), d(x₅), d(x₆))=Min(0, ∞,∞,∞,∞,∞)=0, отже помітимо вершину x₁ як «постійну».

ІІ ітерація: d(x₁̅) = 0;

Обчислимо відстані до інших вершин відносно «постійних»:

d(x₂) = min(∞, d(x₁̅) +x₁₂) = min(∞, 0 +5) = 5;

d(x₃) = min(∞, d(x₁̅) +x₁₃) = min(∞, 0 +13) = 13;

d(x₄) = min(∞, d(x₁̅) +x₁₄) = min(∞, 0 +10) = 10;

d(x₅) = min(∞, d(x₁̅) +x₁₅) = min(∞, 0 +∞) = ∞;

d(x₆) = min(∞, d(x₁̅) +x₁₆) = min(∞, 0 +∞) = ∞.

Min(5,10,13,∞,∞)=5, отже помітимо вершину x₂, d(x₂̅) =5. На графі поряд з поміченою вершиною в дужках поставимо знайдену відстань до неї.

ІІІ ітерація: d(x₁̅) = 0; d(x₂̅) =5;

d(x₃) = min(∞, d(x̅₁) +x₁₃, d(x̅₂) +x₂₃) = min(∞, 0 +13, 5+13) = 13;

d(x₄) = min(∞, d(x̅₁) +x₁₄, d(x̅₂) +x₂₄) = min(∞, 0 +10, 5+8) = 10;

d(x₅) = min(∞, d(x₁̅) +x₁₅, d(x̅₂) +x₂₅) = min(∞, 0 +∞, 5+9) = 14;

d(x₆) = min(∞, d(x₁̅) +x₁₆, d(x̅₂) +x₂₆) = min(∞, 0 +∞, 5+∞) = ∞.

Min(13,10,14,∞)=10, отже помітимо вершину x₄, отже d(x₄̅) =10.

ІV ітерація: d(x₁̅) = 0; d(x₂̅) =5; d(x₄̅) =10;

d(x₃) = min(∞, d(x̅₁) +x₁₃, d(x̅₂) +x₂₃, d(x̅₄) +x₄₃) = min(∞, 0 +13, 5+13, 10+∞) = 13;

d(x₅) = min(∞, d(x₁̅) +x₁₅, d(x̅₂) +x₂₅, d(x̅₄) +x₄₅) = min(∞, 0 +∞, 5+9, 10+8) = 14;

d(x₆) = min(∞, d(x₁̅) +x₁₆, d(x̅₂) +x₂₆, d(x̅₄) +x₄₆) = min(∞, 0 +∞, 5+∞, 10+10) = 20.

Min(13, 14, 20)=13, таким чином помітимо вершину x₃, отже d(x₃̅) =13.

d(x₅) = min(∞, d(x₁̅) +x₁₅, d(x̅₂) +x₂₅, d(x̅₄) +x₄₅, d(x̅₃) +x₃₅) =

=min(∞, 0 +∞, 5+9, 10+8, 13+6) = 14;

d(x₆) = min(∞, d(x₁̅) +x₁₆, d(x̅₂) +x₂₆, d(x̅₄) +x₄₆, d(x̅₃) +x₃₆) =

=min(∞, 0 +∞, 5+∞, 10+10, 13+6) = 19.

VI ітерація: d(x₁̅) = 0; d(x₂̅) =5; d(x₃̅) =13; d(x₄̅) =10; d(x₅̅) =14.

d(x₆) = min(∞, d(x₁̅) +x₁₆, d(x̅₂) +x₂₆, d(x̅₄) +x₄₆, d(x̅₃) +x₃₆, d(x̅₅) +x₅₆) =

=min(∞, 0 +∞, 5+∞, 10+10, 13+6, 14+9) = 19;

d(x₆̅) =19.

Відповідь: d(x₁̅) = 0; d(x₂̅) =5; d(x₃̅) =13; d(x₄̅) =10; d(x₅̅) =14; d(x₆̅) =19.

Дата добавления: 2015-09-27 | Просмотры: 525 | Нарушение авторских прав