Page 20 - 2577

Алгоритми маршрутизації орієнтовані на топологію мережі, дають можливість
визначити стратегію маршрутизації на основі відомостей про топологію мережі і вартості
каналів. До таких стратегій відносяться фіксована, лавинна, стохастична і адаптивна
маршрутизації.
Алгоритм пошуку в ширину є одним із найпростіших алгоритмів маршрутизації в
мережах. Проте ідеї, покладені в його основу, використовуються в більш складних
алгоритмах, зокрема в алгоритмі Дейкстри.
Алгоритм пошуку в ширину вирішує задачу знаходження мінімальних шляхів від
заданої вихідної вершини s шляхом систематичного обходу всіх ребер графа для
”відкриття” всіх вершин, які досяжні з вихідної вершини s. Він обчислює мінімальні відстані
та будує мінімальні шляхи від заданої вихідної вершини s до всіх решти вершин графа, які
досяжні з вихідної вершини.
Алгоритм пошуку в ширину застосовується як для неорієнтованих, так і для
орієнтованих графів. Вхідними даними для реалізації даного алгоритму є топологічна
структура графа, подана у вигляді списку суміжності та вихідної вершини.
Алгоритм пошуку в ширину дає такі результати:
 мінімальні відстані (мінімальні кількості ребер) від вихідної вершини s до кожної
вершини графа, яка досяжна з s ;
 дерево пошуку в ширину з коренем у вершині s , в якому для кожної вершини
шлях з вершини s (кореня дерева пошуку в ширину) відповідає найкоротшому.
Результат роботи такого алгоритму може залежати від порядку перегляду вершин,
суміжних з даною вершиною. Звідси витікає, що дерево пошуку може змінюватися, але
кількість ребер у мінімальних відстанях не залежить від порядку перегляду вершин.
Словесний опис алгоритму буде мати наступний вигляд
Крок І. [Ініціалізація]: для кожної вершини графа:
1. Вершина предок (vertexParent) не визначена (NULL).
2. Мінімальна відстань (routeWeight) дорівнює нескінченності
(numeric_limits<double>::infinity()).
3. Статус (currentVertexStatus) вершини встановити WHITE.
4. Мінімальна відстань для вихідної вершини s дорівнює 0.
5. Статус вихідної вершини s встановити GRAY.
6. Помістити в чергу (vertexQueue) вихідну вершину s .
Крок ІІ. [Перегляд суміжних вершин]: взяти з черги наступну вершину currentVertex
та проглянути список суміжних з нею вершин Vertex. Якщо черга порожня, то STOP.
Крок IІІ. [Модифікація стану суміжної вершини]: для кожної суміжної вершини
Vertex з списку якщо її статус WHITE, то:
1. Змінити статус на GRAY.
2. Збільшити значення мінімальної відстані до вихідної вершини s на 1.
3. Як вершину предок взято вершину currentVertex.
4. Помістити кожну суміжну проглянуту вершину Vertex у чергу.
5. Після завершення перегляду списку суміжних вершин змінити статус вершини
currentVertex на BLACK.
Крок IV. [Ітераційний перехід]: перейти до Кроку ІІ.
Отже, алгоритм пошуку в ширину будує маршрут, додаючи на кожному кроці ітерації
вершину, до якої відстань з вихідної вершини s на поточному етапі обчислень є
найкоротшою. Після перегляду всіх вершин, що знаходяться на відстані k від вихідної
вершини s , алгоритм переходить до розгляду вершин на відстані k , звідси й його назва. В
процесі роботи алгоритму кожна досяжна з s вершина змінює свій стан у такій послідовності:
WHITE (вершина ще не ”відкрита” алгоритмом), GRAY (вершина ”відкрита” алгоритмом, але
список її суміжних вершин ще не проглянутий), BLACK (вершина ”відкрита” алгоритмом і список
її суміжних вершин проглянутий). Код програми, складеної за цим алгортимом представлено в
додатку А.

17