2.6.2 Алгоритм найкоротшого шляху
Процедура BFS
пошуку у ширину знаходить віддаль від
початкової вершини
до кожної із вершин графа
,
для яких існує шлях із
.
Під віддалю розуміють довжину найкоротшого
шляху:
визначається як довжина мінімального
шляху, що веде із
у
.
У нашому випадку довжина шляху – це
кількість ребер із
у
.
Якщо шляхів немає, то віддаль дорівнює
нескінченності. Найкоротших шляхів у
графі
може бути декілька.
Працюючи на графі орієнтованому
чи неорієнтованому з початковою вершиною
,
процедура BFS
виявить (зробить
чорними) всі вершини, що є досягнутими
із
,
і для всіх
буде виконана рівність
.
Окрім того, для будь-якої вершини
,
що є досягнутою із
один із найкоротших шляхів із
у
можна отримати додаючи ребро
до (будь-якого) найкоротшого шляху із
у
.
Для вершини, що є не досягнутою, із
значення
дорівнює NIL.
1
Багатокутник називається
випуклим,
якщо для будь-яких двох точок, що лежать
всередині або на границі багатокутника,
відрізок який з’єднує ці точки повністю
лежить всередині чи на границі
багатокутника.
31