Практикум по дисциплине «Дискретная математика»
Расстояния в ориентированном графе
жүктеу/скачать
0,98 Mb.
бет
12/25
Дата
10.01.2020
өлшемі
0,98 Mb.
#55624
түрі
Практикум
1
...
8
9
10
11
12
13
14
15
...
25
Байланысты:
[ZHitnikova N.I.] Teoriya grafov. Praktikum(z-lib.org)
2.2.
Расстояния
в
ориентированном графе
С помощью алгоритма фронта волны найти расстояния в ориентированном графе
D
: диаметр, радиус и центры.
Пусть
ориентированный граф с n2
вершинами и
v
,
w
(
v
w
) – заданные вершины из
V
.
Алгоритм поиска минимального пути из
в
в ориентированном графе
(
алгоритм
фронта волны
).
Помечаем вершину
индексом 0, затем помечаем вершины
образу вершины
индексом 1. Обозначаем их
FW
1
(
v
). Полагаем
k
=1.
Если
или
k
=
n
-1, и
одновременно
то вершина
не достижима из
. Работа алгоритма заканчивается.
жүктеу/скачать
0,98 Mb.
Достарыңызбен бөлісу:
1
...
8
9
10
11
12
13
14
15
...
25
©engime.org 2024
әкімшілігінің қараңыз
Басты бет
ориентированный граф с n2 
в 
в ориентированном графе
индексом 0, затем помечаем вершины 
или k=n-1, и 
то вершина