- Подробности
- Автор: Super User
- Категория: Теория графов
- Просмотров: 10714
В графе (Рис. 1) найти длину кратчайшего пути из Х4 в Х1
Решение
Составим таблицу пошагово:
На первом шаге вершине S присваиваем метку (0, S), а остальным ( ∞). Выбираем из всех меток наименьшую (y, X4) и делаем её постоянной. Из этой «постоянной» вершины пытаемся пометить достижимые из неё вершины и присваиваем метку:
метка = min(старая метка, метка постоянной вершины + длина ребра).
Метки недостижимых вершин сохраняются. У постоянных вершин метки не меняют точки. Процесс продолжаем, пока постоянной меткой не будет помечена вершина t. Метка вершины t равна длине кратчайшего пути. В нашем случае Lмм=7.
Маршрут восстанавливаем из второй части меток, которые содержат индекс вершины, из которых они помечены.
Тогда кратчайший маршрут: (Х1, Х2, Х3, Х4) или (Х4, Х3, Х2, Х1).

Решение
Составим таблицу пошагово:
| 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 |
s Х1 | ∞ | ∞ | ∞ | ∞ | ∞ | 7,X2 | 7,X2 | 7,X4 |
X2 | ∞ | ∞ | ∞ | 6,X5 | 4,X3 | |||
X3 | ∞ | 3,X4 | 3,X4 | 3,X4 | ||||
t X4 | 0,X4 | |||||||
X5 | ∞ | 2,X4 | 2,X4 | |||||
X6 | ∞ | 1,X4 | ||||||
X7 | ∞ | ∞ | ∞ | 9,X5 | 9,X5 | 6,X2 | 6,X2 | |
X8 | ∞ | ∞ | 4,X6 | 4,X6 | 4,X6 | 4,X6 |
На первом шаге вершине S присваиваем метку (0, S), а остальным ( ∞). Выбираем из всех меток наименьшую (y, X4) и делаем её постоянной. Из этой «постоянной» вершины пытаемся пометить достижимые из неё вершины и присваиваем метку:
метка = min(старая метка, метка постоянной вершины + длина ребра).
Метки недостижимых вершин сохраняются. У постоянных вершин метки не меняют точки. Процесс продолжаем, пока постоянной меткой не будет помечена вершина t. Метка вершины t равна длине кратчайшего пути. В нашем случае Lмм=7.
Маршрут восстанавливаем из второй части меток, которые содержат индекс вершины, из которых они помечены.
Тогда кратчайший маршрут: (Х1, Х2, Х3, Х4) или (Х4, Х3, Х2, Х1).