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