6. Решение задачи аналитическим методом
Обозначим через di,jm длину кратчайшего пути из вершины i в вершину j, который в качестве промежуточных может содержать только первые m вершин графа.
На основании исходных данных формируем матрицу длин кратчайших дуг D0 (Таблица 1), каждый элемент которой равен длине кратчайшей дуги между вершинами i и j. Если такой дуги нет, положим значение элемента равным ?.
Таблица 1- Матрица D0
D0= |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
||
1 |
0 |
1 |
5 |
9 |
9 |
? |
? |
? |
||
2 |
1 |
0 |
1 |
? |
? |
1 |
? |
? |
||
3 |
5 |
1 |
0 |
? |
? |
2 |
? |
1 |
||
4 |
9 |
? |
? |
0 |
9 |
? |
5 |
? |
||
5 |
9 |
? |
? |
9 |
0 |
? |
4 |
4 |
||
6 |
? |
1 |
2 |
? |
? |
0 |
? |
5 |
||
7 |
? |
? |
? |
5 |
4 |
? |
0 |
8 |
||
8 |
? |
? |
1 |
? |
4 |
5 |
8 |
0 |
Представим матрицу D1 (Таблица 2). включив в нее рассчитанные элементы из приложения A.
Таблица 2- Матрица D1
D1= |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
||
1 |
0 |
1 |
5 |
9 |
9 |
? |
? |
? |
||
2 |
1 |
0 |
1 |
10 |
10 |
1 |
? |
? |
||
3 |
5 |
1 |
0 |
14 |
14 |
2 |
? |
1 |
||
4 |
9 |
10 |
14 |
0 |
9 |
? |
5 |
? |
||
5 |
9 |
10 |
14 |
9 |
0 |
? |
4 |
4 |
||
6 |
? |
1 |
2 |
? |
? |
0 |
? |
5 |
||
7 |
? |
? |
? |
5 |
4 |
? |
0 |
8 |
||
8 |
? |
? |
1 |
? |
4 |
5 |
8 |
0 |
Представим матрицу D2 (Таблица 3). включив в нее рассчитанные элементы из приложения.
Таблица 3 - Матрица D2
D2= |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
||
1 |
0 |
1 |
2 |
9 |
9 |
2 |
? |
? |
||
2 |
1 |
0 |
1 |
10 |
10 |
1 |
? |
? |
||
3 |
2 |
1 |
0 |
11 |
11 |
2 |
? |
1 |
||
4 |
9 |
10 |
11 |
0 |
9 |
11 |
5 |
? |
||
5 |
9 |
10 |
11 |
9 |
0 |
11 |
4 |
4 |
||
6 |
2 |
1 |
2 |
11 |
11 |
0 |
? |
5 |
||
7 |
? |
? |
? |
5 |
4 |
? |
0 |
8 |
||
8 |
? |
? |
1 |
? |
4 |
5 |
8 |
0 |
Представим матрицу D3 (Таблица 4). включив в нее рассчитанные элементы из приложения.
Таблица 4 - Матрица D3
D3= |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
||
1 |
0 |
1 |
2 |
9 |
9 |
2 |
? |
3 |
||
2 |
1 |
0 |
1 |
10 |
10 |
1 |
? |
2 |
||
3 |
2 |
1 |
0 |
11 |
11 |
2 |
? |
1 |
||
4 |
9 |
10 |
11 |
0 |
9 |
11 |
5 |
12 |
||
5 |
9 |
10 |
11 |
9 |
0 |
11 |
4 |
4 |
||
6 |
2 |
1 |
2 |
11 |
11 |
0 |
? |
3 |
||
7 |
? |
? |
? |
5 |
4 |
? |
0 |
8 |
||
8 |
3 |
2 |
1 |
12 |
4 |
3 |
8 |
0 |
Представим матрицу D4 (Таблица 5). включив в нее рассчитанные элементы из приложения.
Таблица 5 - Матрица D4
D4= |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
||
1 |
0 |
1 |
2 |
9 |
9 |
2 |
14 |
3 |
||
2 |
1 |
0 |
1 |
10 |
10 |
1 |
15 |
2 |
||
3 |
2 |
1 |
0 |
11 |
11 |
2 |
16 |
1 |
||
4 |
9 |
10 |
11 |
0 |
9 |
11 |
5 |
12 |
||
5 |
9 |
10 |
11 |
9 |
0 |
11 |
4 |
4 |
||
6 |
2 |
1 |
2 |
11 |
11 |
0 |
16 |
3 |
||
7 |
14 |
15 |
16 |
5 |
4 |
16 |
0 |
8 |
||
8 |
3 |
2 |
1 |
12 |
4 |
3 |
8 |
0 |
Представим матрицу D5 (Таблица 6). включив в нее рассчитанные элементы из приложения.
Таблица 6 - Матрица D5
D5= |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
||
1 |
0 |
1 |
2 |
9 |
9 |
2 |
13 |
3 |
||
2 |
1 |
0 |
1 |
10 |
10 |
1 |
14 |
2 |
||
3 |
2 |
1 |
0 |
11 |
11 |
2 |
15 |
1 |
||
4 |
9 |
10 |
11 |
0 |
9 |
11 |
5 |
12 |
||
5 |
9 |
10 |
11 |
9 |
0 |
11 |
4 |
4 |
||
6 |
2 |
1 |
2 |
11 |
11 |
0 |
15 |
3 |
||
7 |
13 |
14 |
15 |
5 |
4 |
15 |
0 |
8 |
||
8 |
3 |
2 |
1 |
12 |
4 |
3 |
8 |
0 |
Представим матрицу D6. (Таблица 7). включив в нее рассчитанные элементы из приложения.
Таблица 7 - Матрица D6
D6= |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
||
1 |
0 |
1 |
2 |
9 |
9 |
2 |
13 |
3 |
||
2 |
1 |
0 |
1 |
10 |
10 |
1 |
14 |
2 |
||
3 |
2 |
1 |
0 |
11 |
11 |
2 |
15 |
1 |
||
4 |
9 |
10 |
11 |
0 |
9 |
11 |
5 |
12 |
||
5 |
9 |
10 |
11 |
9 |
0 |
11 |
4 |
4 |
||
6 |
2 |
1 |
2 |
11 |
11 |
0 |
15 |
3 |
||
7 |
13 |
14 |
15 |
5 |
4 |
15 |
0 |
8 |
||
8 |
3 |
2 |
1 |
12 |
4 |
3 |
8 |
0 |
Представим матрицу D7. (Таблица 8). включив в нее рассчитанные элементы из приложения.
Таблица 8 - Матрица D7
D7= |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
||
1 |
0 |
1 |
2 |
9 |
9 |
2 |
13 |
3 |
||
2 |
1 |
0 |
1 |
10 |
10 |
1 |
14 |
2 |
||
3 |
2 |
1 |
0 |
11 |
11 |
2 |
15 |
1 |
||
4 |
9 |
10 |
11 |
0 |
9 |
11 |
5 |
12 |
||
5 |
9 |
10 |
11 |
9 |
0 |
11 |
4 |
4 |
||
6 |
2 |
1 |
2 |
11 |
11 |
0 |
15 |
3 |
||
7 |
13 |
14 |
15 |
5 |
4 |
15 |
0 |
8 |
||
8 |
3 |
2 |
1 |
12 |
4 |
3 |
8 |
0 |
Представим матрицу D8, включив в нее рассчитанные элементы.
Таблица 9 - Матрица D8
D8= |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
||
1 |
0 |
1 |
2 |
9 |
7 |
2 |
11 |
3 |
||
2 |
1 |
0 |
1 |
10 |
6 |
1 |
10 |
2 |
||
3 |
2 |
1 |
0 |
11 |
5 |
2 |
9 |
1 |
||
4 |
9 |
10 |
11 |
0 |
9 |
11 |
5 |
12 |
||
5 |
7 |
6 |
5 |
9 |
0 |
7 |
4 |
4 |
||
6 |
2 |
1 |
2 |
11 |
7 |
0 |
11 |
3 |
||
7 |
11 |
10 |
9 |
5 |
4 |
11 |
0 |
8 |
||
8 |
3 |
2 |
1 |
12 |
4 |
3 |
8 |
0 |
В результате, нами получена матрица длин кратчайших путей между каждой парой вершин графа. Ниже представлена таблица путей. Каждый элемент Cij таблицы, это путь из вершины i в вершину j:
Таблица 10- Таблица путей
i/j |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
|
1 |
- |
d1-2=1-2 |
d1-3=1-2-3 |
d1-4=1-4 |
d1-5=1-2-3-8-5 |
d1-6=1-2-6 |
d1-7=1-2-3-8-7 |
d1-8=1-2-3-8 |
|
2 |
d2-1=2-1 |
- |
d2-3=2-3 |
d2-4=2-1-4 |
d2-5=2-3-8-5 |
d2-6=2-6 |
d2-7=2-3-8-7 |
d2-8=2-3-8 |
|
3 |
d3-1=3-2-1 |
d3-2=3-2 |
- |
d3-4=3-2-1-4 |
d3-5=3-8-5 |
d3-6=3-6 |
d3-7=3-8-7 |
d3-8=3-8 |
|
4 |
d4-1=4-1 |
d4-2=4-1-2 |
d4-3=4-1-2-3 |
- |
d4-5=4-5 |
d4-6=4-1-2-6 |
d4-7=4-7 |
d4-8=4-1-2-3-8 |
|
5 |
d5-1=5-8-3-2-1 |
d5-2=5-8-3-2 |
d5-3=5-8-3 |
d5-4=5-4 |
- |
d5-6=5-8-3-6 |
d5-7=5-7 |
d5-8=5-8 |
|
6 |
d6-1=6-2-1 |
d6-2=6-2 |
d6-3=6-3 |
d6-4=6-2-1-4 |
d6-5=6-3-8-5 |
- |
d6-7=6-3-8-7 |
d6-8=6-3-8 |
|
7 |
d7-1=7-8-3-2-1 |
d7-2=7-8-3-2 |
d7-3=7-8-3 |
d7-4=7-4 |
d7-5=7-5 |
d7-6=7-8-3-6 |
- |
d7-8=7-8 |
|
8 |
d8-1=8-3-2-1 |
d8-2=8-3-2 |
d8-3=8-3 |
d8-4=8-3-2-1-4 |
d8-5=8-5 |
d8-6=8-3-6 |
d8-7=8-7 |
- |
В результате следуя из таблицы 10 и таблицы 9, кратчайший путь из вершины 1 в вершину 8, проходчит через вершины 1-2-3-8 и имеет вес равный 3.
- Введение
- 1. Граф и его элементы
- 1.1 Основные понятия
- 1.2 Ориентированный граф
- 1.3 Неориентированный граф
- 1.4 Смежность
- 1.5 Маршруты и пути
- 2. Постановка задачи коммивояжера и алгоритмы решения
- 2.1 Задача коммивояжера
- 2.2 Методы решения задачи коммивояжера
- 3. Понятия транспортной сети
- 3.1 Понятие увеличивающая дуга, цепь, разрез
- 4. Алгоритм Флойда-Уоршелл
- 5. Постановка задачи
- 6. Решение задачи аналитическим методом
- 7. Создание приложения для решения задачи
- 7.1 Описание алгоритма
- 7.3 Тестирование программы
- 7.4 Руководство пользователя
- Заключение
- Элементы теории графов
- Элементы теории графов
- Элементы теории графов
- Элементы теории графов
- 1. Графы и их элементы.
- Элементы графа
- Элементы теории графов. Оптимизация на графах.
- 15 Элементы теории графов. Способы задания графов.
- § 2.2. Отношения и характеристики элементов графа
- Элементы теории графов.