3.5.3. Поиск кратчайших путей в сети.

Подобные задачи возникают при выборе маршрутов в вычислительных сетях и транспортных системах. В вычислительных сетях решение подобных задач определяет состав и структуру сетевых протоколов для обслуживания движения пакетов информации. По данным о загрузке каналов, направлении и протяженности вычисляется наиболее оптимальный маршрут прохождения пакета информации. При нахождении такого пути к пакету добавляется заголовок, в котором указывают перечень узлов для перехода от вершины х_i к вершине х_j или очередную вершину перехода. В транспортных системах решение подобных задач определяет наиболее экономный по стоимости или по времени маршрут движения транспортной единицы.

Каждая вершина в таком графе используется только один раз (простой маршрут), а длина кратчайшего пути определится суммой весов ребер на переходе _i,j=(х_i;...х_k;...х_j):

L_i,j=_m,n l_m,n, где im, nj, mn.

Для поиска кратчайших путей существует несколько алгоритмов. Алгоритмы Форда-Беллмана и Дейкстра позволяют найти кратчайшие пути от заданной вершины графа до любой другой. В результате этих вычислений формируется древовидный остов с корнем в заданной вершине.

Алгоритмы Флойда и Данцига позволяют искать кратчайшие пути между любой парой вершин сети.

В основе всех алгоритмов лежит операция сравнения двух простых маршрутов.

На рис. 3.27 показаны два простых маршрута, соединяющих вершины х_i и х_j. Выбор крат- чайшего пути между вершинами

есть результат сравнения длин двух маршрутов, т.е.

L_i,j=min{l_i,j; (l_i,p+ l_p,j)}.

Если существует несколько вершин, смежных с вершинами х_i и х_j следует выполнять процедуру последовательно, сравнивая длины маршрутов для каждой вершины.

Для того, чтобы определять по алгоритму Флойда. кратчайшие путь и переходы между вершинами x_i и x_j, необходимо использовать две матрицы: матрицу кратчайших путей ║l(n;n)║ и матрицу кратчайших переходов ║(n;n)║, которые позволяют сравнивать различные маршруты через базовую вершину x_p.

Вершина х_p в матрице кратчайших путей называется базовой, а строка и столбец матрицы ║l^p║ - базовыми (выделены в матрице штриховкой), если она позволяет сравнивать кратчайшие пути между любой парой вершин x_i и x_j, смежных с вершиной х_p. Базовая вершина

позволяет найти путь из вершины x_i в вершину x_j через вершину x_p по формуле l_ij=(l_ip+ l_pj), представить этот результат для сравнения с имеющимся значением l_ij и выбрать наименьшее значение.

l^p	x0	..	xi	..	xp	..	xj		^p	x0	..	xi	..	xp	..	xj
x0	0	..	l0i	..	l0p	..	l0j		x0	x0	..	xi	..	xp	..	xj
...	...	0	...	..	...	..	...		...	x0	..	xi	..	xp	..	xj
xi	li0	..	0	..	lip	..	lij		xi	x0	..	xi	..	xp	..	xj
...	...	..	...	0	...	..	...		...	x0	..	xi	..	xp	..	xj
xp	lp0	..	lpi	..	0	..	lpj		xp	x0	..	xi	..	xp	..	xj
...	...	..	...	..	...	0	...		...	x0	..	xi	..	xp	..	xj
xj	ljo	..	lji	..	ljp	..	0		xj	x0	..	xi	..	xp	..	xj

Если в качестве базовой, использовать последовательно все вершины, начиная с х₀, то за p=(n-1) шагов итерации можно найти кратчайшие пути между любой парой вершин. Для p=0 матрица ║l⁰║ есть матрица весов графа.

Для p=0 элементы матрицы ⁰ есть концевые вершины перехода из х_i в х_j. Поэтому в каждом столбце х_j матрицы ⁰ указана вершина х_j. На p-м шаге итерации происходит замена вершины перехода вершиной кратчайшего перехода по формулам:

а) если (l_i,p+ l_p,j)^pl_i,j^p, то _i,j ^(p+1) = _i,j ^p=х_j;

b) если (l_i,p+ l_p,j)^p<l_i,j^p, то _i,j ^(p+1)=х_p.

Следовательно, для анализа n-вершинного графа необходимо последовательно построить (n-1) матриц.

Алгоритм Флойда:

шаг 1: составить матрицу весов ║l^p║ и матрицу переходов ║^p║ для p=0, где p – шаг итерации;

шаг 2: определить вершину p базовой и выделить базовые строки и столбец;

шаг 3: вычеркнуть строки и столбцы, базовые элементы которых имеют значение , т.к. (l_i,p+) и (+ l_p,j) всегда больше конечного значения l_i,j;

шаг 4: сравнить каждый невычеркнутый элемент l_ij^p с суммой (l_i,p+ l_p,j)^p для формирования значений l_i,j и _i,j на очередном шаге итерации:

