Page 39 - 4386

Задача пошуку найкоротшого маршруту або відстані між

двома вершинами графа виникає дуже часто, коли граф виступає

моделлю, наприклад, певної транспортної системи.

У довільному зв’язному графі G=(V, E) функція відстані

d(v, w) задовольняє трьом аксіомам метрики, тобто за будь-яких

вершин v, w, u∈V виконується:

1) d(v, w)≥0; d(v, w)=0 тоді і тільки тоді, коли v=w;

2) d(v, w)=d(w, v);

3) d(v, w)≤d(v, u)+d(u, w).

Функція d(v, w), що задовольняє трьом перерахованим

умовам, називається метрикою графа.

3.6 Алгоритм знаходження відстаней від заданої вершини
до інших вершин графа

Розглянемо алгоритм, що дозволяє знайти відстань від

заданої вершини v до інших вершин графа.
i
1. Позначаємо через A ={v }.
i
0
2. Позначаємо індексом i всі вершини, суміжні з вершиною

v , виписуємо множину A усіх цих вершин з їхніми позначками.
i
1
3. Кожну вершину, що не належить множині A ∪A і
0
1
суміжну з кожною з вершин, що належать множині A ,
1
позначаємо відповідним індексом суміжної з множини A 1

вершини; виписуємо множину A усіх цих вершин з їхніми
2
позначками.

4. Повторюємо описану процедуру доти, поки множина

непозначених вершин не виявиться порожньою.

Приклад 3.8. Визначити відстань від вершини 7 до всіх

вершин графа G, зображеного на рис. 3.6.

38