П.6. Алгоритм знаходження максимального шляху
Друга ітерація.
Перша ітерація.
ІІ етап. Побудова найкоротшого шляху.
П'ята ітерація.
Третя ітерація.
Друга ітерація.
Крок 2.Безліч вершин безпосередньо наступних за тимчасовими мітками . Перераховуємо тимчасові мітки цих вершин:
Крок 3.Одна з тимчасових міток перетворюється на постійну:
Крок 4., відбувається повернення на другий крок.
Крок 2.Безліч вершин безпосередньо наступних за тимчасовими мітками . Перераховуємо тимчасові мітки цих вершин:
Крок 3.Одна з тимчасових міток перетворюється на постійну:
Крок 4., відбувається повернення на другий крок.
Четверта ітерація.
Крок 2.Безліч вершин безпосередньо наступних за тимчасовими мітками . Перераховуємо тимчасові мітки цих вершин:
Крок 3.Одна з тимчасових міток перетворюється на постійну:
Крок 4., відбувається повернення на другий крок.
Крок 2.Безліч вершин безпосередньо наступних за тимчасовими мітками . Перераховуємо тимчасові мітки цих вершин:
Крок 3.Одна з тимчасових міток перетворюється на постійну:
Крок 4., кінець першого етапу.
Крок 5.Складемо безліч вершин безпосередньо попередніх вершині з постійними мітками. Перевіримо для цієї вершини виконання
Включаємо дугу в потрібний шлях і вважаємо.
Крок 6., отже. повертаємось до п'ятого кроку.
Крок 5.Складемо безліч вершин безпосередньо попередніх вершині з постійними мітками. Перевіримо для цієї вершини виконання
Включаємо дугу в потрібний шлях і вважаємо.
Крок 6., завершення другого етапу.
Найкоротший шлях утворює послідовність дуг.
Для знаходження максимального шляху граф G (мережі) може бути ациклическим, бо інакше може бути, що довжини деяких шляхів не обмежені зверху. Якщо G - ациклічний граф, то для будь-яких двох його вершин виконується одна з трьох умов:
3. Немає шляху між і .
Через необхідну ациклічність графа перші та другі умови одночасно не здійсненні.
Перед обчисленням максимального шляху орграфі необхідно впорядкувати вершини графа за алгоритмом Фалкерсона. Сам алгоритм обчислення максимального шляху є чисто перечислювальним. Він перебирає всі можливі шляхи від поточної вершини до наступних, досяжних з поточної вершини.
Нехай - довжина максимального шляху від вершини до вершини, тоді величина задовольняє наступним рекурентним співвідношенням:
Співвідношення (1) дозволяють легко обчислити довжини максимальних шляхів до вершин, досяжних з вершиниs. Самі шляхи можуть бути побудовані методом послідовного повернення (другий етап алгоритму Дейкстри).
Приклад.Граф G заданий матрицею ваг Ω. Знайти довжину максимального шляху з вершини у сам цей шлях.
По даній матриці терезів побудований граф на рис.15. Цей граф є ациклічним, тому можливе впорядкування його вершин за алгоритмом Фалкерсона. Зробимо це графічним методом.
| Мал. 15 |
Графічний спосіб упорядкування вершин графа (алгоритмФалкерсона)
1. Вершина -не містить вхідних дуг, отже, віднесемо її допершоїгрупи.
2. Викреслюємо вершину і всі дуги, що виходять із . Отримаємо граф на рис.16.
| Мал. 16 |
В отриманому графі знову знаходимо вершини, в які не входить жодна дуга. Це вершина. Віднесемо її додругої групи.
3. Викреслюємо вершину і всі дуги, що виходять із . Отримаємо граф на рис.17.
| Мал. 17 |
В отриманому графі знову знаходимо вершини, в які не входить жодна дуга. Це вершина. Віднесемо її дотретій групі.
4. Викреслюємо вершину і всі дуги, що виходять із . Отримаємо граф на рис.18.
| Мал. 18 |
| Мал. 19 |
5. Викреслюємо вершину і всі дуги, що виходять із . Отримаємо граф на рис.19.
| Мал. 20 |
6. Викреслюємо вершину і всі дуги, що виходять із . Отримаємо граф на рис.20.
Знаходимо вершини, в які не входить жодна дуга. Це вершина. Віднесемо її дошостої групи
Ізоморфний граф із упорядкованими вершинами представлений на рис.21.
| Мал. 21 |
Етап I
Отже, довжина максимального шляху дорівнює 30.