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

UptoLike

ВУЗ: 

ТвГТУ | Тверь

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

Рубрика: 

16
Таблица 2 Таблица 3
t
c
i
T
1 2 3
0
4,1
3
5,1
6
5
6
,1
3
64
5
,
54
6
,
5
3,6
8
c
t
N
2 3 3
+
t
N
0 1 2
Определяемое таким путём множество кратчайших маршрутов
получается
упорядоченным по их длине, поэтому процесс поиска
кратчайших маршрутов к заданной вершине
l
A не требует построения
всего множества кратчайших маршрутов из вершины
k
A
, но может быть
остановлен в момент появления концевой дуги с вершиной
l
A .
Более детально порядок построения кратчайшего маршрута
эстафетным методом и его вычислительную схему рассмотрим на примере
поиска кратчайшего маршрута )3 ,1(
0
3,1
== lk
μ
на графе дорожной сети,
заданной матрицей расстояний
c (табл. 1).
Из вершины (пункта)
k
A
в момент старта 0=
c
k
T ( −
=
1
k
номер пункта
старта) начинает движение группа гонцов с эстафетами, двигающихся с
единичной скоростью ко всем смежным с
1
A
вершинам (табл. 1;
654
,, AAA ).
Гонца, который первым придёт к своему объекту, будем именовать
лидером и обозначать
ji
Л
,
(первый индекс – номер пункта старта
i
A ,
второй – финиша). Для 1
=
k
лидер
4,1
Л финиширует в пункте
4
A в момент
времени, численно равный минимальному из элементов строки 1
=
k
:
{
}
3 ,438,6,3minmin
114,14,1
1
==⇒=====
ф
kjij
j
TjcccL . (2.3)
t
0
,lk
μ
0
, lk
L
1 1,4 3
2 1,4,6 5
3 1,5 6
3 1,4,5 6
4 1,4,6,3 8
5 1,4,6,2 9
6 1,4,6,3,1 13

Страницы