2014-02-09
6284
Пусть необходимо найти минимальный путь из вершины 
в вершину 
.
1. Выписываются все вершины с 1 по n. Вершина 
помечается индексом 0.
2. Находится первый фронт волны 
как множество вершин образа вершины .
(3.17)
3. Все вершины, принадлежащие первому фронту волны, помечаются индексом 1.
4. Вводится счетчик шагов (фронтов волны) 
.
5. Если 
или 
, то вершина недостижима из вершины, и работа алгоритма на этом заканчивается. В противном смысле переходим к пункту 6.
6. Если 
, то переходим к пункту 8. В противном случае существует путь из вершины в вершину длиной в 
единиц, и этот путь минимальный:
7. Находятся промежуточные вершины 
z по правилу:
, (3.18)
где 
- прообраз вершины 
- множество вершин, из которых заходят дуги в вершину
8. Определяется 
фронт волны как все непомеченные вершины, принадлежащие образу вершин - го фронта волны. Помечаются индексом вершины фронта волны. Далее осуществляется переход к пункту 5.
ПРИМЕР
Пусть задан граф матрицей смежности:
| 
| 
| 
| 
| 
| |
|
| ||||||
|
| ||||||
|
| ||||||
|
| ||||||
|
| ||||||
|
|
Необходимо найти минимальный путь из вершины в вершину (по алгоритму «фронта волны»).
|
|
|
1. Выпишем все вершины. Вершина помечается индексом «0»
2. Находится первый фронт волны:
3. Все вершины, принадлежащие первому фронту волны, помечаются индексом «1».
0 1 1
4. Так как 
, 
и 
, то определяем второй фронт волны:
5. Все вершины, принадлежащие второму фронту волны, помечаются индексом «2».
0 2 2 1 1
6. Так как 
, 
и 
, то определяем третий фронт волны:
7. Так как 
, то существует путь из вершины в вершину длиной 3 единицы:
8. Находятся промежуточные вершины 
:
Выберем 
Выберем 
Таким образом, минимальный путь из вершины в вершину имеет вид:
