Головна

алгоритм Дейкстри

  1. I. РОЗРОБКА АЛГОРИТМІВ. ГРАФІЧНЕ ЗОБРАЖЕННЯ (БЛОК-СХЕМИ) І СЛОВЕСНА ЗАПИС АЛГОРИТМІВ
  2. АЛГОРИТМ 10
  3. алгоритм DES
  4. алгоритм RSA
  5. Алгоритм автоматичного формування парних симетричних ключів шифрування-дешифрування відкритих повідомлень на робочих станціях абонентів корпоративної системи.
  6. Алгоритм відра маркерів
  7. Алгоритм вираження симетричних многочленів через елементарні.

Етап 1. Знаходження довжини найкоротшого шляху.

Крок 1. Присвоєння вершин початкових міток.

вважаємо  , І вважаємо цю мітку постійної (постійні мітки помічаємо зверху зірочкою). Для інших вершин ,  вважаємо  і вважаємо ці мітки тимчасовими. позначимо через  поточну вершину і приймемо спочатку .

Крок 2. Редагування місць.

Для кожної вершини  з часовою міткою, безпосередньо наступного за вершиною  , Міняємо її позначку згідно з наступним правилом:

.

Крок 3. Перетворення тимчасової мітки в постійну.

З усіх вершин з тимчасовими мітками вибираємо вершину  з найменшим значенням мітки

 де  - Тимчасова мітка.

Перетворюємо цю мітку в постійну і вважаємо .

Крок 4. Перевірка на завершення першого етапу.

якщо  , то  - Довжина найкоротшого шляху від вершини  до  . В іншому випадку відбувається повернення до другого кроку.

Етап 2. Побудова найкоротшого шляху.

Крок 5. Послідовний пошук дуг найкоротшого шляху.

Серед вершин, які безпосередньо передують вершині  з постійними мітками, знаходимо вершину  , Що задовольняє співвідношенню

.

включаємо дугу  в шуканий шлях і вважаємо .

Крок 6. Перевірка на завершення другого етапу.

якщо  , То найкоротший шлях знайдений - його утворює послідовність дуг, отриманих на п'ятому кроці і вибудуваних в зворотному порядку. В іншому випадку повертаємося до п'ятого кроку.

Приклад 3.1. За заданою матрицею ваг

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

Рішення.

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

Етап 1. Крок 1. Вважаємо ,

.

Крок 2. За вершиною  слідують вершини, які утворюють безліч .

Перерахуємо тимчасові мітки:

, ,

, .

отримуємо  . Отже, вершині  присвоюється постійна мітка: , .

Крок 3.  . Перерахуємо тимчасові мітки:

, ,

, .

отримуємо  . Отже, вершині  присвоюється постійна мітка: , .

Крок 4.  . Перерахуємо тимчасові мітки:

, ,

, .

отримуємо  . Отже, вершині  присвоюється постійна мітка: .

Крок 5.  . Перерахуємо тимчасові мітки:

,

,

.

отримуємо  . Отже, вершин и  присвоюються постійні мітки: .

Крок 6.  . вершині  присвоюється постійна мітка .

Етап 2.

Проводимо послідовний пошук дуг найкоротшого шляху.

вершині  передують вершини  . Найкоротша відстань отримаємо при проходженні по дузі

вершині  передують вершини  . Найкоротша відстань отримати при проходженні по дузі

Таким чином, найкоротший шлях від вершини  до вершини  побудований. Його довжина (вага) становить 21, тобто  , Сам шлях задає наступну послідовність дуг -

відповідь: , -

4. ейлерову І Гамільтона циклу

 



Попередня   6   7   8   9   10   11   12   13   14   15   16   17   18   19   20   21   Наступна

Можливості підключення графів | ступінь вершин | Подання графів в комп'ютері | Приклад 1.6. | дерева | Приклад 2.1. | остовне дерева | Приклад 2.2. | Алгоритм Краскала і алгоритм Прима | алгоритм Краскала |

© um.co.ua - учбові матеріали та реферати