Элементарные решения неэлементарных задач на графах. Берзин Е.А. - 21 стр.

UptoLike

ВУЗ: 

ТвГТУ | Тверь

Составители: 

Рубрика: 

23
Рис. 2. Блок-схема алгоритма построения кратчайшего маршрута (КМ)
эстафетным методом
–
–
+
+
Начало
Ввод:
ij
c=c
, k, l
1
=
t
{}
{
}
0,},,0|{, ==∈>=≠=
c
k
tt
kj
t
k
t
TkIGjcjGkjG
Определение множеств
(
)
{
}
{
}
kk
jji ;, из условия
()
(
)
{
}
{
}
t
t
tijij
Gj
k
jIijiccIi
t
t
i
;,,min: ∈⇒=∈∀
∈
(
)
{
}
=∈∀
t
t
jiIi ,:
∅?
Построение множества концевых дуг КМ:
{}
(
)
(
)
}
}
}
ttttji
c
iij
c
i
Ii
tt
ijjicTcTji
tttt
t
,,,min:, ⇒+=+
∈
Определение КМ и их длин по концевым дугам:
(
)
{
}
ttt
c
ikjtttttkj
TLjjkjiik
+
==∪=
00
;,,...,,,...,
μ
{
}
t
jl
∈
Пересчет
{
}
{
}
{}
011
11
; ,\
; ;\
ttt
kj
c
j
c
ji
t
t
t
i
t
i
t
tt
t
tt
LTTIijGG
jiIIjGG
==∈=
=∪==
=
++
++
1
+
=
tt
Вывод:
{
}
0000
;,
tt
kjklttkjkl
LLjj =∈=
μμ
Конец
2º
3º
4º
5º
6º
7º
8º
9º
10º
11º
1º

Страницы