Материал: 1997
На первом шаге текущее дерево состоит из одной вершины 1. рассмотрим вершины соседние с текущим деревом, для данного примеры это будут вершины 2,7 и 8. Присваиваем этим вершинам «временную пометку», для этого определяем потенциалы этих вершин путем «просмотра» вершины 1. Записываем значения потенциалов для каждой из вершин:
|
min( ;0 4) 4 |
; |
|
|
|
|
L12 |
|
|
|
|||
|
min( ;0 7) 7 |
; |
|
|
|
|
L17 |
|
|
|
|||
|
min( ;0 8) 8. |
|
|
|
||
L18 |
|
|
|
|||
Постоянную пометку получает та вершина, которая имеет мини- |
||||||
становится |
|
|
|
|||
мальное значен е потенциала, т.е. 2-ая вершина |
L12 L12 |
4. Таким |
||||
Собразом ребро 1-2 |
|
|
ребром текущего дерева. |
|
||
|
1 |
2 |
(4;1) |
|
|
|
На втором шаге текущее дерево уже будет состоять из вершины 1 и 2 ребра, соед няющего эти вершины. Рассмотрим вершины соседние с текущ м деревом: 4,7,8. Присваиваем этим вершинам «временную пометку», для этого определяем потенциалы этих вершин путем «про-
смотра»:
ПостояннуюбАпометку получает вершина 4 (в данном случае две
|
min( ;4 3) 7; |
L14 |
|
|
min(7;4 5) 7; |
L17 |
|
|
min(8;4 ) 8. |
L18 |
вершины имеют одинаковое минимальное значение потенциала, можно
выбрать любую), т.е. |
|
7. Таким образом ребро 2-4 добавляет- |
|
L14 L14 |
|||
ся к текущему дереву. |
|
И |
|
1 |
|
||
|
Д2 (4;1) |
||
|
|
4 |
(7;2) |
На третьем шаге по тому же алгоритму получаем следующие значения потенциалов для вершин соседних с текущем деревом:
|
min( ;7 4) 11; |
|
|
|
|
L13 |
1 |
|
2 (4;1) |
|
|
|
min( ;7 3) 10; |
|
|
||
L15 |
|
|
|
|
|
|
min( ;7 1) 8; |
|
|
|
|
L16 |
|
4 |
(7;2) |
||
|
min(7;7 2) 7; |
|
|||
|
7 (7;1) |
|
|||
L17 |
|
|
|||
|
min(8;7 ) 8. |
|
|
|
|
L18 |
|
|
|
|
|
16
|
|
|
7. |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||
L17 L17 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||||
4-й шаг |
|
|
|
|
1 |
|
|
|
|
2 (4;1) |
|
|
|
|
|
|
|
|
||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||||||
|
|
min(11;7 ) 11; |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||
L13 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||||
|
|
min(10;7 ) 10; |
|
|
|
|
|
|
|
|
|
|
4 |
|
|
(7;2) |
|
|
||||||
L15 |
|
|
|
|
7 (7;1) |
|
|
|
|
|
|
|||||||||||||
|
|
min(8;7 4) 8; |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||||||||
L16 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||||
С13 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
L110 min( ;7 5) 12; |
|
|
|
|
|
|
|
|
|
|
6 |
(8;4) |
|
|
||||||||||
|
|
min( ;7 6) 13; |
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||||||
L19 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||||
|
|
min(8;7 3) 8. |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||
L18 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||||
|
|
|
8. |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||
L16 L16 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||||
5-й шаг |
|
|
|
|
1 |
|
|
|
|
2 |
(4;1) |
|
|
|
|
|
|
|
||||||
L |
|
min(11;8 ) 11; |
|
|
|
|
|
|
|
|
|
|
|
|||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||||
|
min(10;8 ) 10; |
|
|
|
|
|
|
|
|
|
|
|
4 |
(7;2) |
|
|||||||||
L15 |
|
|
|
|
7 |
|
|
|
|
|
||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
(7;1) |
|
|
|
|
|
|
|
|
|
|||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||
L110 min(12;8 2) 10; |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||||||
15 |
бА15 |
|
|
|
|
|
|
|
|
|
||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
L19 |
min(13;8 ) 13; |
8 (8;1) |
|
|
|
|
|
|
|
6 |
(8;4) |
|
||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||
иL min(8;8 ) 8. |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||||
18 |
|
|
8. |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||
L18 L18 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||||
6-й шаг |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||
|
|
min(11;8 ) 11; |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||
L13 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||||
|
|
min(10;8 ) 10; |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||
L15 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
L110 min(10;8 ) 10; |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||||
|
|
min(13;8 ) 13 |
Д4 |
|
|
|
|
|||||||||||||||||
L19 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||||
L |
|
L |
|
10. |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||
|
|
|
|
|
1 |
|
2 |
(4;1) |
|
|
И |
|||||||||||||
|
|
|
|
|
|
|
|
|||||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|||||||||||||
|
|
|
|
|
7 |
(7;1) |
|
|
|
(7;2) |
|
|
|
|
|
|
|
|
|
|||||
|
|
|
|
8 |
|
|
|
|
|
|
5 |
(10;4) |
|
|
|
|
|
|
||||||
|
|
|
|
(8;1) |
|
6 |
|
|
|
|
|
|
|
|
|
|||||||||
|
|
|
|
|
(8;4) |
|
|
|
|
|
|
|||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||||
7-й шаг |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||
|
|
min(11;10 2) 11; |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||
L13 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
L110 min(10;10 ) 10; |
1 |
|
|
|
|
2 (4;1) |
|
|
|
|
|
|
|
|
|
|||||||||
|
|
min(13;10 ) 13 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||||||||
L19 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||||
L10 |
|
|
10. |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||
L10 |
|
|
|
|
|
|
|
|
|
|
4 |
|
(7;2) |
|
|
|||||||||
|
|
|
|
|
|
|
|
7 |
(7;1) |
|
|
|
|
|
||||||||||
|
|
|
|
|
|
|
8 |
|
|
|
|
|
|
|
|
5 |
(10;4) |
|||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||||||||
|
|
|
|
|
|
|
(8;1) |
|
|
|
|
|
|
6 |
|
|
|
|
|
|||||
|
|
|
|
|
|
|
|
|
|
|
|
|
(8;4) |
|||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||||
|
|
|
|
|
|
|
|
17 |
|
|
|
|
|
|
|
|
|
|
|
|
10 |
(10;6) |
||
8-й шаг
L13 min(11;10 ) 11; L19 min(13;10 7) 13
|
|
|
|
|
11. |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||
|
L13 L13 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||||
С |
1 |
|
|
|
|
2 |
(4;1) |
|
|
|
|
|
3 |
|
(11;4) |
|
|
|
|
||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||
|
|
|
|
|
|
|
|
|
|
7 |
(7;1) |
|
|
|
4 |
(7;2) |
|
|
|
|
|
|
|
|
|||||
|
|
|
|
|
|
8 |
(8;1) |
|
|
|
|
|
|
|
|
5 |
(10;4) |
|
|
|
|
||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||||||
и |
|
|
|
|
|
6 |
(8;4) |
|
|
|
|
|
|
|
|
|
|||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||
|
9-й шаг |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
10 |
(10;6) |
|
|
|
|
|
||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||
|
|
min(13;11 ) 13 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||||||
|
L19 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||||||||
|
|
бА |
|
|
|
|
|
|
|
|
|
||||||||||||||||||
|
|
|
|
|
13. |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||
|
L19 L19 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||||
|
|
|
|
|
|
|
|
1 |
|
|
|
|
2 |
(4;1) |
|
|
|
|
|
|
3 |
|
(11;4) |
|
|
||||
|
|
|
|
|
|
|
|
|
|
|
|
7 |
(7;1) |
|
|
4 |
|
|
(7;2) |
|
|
|
|
|
|
|
|||
|
|
|
|
|
|
|
|
8 |
(8;1) |
9 |
|
(13;7) |
|
6 |
|
|
(8;4) |
|
5 |
(10;4) |
|
|
|||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||||
|
|
|
|
|
|
|
|
|
|
|
|
Д |
|
|
|
||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
10 |
(10;6) |
|
|
|
||
|
|
|
|
|
|
|
Компактная запись дерева кратчайших путей |
Таблица 4 |
|||||||||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
из вершины 1 во все другие |
|
|
|
|
|
|
|
|
||||||||||
|
Номер |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
И |
|
|
|||||||
|
вершины |
|
|
1 |
|
|
|
2 |
|
3 |
4 |
|
|
5 |
|
6 |
|
|
7 |
|
|
8 |
|
|
9 |
10 |
|
||
|
Расстояние |
|
- |
|
|
|
4 |
|
11 |
7 |
|
|
10 |
|
8 |
|
|
7 |
|
|
8 |
|
|
13 |
10 |
|
|||
|
Номер со- |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
седней |
|
|
- |
|
|
|
1 |
|
4 |
2 |
|
|
4 |
|
4 |
|
|
1 |
|
|
1 |
|
|
7 |
6 |
|
||
|
вершины |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Данная таблица позволяет определить путь по кратчайшему расстоянию из 1 вершины в любую другую вершину графа.
Например из 1 в 6: 6-4-2-1.
18
Задание 1. Построить дерево кратчайших путей по вариантам заданным в таблице 5.
|
|
|
|
Таблица 5 |
|
С |
|
Варианты заданий для построения |
|||
|
дерева кратчайших путей |
||||
Вариант |
Номер схемы |
Исходная вершина |
|
||
|
|
||||
|
1 |
|
1 |
1 |
|
|
2 |
|
2 |
2 |
|
|
3 |
|
3 |
3 |
|
|
4 |
|
4 |
4 |
|
и |
|
5 |
5 |
|
|
5 |
|
|
|||
|
6 |
|
1 |
6 |
|
|
7 |
|
2 |
7 |
|
|
8 |
|
3 |
1 |
|
бА |
|
||||
9 |
|
4 |
2 |
|
|
|
10 |
|
5 |
3 |
|
|
11 |
|
1 |
4 |
|
|
12 |
|
3 |
5 |
|
|
13 |
|
2 |
6 |
|
|
14 |
|
4 |
7 |
|
|
15 |
|
5 |
1 |
|
|
16 |
|
1 |
2 |
|
Схемы для выполнения задания приведены в приложении 2.
Задание 2. Описать траекторию движения автобусного маршрута используя граф транспортной сети сформированный в программном
комплексе АРМ «МАРС». |
И |
Варианты для выполнения задания приведены в таблице, описание |
|
маршрутов – приложение 3. |
Д |
19
|
|
|
Таблица 6 |
Варианты заданий для формирования маршрутов |
|||
|
Вариант |
Номер маршрута |
|
|
1 |
1,5 |
|
С |
2 |
2,6 |
|
3 |
3,1 |
|
|
4 |
4,2 |
|
|
5 |
5,3 |
|
|
6 |
6,4 |
|
|
7 |
1,3 |
|
|
8 |
2,4 |
|
|
9 |
3,5 |
|
|
10 |
4,6 |
|
|
11 |
5,2 |
|
|
и |
12 |
6,3 |
|
13 |
1,4 |
|
|
14 |
2,5 |
|
|
15 |
3,6 |
|
|
16 |
4,1 |
|
|
В имеющемсябАсписке введено 246 маршрутов. Вводить создаваемые маршруты рекомендуется под программными номерами незадействованными в «существующей» маршрутной сети. Установив курсов на свободном программном номере в поле 1 (рис. 8) через запятую без пробелов вводятся номера вершин транспортных узлов через которые
Указан я к выполнению задания 2.
Задание выполняется в программном комплексе АРМ «МАРС» с
использованием закладки «Ввод данных расчеты» + «Маршрутная сеть» + «Вводимая».
будет проходить планируемыйДмаршрут.
Ввод вершин графа начинается с конечного пункта в прямом направлении маршрута, далее последовательно перечисляются все смежные узлы транспортной сети до конечно пункта в прямом направлении маршрута. Затем продолжается ввод транспортных узлов для обратного направления движения по маршруту. Список транспортных узлов, через
которые проходит маршрут, обязательно должен заканчиваться «запя- |
|
той». |
И |
|
|
Для сохранения введенных транспортных узлов для данного маршрута требуется нажать кнопку «Ввод остановок» после чего в поле 2 автоматически появится количество введенных остановок маршрута (транспортных узлов).
20