logo
Граф и его элементы

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.