в орграфі методом Дейкстри.
Ленція 15
Знаходження мінімального шляху
в орграфі методом Дейкстри.
Розглянемо задачу пошуку мінімального шляху між заданими вершинами орграфа з використанням алгоритму Дейкстри.
Задана матриця ваги дуг між вершинами, де xij – відстань від i-ї вершини до j-ї вершини. Знайти мінімальний шлях від х1 до інших вершин за алгоритмом Дейкстри:
Згідно матриці побудуємо орграф.
Впорядкуємо вершини орграфа.
Введемо позначки: d(xi) – довжина шляху від вершини x1 до вершини xi.
Поступово біля вершин поставимо мітки на зразок х3̅(12) – статус «постійна», тобто до вершини знайдено мінімальний шлях.
І ітерація: x11 – відстань від 1-ї вершини до 1-ї вершини дорівнює 0, а шляхи до 1-ї вершини від інших вершин відсутні, то початкові значення приймемо як:
d(x1) = 0; d(x2) = d(x3) = d(x4) = d(x5) = d(x6) =∞.
Min(d(x1), d(x2), d(x3), d(x4), d(x5), d(x6))=Min(0, ∞,∞,∞,∞,∞)=0, отже помітимо вершину x1 як «постійну».
ІІ ітерація: d(x1̅) = 0;
Обчислимо відстані до інших вершин відносно «постійних»:
d(x2) = min(∞, d(x1̅) +x12) = min(∞, 0 +5) = 5;
d(x3) = min(∞, d(x1̅) +x13) = min(∞, 0 +13) = 13;
d(x4) = min(∞, d(x1̅) +x14) = min(∞, 0 +10) = 10;
d(x5) = min(∞, d(x1̅) +x15) = min(∞, 0 +∞) = ∞;
d(x6) = min(∞, d(x1̅) +x16) = min(∞, 0 +∞) = ∞.
Min(5,10,13,∞,∞)=5, отже помітимо вершину x2, d(x2̅) =5. На графі поряд з поміченою вершиною в дужках поставимо знайдену відстань до неї.
ІІІ ітерація: d(x1̅) = 0; d(x2̅) =5;
d(x3) = min(∞, d(x̅1) +x13, d(x̅2) +x23) = min(∞, 0 +13, 5+13) = 13;
d(x4) = min(∞, d(x̅1) +x14, d(x̅2) +x24) = min(∞, 0 +10, 5+8) = 10;
d(x5) = min(∞, d(x1̅) +x15, d(x̅2) +x25) = min(∞, 0 +∞, 5+9) = 14;
d(x6) = min(∞, d(x1̅) +x16, d(x̅2) +x26) = min(∞, 0 +∞, 5+∞) = ∞.
Min(13,10,14,∞)=10, отже помітимо вершину x4, отже d(x4̅) =10.
ІV ітерація: d(x1̅) = 0; d(x2̅) =5; d(x4̅) =10;
d(x3) = min(∞, d(x̅1) +x13, d(x̅2) +x23, d(x̅4) +x43) = min(∞, 0 +13, 5+13, 10+∞) = 13;
d(x5) = min(∞, d(x1̅) +x15, d(x̅2) +x25, d(x̅4) +x45) = min(∞, 0 +∞, 5+9, 10+8) = 14;
d(x6) = min(∞, d(x1̅) +x16, d(x̅2) +x26, d(x̅4) +x46) = min(∞, 0 +∞, 5+∞, 10+10) = 20.
Min(13, 14, 20)=13, таким чином помітимо вершину x3, отже d(x3̅) =13.
V ітерація: d(x1̅) = 0; d(x2̅) =5; d(x3̅) =13; d(x4̅) =10;
d(x5) = min(∞, d(x1̅) +x15, d(x̅2) +x25, d(x̅4) +x45, d(x̅3) +x35) =
=min(∞, 0 +∞, 5+9, 10+8, 13+6) = 14;
d(x6) = min(∞, d(x1̅) +x16, d(x̅2) +x26, d(x̅4) +x46, d(x̅3) +x36) =
=min(∞, 0 +∞, 5+∞, 10+10, 13+6) = 19.
Min(14,19)=14, отже помітимо вершину x4, тоді d(x5̅) =14.
VI ітерація: d(x1̅) = 0; d(x2̅) =5; d(x3̅) =13; d(x4̅) =10; d(x5̅) =14.
d(x6) = min(∞, d(x1̅) +x16, d(x̅2) +x26, d(x̅4) +x46, d(x̅3) +x36, d(x̅5) +x56) =
=min(∞, 0 +∞, 5+∞, 10+10, 13+6, 14+9) = 19;
d(x6̅) =19.
Відповідь: d(x1̅) = 0; d(x2̅) =5; d(x3̅) =13; d(x4̅) =10; d(x5̅) =14; d(x6̅) =19.
Дата добавления: 2015-09-27 | Просмотры: 530 | Нарушение авторских прав
|