Теми рефератів
> Реферати > Курсові роботи > Звіти з практики > Курсові проекти > Питання та відповіді > Ессе > Доклади > Учбові матеріали > Контрольні роботи > Методички > Лекції > Твори > Підручники > Статті Контакти
Реферати, твори, дипломи, практика » Курсовые проекты » Алгоритми маршрутизації

Реферат Алгоритми маршрутизації





tify"> Алгоритм Флойда вимагає виконання наступних дій.

Крок 0 . Визначаємо початкову матрицю відстані D 0 і матрицю послідовності вузлів S 0. Діагональні елементи обох матриць позначаються знаком - raquo ;, що показує, що ці елементи в обчисленнях не беруть участь. Вважаємо k=1:


Рис. 17. Початкова ситуація

Основний крок k . Задаємо рядок k і стовпець k як провідну рядок і провідний стовпець. Розглядаємо можливість застосування трикутного оператора до всіх елементів d ij матриці D k - 1. Якщо виконується нерівність d ik + d kj lt; d ij, (i lt; gt; k, j lt; gt; k, i lt; gt; j), тоді виконуємо наступні дії:

створюємо матрицю D k шляхом заміни в матриці D k - 1 елемента d ij на суму d ik + d kj,

створюємо матрицю S k шляхом заміни в матриці S k - 1 елемента s ij на k. Вважаємо k=k + 1 і повторюємо крок k.

Пояснимо дії, що виконуються на k-му кроці алгоритму, представивши матрицю D k - 1 так, як вона показана на малюнку 3. На цьому малюнку рядок k і стовпець k є провідними. Рядок i - будь-який рядок з номером від 1 до k - 1, а рядок p - довільна рядок з номером від k + 1 до n. Аналогічно стовпець j являє будь стовпець з номером від 1 до k - 1, стовпець q - довільний стовпець з номером від k + 1 до n. Трикутний оператор виконується наступним чином. Якщо сума елементів провідних рядка і стовпця (показаних в квадратах) менше елементів, що знаходяться в перетині стовпця і рядка (показаних у гуртках), відповідних розглянутим провідним елементам, то відстань (елемент в гуртку) замінюється на суму відстаней, представлених провідними елементами:


Рис. 18. Ілюстрація алгоритму Флойда

Після реалізації n кроків алгоритму визначення за матрицями D n і S n найкоротшого шляху між вузлами i та j виконується за такими правилами.

Відстань між вузлами i та j одно елементу d ij в матриці D n.

Проміжні вузли шляху від вузла i до вузла j визначаємо по матриці S n. Нехай s ij=k, тоді маємо шлях i - gt; k - gt; j. Якщо далі s ik=k і s kj=j, тоді вважаємо, що весь шлях визначений, так як знайдені всі проміжні вузли. В іншому випадку повторюємо описану процедуру для шляхів від вузла i до вузла k і від вузла k до вузла j.

Приклад. Знайдемо для мережі, показаної на малюнку 4, найкоротші шляхи між будь-якими двома вузлами. Відстань між вузлами цієї мережі проставлені на малюнку біля відповідних ребер. Ребро (3, 5) орієнтовано, тому не допускається рух від вузла 5 до вузла 3. Всі інші ребра допускають рух в обидві сторони:


Рис. 19. Приклад мережі


Крок 0 . Початкові матриці D 0 і S 0 будуються безпосередньо за заданою схемою мережі. Матриця D 0 симетрична, за винятком пари елементів d 35 і d 53, де d 53 одно нескінченності, оскільки неможливий перехід від вузла 5 до вузла 3:


Рис.20. Початковий стан


Крок 1 . У матриці D 0 виділені провідні рядок і стовпець (k=1). Подвійною рамкою представлені елементи d 23 і d 32, єдині серед елементів матриці D 0, значення яких можна поліпшити за допомогою трикутного оператора. Таким чином, щоб на основі матриць D 0 і S 0 отримати матриці D 1 і S 1, виконуємо наступні дії.

Замінюємо d 23 на d 21 + d 13=3 + 10=13 і встановлюємо s 23=1.

Замінюємо d 32 на d 31 + d 12=10 + 3=13 і встановлюємо s 32=1.

Матриці D 1 і S 1 мають такий вигляд:


Рис.21. Матриці D 1 і S 1


Крок 2 . Вважаємо k=2; в матриці D 1 виділені провідні рядок і стовпець. Трикутний оператор застосовується до елементів матриці D 1 і S 1, виділеним подвійною рамкою. В результаті отримуємо матриці D 2 і S 2:


Рис.22. Матриці D 2 і S 2


Крок 3 . Вважаємо k=3; в матриці D 2 виділені провідні рядок і стовпець. Трикутний оператор застосовується до елементів матриці D 2 і S 2, виділеним подвійною рамкою. В результаті отримуємо матриці D 3 і S 3:


Рис.23. Матриці D 3 і S 3


Крок 4 . Вважаємо k=4, провідні рядок і стовпець у матриці D 3 виділені. Отримуємо нові матриці D 4 і S 4:


Рис.24. Матриці D 4 і S 4

Крок 5 . Вважаємо k=5, провідні рядок і стовпець у матриці D 4 виділені. Ніяких дій на цьому кроці не виконуються; обчислення закінчені.

Кінцеві матриці D 4 і S 4 містять всю інформацію, необхідну для визначення найкоротших шляхів між будь-якими дво...


Назад | сторінка 4 з 7 | Наступна сторінка





Схожі реферати:

  • Реферат на тему: Автоматизація розв'язання задачі на находженіе матриці в складі іншої м ...
  • Реферат на тему: Розробка в середовищі Turbo Pascal програми обчислення суми елементів рядкі ...
  • Реферат на тему: Розробка в середовищі Turbo Pascal програми сортування елементів, що знаход ...
  • Реферат на тему: Визначення ортогональної матриці
  • Реферат на тему: Матриці