a) если (l_i,p+ l_p,j)^p<l_i,j^p, то l_i,j^p+1=(l_i,p+ l_p,j)^p, а _i,j ^(p+1)=p;

b) если (l_i,p+ l_p,j)^p>l_i,j^p, то l_i,j^p+1=l_i,j^p; _i,j ^(p+1)= _i,j ^p.

шаг 5: если p<n, то принять p=p+1 и вернуться к шагу 4, иначе конец.

Пример: Найти кратчайшие пути на графе (см. рис. 3.28).

Ниже таблицами показан процесс вычисления от p=0 до p=7

l^0

x0

x1

x2

x3

x4

x5

x6

x7

^0

x0

x1

x2

x3

x4

x5

x6

x7

x0

0

9

∞

3

∞

∞

∞

∞

x0

x0

x1

x2

x3

x4

x5

x6

x7

x1

9

0

2

∞

7

∞

∞

∞

x1

x0

x1

x2

x3

x4

x5

x6

x7

x2

∞

2

0

2

4

8

6

∞

x2

x0

x1

x2

x3

x4

x5

x6

x7

x3

3

∞

2

0

∞

∞

5

∞

x3

x0

x1

x2

x3

x4

x5

x6

x7

x4

∞

7

4

∞

0

10

∞

9

x4

x0

x1

x2

x3

x4

x5

x6

x7

x5

∞

∞

8

∞

10

0

7

12

x5

x0

x1

x2

x3

x4

x5

x6

x7

x6

∞

∞

6

5

∞

7

0

10

x6

x0

x1

x2

x3

x4

x5

x6

x7

x7

∞

∞

∞

∞

9

12

10

0

x7

x0

x1

x2

x3

x4

x5

x6

x7

l^1

x0

x1

x2

x3

x4

x5

x6

x7

^1

x0

x1

x2

x3

x4

x5

x6

x7

x0

0

9

∞

3

∞

∞

∞

∞

x0

x0

x1

x2

x3

x4

x5

x6

x7

x1

9

0

2

12

7

∞

∞

∞

x1

x0

x1

x2

x0

x4

x5

x6

x7

x2

∞

2

0

2

4

8

6

∞

x2

x0

x1

x2

x3

x4

x5

x6

x7

x3

3

12

2

0

∞

∞

5

∞

x3

x0

x0

x2

x3

x4

x5

x6

x7

x4

∞

7

4

∞

0

10

∞

9

x4

x0

x1

x2

x3

x4

x5

x6

x7

x5

∞

∞

8

∞

10

0

7

12

x5

x0

x1

x2

x3

x4

x5

x6

x7

x6

∞

∞

6

5

∞

7

0

10

x6

x0

x1

x2

x3

x4

x5

x6

x7

x7

∞

∞

∞

∞

9

12

10

0

x7

x0

x1

x2

x3

x4

x5

x6

x7

l^2

x0

x1

x2

x3

x4

x5

x6

x7

^2

x0

x1

x2

x3

x4

x5

x6

x7

x0

0

9

11

3

16

∞

∞

∞

x0

x0

x1

x1

x3

x1

x5

x6

x7

x1

9

0

2

12

7

∞

∞

∞

x1

x0

x1

x2

x0

x4

x5

x6

x7

x2

11

2

0

2

4

8

6

∞

x2

x1

x1

x2

x3

x4

x5

x6

x7

x3

3

12

2

0

19

∞

5

∞

x3

x0

x0

x2

x3

x1

x5

x6

x7

x4

16

7

4

19

0

10

∞

9

x4

x1

x1

x2

x1

x4

x5

x6

x7

x5

∞

∞

8

∞

10

0

7

12

x5

x0

x1

x2

x3

x4

x5

x6

x7

x6

∞

∞

6

5

∞

7

0

10

x6

x0

x1

x2

x3

x4

x5

x6

x7

x7

∞

∞

∞

∞

9

12

10

0

x7

x0

x1

x2

x3

x4

x5

x6

x7

l^3

x0

x1

x2

x3

x4

x5

x6

x7

^3

x0

x1

x2

x3

x4

x5

x6

x7

x0

0

9

11

3

15

19

17

∞

x0

x0

x1

x1

x3

x2

x2

x2

x7

x1

9

0

2

4

6

10

8

∞

x1

x0

x1

x2

x2

x2

x2

x2

x7

x2

11

2

0

2

4

8

6

∞

x2

x1

x1

x2

x3

x4

x5

x6

x7

x3

3

4

2

0

6

10

5

∞

x3

x0

x2

x2

x3

x2

x2

x6

x7

x4

15

6

4

6

0

10

10

9

x4

x2

x2

x2

x2

x4

x5

x2

x7

x5

19

10

8

10

10

0

7

12

x5

x2

x2

x2

x2

x4

x5

x6

x7

x6

17

8

6

5

10

7

0

10

x6

x2

x2

x2

x3

x2

x5

x6

x7

x7

∞

∞

∞

∞

9

12

10

0

x7

x0

x1

x2

x3

x4

x5

x6

x7

