2 Решение задачи
Разработка схемы автобусных маршрутов состоит из нескольких этапов.
2.1 Этап 1. Определение (по времени) путей между пунктами (микрорайонами)
Этот этап выполняется с помощью потенциалов – нахождение кратчайших расстояний. Он состоит из двух шагов.
Шаг 1. Присвоим начальному узлу сети потенциал 0. В данной задаче первым начальным узлом примем пункт 1. Присвоим ему потенциал 0 (рис. 2).
Шаг 2. Просмотрим все звенья, начальные узлы которых имеют потенциалы, а конечные нет. Определим потенциалы конечных узлов как соединяющему начальный и конечный узлы. Выберем конечный узел с наименьшим потенциалом, запишем его рядом с узлом и отметим звено стрелкой. Шаг 2 повторяем до тех пор, пока всем узлам не будут присвоены потенциалы.
Рисунок 2 - Определение кратчайших путей
Звенья со стрелочками показывают кратчайший путь от пункта 1 ко всем остальным пунктам. Результаты этих расчетов записываем в табл. 3, где в соответствующих клетках в верхнем левом углу указаны пункты между начальным и конечным пунктами.
Аналогично выполняются расчеты по всем пунктам, каждый из которых последовательно принимается за начальный, а результаты вносятся в табл. 3, где выявлены все кратчайшие по времени следования маршруты между всеми пунктами транспортной сети.
Таблица 3 – Кратчайшие (по времени) маршруты между всеми пунктами сети
Откуда |
Куда |
|||||||
№ микрорайона |
13 |
14 |
9 |
1 |
3 |
10 |
5 |
12 |
13 |
|
|
|
5,9 |
9 |
9 |
9 |
|
51 |
36 |
99 |
125 |
64 |
74 |
100 |
||
14 |
|
|
|
9,5 |
|
|
9 |
|
51 |
41 |
102 |
93 |
31 |
70 |
64 |
||
9 |
|
|
|
5 |
|
|
|
10 |
36 |
41 |
62 |
89 |
31 |
37 |
85 |
||
1 |
5,9 |
9,5 |
5 |
|
11 |
5,9 |
|
|
99 |
102 |
62 |
63 |
93 |
25 |
107 |
||
3 |
9 |
|
|
|
|
|
|
|
125 |
93 |
89 |
63 |
70 |
85 |
82 |
||
10 |
9 |
|
|
5,9 |
|
|
9 |
|
64 |
31 |
31 |
93 |
70 |
68 |
49 |
||
5 |
9 |
9 |
|
|
|
9 |
|
9,10 |
74 |
70 |
37 |
25 |
85 |
68 |
121 |
||
12 |
|
|
10 |
|
|
|
9,10 |
|
100 |
64 |
85 |
107 |
82 |
49 |
121 |