2 Определение расстояний перевозки
2.1 Пункты отправления — пункты назначения (первый вид транспорта)
Как следует из исходных данных, каждый пункт назначения связан с каждым пунктом отправления единственным прямым маршрутом. Следовательно, расстояния между этими пунктами совпадают с расстояниями, приведёнными в матрице расстояний между пунктами (таблица 1).
Таблица 1 – Расстояния между пунктами отправления и назначения
Расстояние, км |
Пункты назначения | ||||||||
В1 |
В2 |
В3 |
В4 | ||||||
Пункты отправления |
А1 |
112 |
102 |
90 |
76 | ||||
А2 |
128 |
119 |
108 |
95 | |||||
А3 |
144 |
136 |
126 |
114 | |||||
A4 |
160 |
153 |
144 |
133 |
2.2 Пункты взаимодействия — пункты назначения (второй вид транспорта)
Как следует из исходных данных, каждый пункт назначения связан с каждым пунктом взаимодействия единственным прямым маршрутом. Следовательно, расстояния между этими пунктами совпадают с расстояниями, приведёнными в матрице расстояний между пунктами (таблица 2).
Таблица 2 – Расстояния между пунктами взаимодействия и назначения
Расстояние, км |
Пункты назначения | ||||
В1 |
В2 |
В3 |
В4 | ||
Пункты взаимодействия |
D1 |
64 |
51 |
36 |
19 |
D2 |
80 |
68 |
54 |
38 | |
D3 |
96 |
85 |
72 |
57 |
2.3 Пункты отправления - пункты взаимодействия (первый вид транспорта)
Из матрицы расстояний видно, что прямых маршрутов между пунктами Ak (k=1…4) отправления и пунктами Di (i=2,3) взаимодействия нет. Необходимо построить кратчайшие маршруты, пролегающие через промежуточные пункты Еs (s=1…9), и определить длины этих маршрутов.
Сформируем матрицу расстояний между пунктами Аk отправления, промежуточными пунктами Еs. пунктами Di взаимодействия; введём сквозную нумерацию узлов (таблица 3).
Таблица 3 – Матрица расстояний между пунктами отправления,
взаимодействия и промежуточными пунктами
Пункты |
А1 |
А2 |
А3 |
A4 |
E1 |
E2 |
E3 |
E4 |
E5 |
E6 |
E7 |
E8 |
E9 |
D2 |
D3 | |||||||||||||||||||
|
Узлы |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
10 |
11 |
12 |
13 |
14 |
15 | ||||||||||||||||||
А1 |
1 |
|
|
|
|
|
|
8 |
34 |
|
|
|
|
|
|
| ||||||||||||||||||
А2 |
2 |
|
|
|
|
5 |
|
|
44 |
4 |
|
|
|
|
|
| ||||||||||||||||||
А3 |
3 |
|
|
|
|
|
56 |
|
|
11 |
23 |
|
|
|
|
| ||||||||||||||||||
A4 |
4 |
|
|
|
|
|
|
|
|
|
|
|
11 |
|
|
| ||||||||||||||||||
E1 |
5 |
|
5 |
|
|
|
|
|
|
|
|
45 |
|
|
|
| ||||||||||||||||||
E2 |
6 |
|
|
56 |
|
|
|
|
|
68 |
|
|
56 |
|
4 |
| ||||||||||||||||||
E3 |
7 |
8 |
|
|
|
|
|
|
12 |
|
|
13 |
|
|
|
| ||||||||||||||||||
E4 |
8 |
34 |
44 |
|
|
|
|
12 |
|
18 |
|
32 |
|
|
5 |
| ||||||||||||||||||
E5 |
9 |
|
4 |
11 |
|
|
68 |
|
18 |
|
2 |
|
10 |
12 |
|
| ||||||||||||||||||
E6 |
10 |
|
|
23 |
|
|
|
|
|
2 |
|
|
|
8 |
|
9 | ||||||||||||||||||
E7 |
11 |
|
|
|
|
45 |
|
13 |
32 |
|
|
|
4 |
|
3 |
| ||||||||||||||||||
E8 |
12 |
|
|
|
11 |
|
56 |
|
|
10 |
|
4 |
|
9 |
|
9 | ||||||||||||||||||
E9 |
13 |
|
|
|
|
|
|
|
|
12 |
8 |
|
9 |
|
|
| ||||||||||||||||||
D2 |
14 |
|
|
|
|
|
4 |
|
5 |
|
|
3 |
|
|
|
| ||||||||||||||||||
D3 |
15 |
|
|
|
|
|
|
|
|
|
9 |
|
9 |
|
|
|
2.3.1 Пункт D2
Построим маршруты в узел 14 (пункт D2) из узлов 1 (пункт A1), 2 (пункт А2), 3 (пункт А3) и 4 (пункт А4).
Приближение k=0.
Определим длины прямых (без посещения промежуточных узлов) маршрутов в узел 14. Для каждого j-го узла (j = 6, 8, 11), который соединен дугой с узлом 14 (т.е. имеется прямой маршрут), длина U0j кратчайшего маршрута принимается равной расстоянию Lj-14 между этим узлом и узлом 14; для остальных узлов значения U0j принимаются равными бесконечности:
U06 = L6-14 = 4;
U08 = L8-14 = 5;
U011 = L11-14 = 3.
Полученные маршруты и значения их длин U0j занесем в таблицу 8.
Определим длины прямых (без посещения промежуточных узлов) маршрутов в узел 14. Для каждого j-гo узла (j = 11, 12), который соединён дугой с узлом 14 (т.е. имеется прямой маршрут), длина U0j кратчайшего маршрута принимается равной расстоянию Lj-14 между этим узлом и узлом 14; для остальных узлов значения Uj принимаются равными бесконечности:
U11 = L11-14= 28;U12 = L12-14=27.
Полученные маршруты и значения их длин U0jзанесём в таблицу 7.
Приближение k=1.
Определим длину L1i-j возможного маршрута из i-гo узла в узел 14, проходящего через j-й узел, с числом промежуточных узлов не более одного как сумму расстояния Li-j от i-гo узла до j-гo узла и длины U0j прямого маршрута из этого узла в узел 14:
L1i-j = Li-j + U0j, i= 1, 2, …15, j = 1,2, …15,i≠14,i≠14, i≠j.
В качестве длины кратчайшего маршрута из i-гo узла в узел 14 принимается минимальное из возможных значений:
U1s = min{L1i-j}.
Таблица 4 – Маршруты в узел 14 с числом промежуточных узлов не более одного
Из узла 1 |
j |
L1-j |
U0j |
L11-j |
U11 |
1- 8-14 |
8 |
34 |
5 |
39 |
39 |
Из узла 2 |
j |
L2-j |
U0j |
L12-j |
U12 |
2- 8-14 |
8 |
44 |
5 |
49 |
49 |
Из узла 3 |
j |
L3-j |
U0j |
L13-j |
U13 |
3- 6-14 |
6 |
56 |
4 |
60 |
60 |
Из узла 5 |
j |
L5-j |
U0j |
L15-j |
U15 |
5- 11-14 |
11 |
45 |
3 |
48 |
48 |
Из узла 6 |
j |
L6-j |
U0j |
L16-j |
U16 |
6- 14 |
14 |
4 |
|
4 |
4 |
Из узла 7 |
J |
L7-j |
U0j |
L17-j |
U17 |
7- 8-14 |
8 |
12 |
5 |
17 |
|
7- 11-14 |
11 |
13 |
3 |
16 |
16 |
Из узла 8 |
j |
L8-j |
U0j |
L18-j |
U18 |
8- 11-14 |
11 |
32 |
3 |
35 |
|
8- 14 |
14 |
5 |
|
5 |
5 |
Из узла 9 |
j |
L9-j |
U0j |
L19-j |
U19 |
9- 6-14 |
6 |
68 |
4 |
72 |
|
9- 8-14 |
8 |
18 |
5 |
23 |
23 |
Из узла 11 |
j |
L11-j |
U0j |
L111-j |
U111 |
11- 8-14 |
8 |
32 |
5 |
37 |
|
11- 14 |
14 |
3 |
|
3 |
3 |
Из узла 12 |
j |
L12-j |
U0j |
L112-j |
U112 |
12- 6-14 |
6 |
56 |
4 |
60 |
|
12- 11-14 |
11 |
4 |
3 |
7 |
7 |
Полученные кратчайшие маршруты из каждого узла в узел 14 и значения их длин U1j (выделены заливкой) занесём в таблицу 8.
Приближение k=2.
Определим длину L2i-j возможного маршрута из i-гo узла в узел 14, проходящего через j-й узел, с числом промежуточных узлов не более двух как сумму расстояния Li-j от i-гo узла до j-ro узла и длины U1j маршрута из j-гo узла в узел 14 с числом узлов не более одного:
L2i-j = Li-j + U1j, i = 1, 2, …15, j = 1,2, … 15, i≠14, i≠14, i≠j.
В качестве длины кратчайшего маршрута из i-гo узла в узел 14 принимается минимальное значение из возможных:
U2j = min {L2i-j}.
Таблица 5 – Маршруты в узел 14 с числом промежуточных узлов не более двух
Из узла 1 |
j |
L1-j |
U1j |
L21-j |
U21 |
1- 7-11-14 |
7 |
8 |
16 |
24 |
24 |
1- 8-14 |
8 |
34 |
5 |
39 |
|
Из узла 2 |
j |
L2-j |
U1j |
L22-j |
U22 |
2- 5-11-14 |
5 |
5 |
48 |
53 |
|
2- 8-14 |
8 |
44 |
5 |
49 |
|
2- 9-8-14 |
9 |
4 |
23 |
27 |
27 |
Из узла 3 |
j |
L3-j |
U1j |
L23-j |
U23 |
3- 6-14 |
6 |
56 |
4 |
60 |
|
3- 9-8-14 |
9 |
11 |
23 |
34 |
34 |
Из узла 4 |
j |
L4-j |
U1j |
L24-j |
U24 |
4- 12-11-14 |
12 |
11 |
7 |
18 |
18 |
Из узла 5 |
j |
L5-j |
U1j |
L25-j |
U25 |
5- 2-8-14 |
2 |
5 |
49 |
54 |
|
5- 11-14 |
11 |
45 |
3 |
48 |
48 |
Из узла 6 |
j |
L6-j |
U1j |
L26-j |
U26 |
6- 3-6-14 |
3 |
56 |
60 |
116 |
|
6- 9-8-14 |
9 |
68 |
23 |
91 |
|
6- 12-11-14 |
12 |
56 |
7 |
63 |
|
6- 14 |
14 |
4 |
|
4 |
4 |
Из узла 7 |
j |
L7-j |
U1j |
L27-j |
U27 |
7- 1-8-14 |
1 |
8 |
39 |
47 |
|
7- 8-14 |
8 |
12 |
5 |
17 |
|
7- 11-14 |
11 |
13 |
3 |
16 |
16 |
Из узла 8 |
j |
L8-j |
U1j |
L28-j |
U28 |
8- 7-11-14 |
7 |
12 |
16 |
28 |
|
8- 11-14 |
11 |
32 |
3 |
35 |
|
8- 14 |
14 |
5 |
|
5 |
5 |
Из узла 9 |
j |
L9-j |
U1j |
L29-j |
U29 |
9- 2-8-14 |
2 |
4 |
49 |
53 |
|
9- 3-6-14 |
3 |
11 |
60 |
71 |
|
9- 6-14 |
6 |
68 |
4 |
72 |
|
9- 8-14 |
8 |
18 |
5 |
23 |
23 |
9- 12-11-14 |
12 |
10 |
7 |
17 |
17 |
Из узла 10 |
j |
L10-j |
U1j |
L210-j |
U210 |
10- 3-6-14 |
3 |
23 |
60 |
83 |
|
10- 9-8-14 |
9 |
2 |
23 |
25 |
25 |
Из узла 11 |
j |
L11-j |
U1j |
L211-j |
U211 |
11- 8-14 |
8 |
32 |
5 |
37 |
|
11- 14 |
14 |
3 |
|
3 |
3 |
Из узла 12 |
j |
L12-j |
U1j |
L212-j |
U212 |
12- 6-14 |
6 |
56 |
4 |
60 |
|
12- 9-8-14 |
9 |
10 |
23 |
33 |
|
12- 11-14 |
11 |
4 |
3 |
7 |
7 |
Из узла 13 |
j |
L13-j |
U1j |
L213-j |
U213 |
13- 9-8-14 |
9 |
12 |
23 |
35 |
|
13- 12-11-14 |
12 |
9 |
7 |
16 |
16 |
Из узла 15 |
j |
L15-j |
U1j |
L215-j |
U215 |
15- 12-11-14 |
12 |
9 |
7 |
16 |
16 |
Полученные кратчайшие маршруты из каждого узла в узел 14 и значения их длин U2j (выделены заливкой) занесём в таблицу 8.
Приближение k=3.
Определим длину L3i-j возможного маршрута из i-гo узла в узел 14, проходящего через j-й узел, с числом промежуточных узлов не более трёх как сумму расстояния Li-j от i-гo узла до j-гo узла и длины U2j маршрута из j-гo узла в узел 14 с числом узлов не более двух:
L3s-j = Li-j + U2j,i = 1, 2, …15, j = 1,2, … 15, i≠14, i≠14, i≠j.
В качестве длины кратчайшего маршрута из i-гo узла в узел 14 принимается минимальное из возможных значение:
U3j = min {L3i-j}.
Таблица 6 – Маршруты в узел 14 с числом промежуточных узлов не более трех
Из узла 1 |
j |
L1-j |
U2j |
L31-j |
U31 |
1- 7-11-14 |
7 |
8 |
16 |
24 |
24 |
1- 8-14 |
8 |
34 |
5 |
39 |
|
Из узла 2 |
j |
L2-j |
U2j |
L32-j |
U32 |
2- 5-11-14 |
5 |
5 |
48 |
53 |
|
2- 8-14 |
8 |
44 |
5 |
49 |
|
2- 9-12-11-14 |
9 |
4 |
17 |
21 |
21 |
Из узла 3 |
j |
L3-j |
U2j |
L33-j |
U33 |
3- 6-14 |
6 |
56 |
4 |
60 |
|
3- 9-12-11-14 |
9 |
11 |
17 |
28 |
28 |
3- 10-9-8-14 |
10 |
23 |
25 |
48 |
|
Из узла 4 |
j |
L4-j |
U2j |
L34-j |
U34 |
4- 12-11-14 |
12 |
11 |
7 |
18 |
18 |
Из узла 5 |
j |
L5-j |
U2j |
L35-j |
U35 |
5- 2-9-8-14 |
2 |
5 |
27 |
32 |
32 |
5- 11-14 |
11 |
45 |
3 |
48 |
|
Из узла 6 |
j |
L6-j |
U2j |
L36-j |
U36 |
6- 3-9-8-14 |
3 |
56 |
34 |
90 |
|
6- 9-12-11-14 |
9 |
68 |
17 |
85 |
|
6- 12-11-14 |
12 |
56 |
7 |
63 |
|
6- 14 |
14 |
4 |
|
4 |
4 |
Из узла 7 |
j |
L7-j |
U2j |
L37-j |
U37 |
7- 8-14 |
8 |
12 |
5 |
17 |
|
7- 11-14 |
11 |
13 |
3 |
16 |
16 |
Из узла 8 |
j |
L8-j |
U2j |
L38-j |
U38 |
8- 1-7-11-14 |
1 |
34 |
24 |
58 |
|
8- 2-9-8-14 |
2 |
44 |
27 |
71 |
|
8- 7-11-14 |
7 |
12 |
16 |
28 |
|
8- 9-12-11-14 |
9 |
18 |
17 |
35 |
|
8- 11-14 |
11 |
32 |
3 |
35 |
|
8- 14 |
14 |
5 |
|
5 |
5 |
Из узла 9 |
j |
L9-j |
U2j |
L39-j |
U39 |
9- 6-14 |
6 |
68 |
4 |
72 |
|
9- 8-14 |
8 |
18 |
5 |
23 |
|
9- 12-11-14 |
12 |
10 |
7 |
17 |
17 |
9- 13-12-11-14 |
13 |
12 |
16 |
28 |
|
Из узла 10 |
j |
L10-j |
U2j |
L310-j |
U310 |
10- 3-9-8-14 |
3 |
23 |
34 |
57 |
|
10- 9-12-11-14 |
9 |
2 |
17 |
19 |
19 |
10- 13-12-11-14 |
13 |
8 |
16 |
24 |
|
10- 15-12-11-14 |
15 |
9 |
16 |
25 |
|
Из узла 11 |
j |
L11-j |
U2j |
L311-j |
U311 |
11- 8-14 |
8 |
32 |
5 |
37 |
|
11- 14 |
14 |
3 |
|
3 |
3 |
Из узла 12 |
j |
L12-j |
U2j |
L312-j |
U312 |
12- 6-14 |
6 |
56 |
4 |
60 |
|
12- 11-14 |
11 |
4 |
3 |
7 |
7 |
Из узла 13 |
j |
L13-j |
U2j |
L313-j |
U313 |
13- 9-12-11-14 |
9 |
12 |
17 |
29 |
|
13- 10-9-8-14 |
10 |
8 |
25 |
33 |
|
13- 12-11-14 |
12 |
9 |
7 |
16 |
16 |
Из узла 15 |
j |
L15-j |
U2j |
L315-j |
U315 |
15- 10-9-8-14 |
10 |
9 |
25 |
34 |
|
15- 12-11-14 |
12 |
9 |
7 |
16 |
16 |
Полученные кратчайшие маршруты из каждого узла в узел 14 и значения их длин U3j (выделены заливкой) занесём в таблицу 8.
Приближение k=4.
Определим длину L4i-j возможного маршрута из i-го узла в узел 14, проходящего через j-й узел, с числом промежуточных узлов не более четырех как сумму расстояния Li-j от i-го узла до j-го узла и длины U3j маршрута из j-го узла в узел 14 с числом узлов не более трех:
L4i-j = Li-j + U3j , i = 1, 2, ... 15, j = 1, 2, ... 15, i ≠ 14, j ≠ 14, j ≠ i.
В качестве длины кратчайшего маршрута из i-го узла в узел 14 принимается минимальное значение из возможных:
U4j = min {L4i-j}.
Таблица 7 – Маршруты в узел 14 с числом промежуточных узлов не более четырех
Из узла 1 |
j |
L1-j |
U3j |
L41-j |
U41 |
1- 7-11-14 |
7 |
8 |
16 |
24 |
24 |
1- 8-14 |
8 |
34 |
5 |
39 |
|
Из узла 2 |
j |
L2-j |
U3j |
L42-j |
U42 |
2- 5-2-9-8-14 |
5 |
5 |
32 |
37 |
|
2- 8-14 |
8 |
44 |
5 |
49 |
|
2- 9-12-11-14 |
9 |
4 |
17 |
21 |
21 |
Из узла 3 |
j |
L3-j |
U3j |
L43-j |
U43 |
3- 6-14 |
6 |
56 |
4 |
60 |
|
3- 9-12-11-14 |
9 |
11 |
17 |
28 |
28 |
3- 10-9-12-11-14 |
10 |
23 |
19 |
42 |
|
Из узла 4 |
j |
L4-j |
U3j |
L44-j |
U44 |
4- 12-11-14 |
12 |
11 |
7 |
18 |
18 |
Из узла 5 |
j |
L5-j |
U3j |
L45-j |
U45 |
5- 2-9-12-11-14 |
2 |
5 |
21 |
26 |
26 |
5- 11-14 |
11 |
45 |
3 |
48 |
|
Из узла 6 |
j |
L6-j |
U3j |
L46-j |
U46 |
6- 3-9-12-11-14 |
3 |
56 |
28 |
84 |
|
6- 9-12-11-14 |
9 |
68 |
17 |
85 |
|
6- 12-11-14 |
12 |
56 |
7 |
63 |
|
6- 14 |
14 |
4 |
|
4 |
4 |
Из узла 7 |
j |
L7-j |
U3j |
L47-j |
U47 |
7- 8-14 |
8 |
12 |
5 |
17 |
|
7- 11-14 |
11 |
13 |
3 |
16 |
16 |
Из узла 8 |
j |
L8-j |
U3j |
L48-j |
U48 |
8- 1-7-11-14 |
1 |
34 |
24 |
58 |
|
8- 2-9-12-11-14 |
2 |
44 |
21 |
65 |
|
8- 7-11-14 |
7 |
12 |
16 |
28 |
|
8- 9-12-11-14 |
9 |
18 |
17 |
35 |
|
8- 11-14 |
11 |
32 |
3 |
35 |
|
8- 14 |
14 |
5 |
|
5 |
5 |
Из узла 9 |
j |
L9-j |
U3j |
L49-j |
U49 |
9- 6-14 |
6 |
68 |
4 |
72 |
|
9- 8-14 |
8 |
18 |
5 |
23 |
|
9- 12-11-14 |
12 |
10 |
7 |
17 |
17 |
9- 13-12-11-14 |
13 |
12 |
16 |
28 |
|
Из узла 10 |
j |
L10-j |
U3j |
L410-j |
U410 |
10- 3-9-12-11-14 |
3 |
23 |
28 |
51 |
|
10- 9-12-11-14 |
9 |
2 |
17 |
19 |
19 |
10- 13-12-11-14 |
13 |
8 |
16 |
24 |
|
10- 15-12-11-14 |
15 |
9 |
16 |
25 |
|
Из узла 11 |
j |
L11-j |
U3j |
L411-j |
U411 |
11- 5-2-9-8-14 |
5 |
45 |
32 |
77 |
|
11- 8-14 |
8 |
32 |
5 |
37 |
|
11- 14 |
4 |
3 |
|
3 |
3 |
Из узла 12 |
j |
L12-j |
U3j |
L412-j |
U412 |
12- 6-14 |
6 |
56 |
4 |
60 |
|
12- 11-14 |
11 |
4 |
3 |
7 |
7 |
Из узла 13 |
j |
L13-j |
U3j |
L413-j |
U413 |
13- 9-12-11-14 |
9 |
12 |
17 |
29 |
|
13- 10-9-12-11-14 |
10 |
8 |
19 |
27 |
|
13- 12-11-14 |
12 |
9 |
7 |
16 |
16 |
Из узла 15 |
j |
L15-j |
U3j |
L415-j |
U415 |
15- 10-9-12-11-14 |
10 |
9 |
19 |
28 |
|
15- 12-11-14 |
12 |
9 |
7 |
16 |
16 |
Приближение k=5
Определим длину L5i-j возможного маршрута из i-го узла в узел 14, проходящего через j-й узел, с числом промежуточных узлов не более пяти как сумму расстояния Li-j от i-го узла до j-го узла и длины U4j маршрута из j-го узла в узел 14 с числом узлов не более четырех:
L5i-j = Li-j + U4j , i = 1, 2, ... 15, j = 1, 2, ... 15, i ≠ 14, j ≠ 14, j ≠ i.
В качестве длины кратчайшего маршрута из i-го узла в узел 14 принимается минимальное значение из возможных:
U5j = min {L5i-j}.
Результаты расчетов показывают, что длины кратчайших маршрутов U5j с числом промежуточных узлов не более пяти оказываются равными длинам кратчайших маршрутов U4i с числом промежуточных узлов не более четырех. В связи с этим дальнейшие расчеты прекращаются.
В таблице 8 для каждого приближения приведены полученные кратчайшие маршруты в узел 14 и их длины.
Таблица 8 – Кратчайшие маршруты в узел 14
J |
k=0 |
k=1 |
k=2 |
k=3 |
k=4 | |||||||||
Маршрут |
U0j |
Маршрут |
U1j |
Маршрут |
U2j |
Маршрут |
U3j |
Маршрут |
U4j | |||||
1 |
|
|
1-8-14 |
39 |
1-7-11-14 |
24 |
1-7-11-14 |
24 |
1-7-11-14 |
24 | ||||
2 |
|
|
2-8-14 |
49 |
2-9-8-14 |
27 |
2-9-12-11-14 |
21 |
2-9-12-11-14 |
21 | ||||
3 |
|
|
3-6-14 |
60 |
3-9-8-14 |
34 |
3-9-12-11-14 |
28 |
3-9-12-11-14 |
28 | ||||
4 |
|
|
|
|
4-12-11-14 |
18 |
4-12-11-14 |
18 |
4-12-11-14 |
18 | ||||
5 |
|
|
5-11-14 |
48 |
5-11-14 |
48 |
5-2-9-8-14 |
32 |
5-2-9-12-11-14 |
26 | ||||
6 |
6-14 |
4 |
6-14 |
4 |
6-14 |
4 |
6-14 |
4 |
6-14 |
4 | ||||
7 |
|
|
7-11-14 |
16 |
7-11-14 |
16 |
7-11-14 |
16 |
7-11-14 |
16 | ||||
8 |
8-14 |
5 |
8-14 |
5 |
8-14 |
5 |
8-14 |
5 |
8-14 |
5 | ||||
9 |
|
|
9-8-14 |
23 |
9-12-11-14 |
17 |
9-12-11-14 |
17 |
9-12-11-14 |
17 | ||||
10 |
|
|
|
|
10-9-8-14 |
25 |
10-9-12-11-14 |
19 |
10-9-12-11-14 |
19 | ||||
11 |
11-14 |
3 |
11-14 |
3 |
11-14 |
3 |
11-14 |
3 |
11-14 |
3 | ||||
12 |
|
|
12-11-14 |
7 |
12-11-14 |
7 |
12-11-14 |
7 |
12-11-14 |
7 | ||||
13 |
|
|
|
|
13-12-11-14 |
16 |
13-12-11-14 |
16 |
13-12-11-14 |
16 | ||||
15 |
|
|
|
|
15-12-11-14 |
16 |
15-12-11-14 |
16 |
15-12-11-14 |
16 |
Искомые кратчайшие маршруты в узел 14 (пункт D2)
из узла 1 (пункт А1): 1-7-11-14 (А1-Е3-Е7-Е6-D2); расстояние перевозки 24;
из узла 2 (пункт А2): 2-9-12-11-14 (A2-E5- E8-E7-D2); расстояние перевозки 21;
из узла 3 (пункт А3): 3-9-12-11-14 (A3- E5- E8-E7-D2); расстояние перевозки 28;
из узла 4 (пункт А4): 4-12-11-14 (A4- E8-E7-D2); расстояние перевозки 18.