l^4

x0

x1

x2

x3

x4

x5

x6

x7

^4

x0

x1

x2

x3

x4

x5

x6

x7

x0

0

7

5

3

9

13

8

∞

x0

x0

x3

x3

x3

x3

x3

x3

x7

x1

7

0

2

4

6

10

8

∞

x1

x3

x1

x2

x2

x2

x2

x2

x7

x2

5

2

0

2

4

8

6

∞

x2

x3

x1

x2

x3

x4

x5

x6

x7

x3

3

4

2

0

6

10

5

∞

x3

x0

x2

x2

x3

x2

x2

x6

x7

x4

9

6

4

6

0

10

10

9

x4

x3

x2

x2

x2

x4

x5

x2

x7

x5

13

10

8

10

10

0

7

12

x5

x3

x2

x2

x2

x4

x5

x6

x7

x6

8

8

6

5

10

7

0

10

x6

x3

x2

x2

x3

x2

x5

x6

x7

x7

∞

∞

∞

∞

9

12

10

0

x7

x0

x1

x2

x3

x4

x5

x6

x7

l^5

x0

x1

x2

x3

x4

x5

x6

x7

^5

x0

x1

x2

x3

x4

x5

x6

x7

x0

0

7

5

3

9

13

8

18

x0

x0

x3

x3

x3

x3

x3

x3

x4

x1

7

0

2

4

6

10

8

15

x1

x3

x1

x2

x2

x2

x2

x2

x4

x2

5

2

0

2

4

8

6

13

x2

x3

x1

x2

x3

x4

x5

x6

x4

x3

3

4

2

0

6

10

5

15

x3

x0

x2

x2

x3

x2

x2

x6

x4

x4

9

6

4

6

0

10

10

9

x4

x3

x2

x2

x2

x4

x5

X2

x7

x5

13

10

8

10

10

0

7

12

x5

x3

x2

x2

x2

x4

x5

x6

x7

x6

8

8

6

5

10

7

0

10

x6

x3

x2

x2

x3

x2

x5

x6

x7

x7

18

15

13

15

9

12

10

0

x7

x4

x4

x4

x4

x4

x5

x6

x7

l^6

x0

x1

x2

x3

x4

x5

x6

x7

^6

x0

x1

x2

x3

x4

x5

x6

x7

x0

0

7

5

3

9

13

8

18

x0

x0

x3

x3

x3

x3

x3

x3

x4

x1

7

0

2

4

6

10

8

15

x1

x3

x1

x2

x2

x2

x2

x2

x4

x2

5

2

0

2

4

8

6

13

x2

x3

x1

x2

x3

x4

x5

x6

x4

x3

3

4

2

0

6

10

5

15

x3

x0

x2

x2

x3

x2

x2

x6

x4

x4

9

6

4

6

0

10

10

9

x4

x3

x2

x2

x2

x4

x5

x2

x7

x5

13

10

8

10

10

0

7

12

x5

x3

x2

x2

x2

x4

x5

x6

x7

x6

8

8

6

5

10

7

0

10

x6

x3

x2

x2

x3

x2

x5

x6

x7

x7

18

15

13

15

9

12

10

0

x7

x4

x4

x4

x4

x4

x5

x6

x7

l^7

x0

x1

x2

x3

x4

x5

x6

x7

^7

x0

x1

x2

x3

x4

x5

x6

x7

x0

0

7

5

3

9

13

8

18

x0

x0

x3

x3

x3

x3

x3

x3

x4

x1

7

0

2

4

6

10

8

15

x1

x3

x1

x2

x2

x2

x2

x2

x4

x2

5

2

0

2

4

8

6

13

x2

x3

x1

x2

x3

x4

x5

x6

x4

x3

3

4

2

0

6

10

5

15

x3

x0

x2

x2

x3

x2

x2

x6

x4

x4

9

6

4

6

0

10

10

9

x4

x3

x2

x2

x2

x4

x5

x2

x7

x5

13

10

8

10

10

0

7

12

x5

x3

x2

x2

x2

x4

x5

x6

x7

x6

8

8

6

5

10

7

0

10

x6

x3

x2

x2

x3

x2

x5

x6

x7

x7

18

15

13

15

9

12

10

0

x7

x4

x4

x4

x4

x4

x5

x6

x7

По матрицам ||l⁷|| и ||_i,j⁷|| можно найти длину кратчайшего перехода между любой парой вершин исходного графа.

Например, между вершинами х₀ и х₇ длина кратчайшего пути равна 18, а переход ₀₇=(х₀, х₃, х₂, х₄, х₇), между вершинами х₁ и х₆ длина кратчайшего пути равна 8, а переход ₁₆=(х₁, х₂, х₆) и т.д.

При решении практических задач возникает необходимость поиска нескольких путей, частично - упорядоченных по возрастанию относительно кратчайшего. Такие задачи возникают при временной загруженности канала на определенном участке или неисправности узла. Для решения подобных задач разработаны обобщенные алгоритмы Флойда.