Реферат: Нахождение кратчайшего маршрута между двумя городами по существующей сети дорог

2

3

4

5

1

– 2 3 4 5

2

1 – 3 4 5

3

1 2 – 4 5

4

1 2 3 – 5

5

1 2 3 4 –

Шаг 1. В матрице D₀ выделены ведущие строка и столбец (k=1) (рис. 8). После этого каждый элемент проверяется с помощью треугольного оператора. Таким образом, чтобы на основе матриц D₀ и S₀ получить матрицы D₁ и S₁, выполняем следующие действия:

1. проверяем d₃₂ > d₃₁ + d₁₂ = 20 > 30 + 100 = 20 > 130 если условие принимает истину, то устанавливаем S₃₂ = 1 ,а если нет тогда все так и остается.

Матрицы D₁ и S₁ имеют следующий вид (см. рис. 9):

рис. 9 D1 1 2 3 4 5 1 – 100 30 ∞ ∞ 2 100 – 20 15 ∞ 3 30 20 – 10 ∞ 4 ∞ 15 10 – 50 5 ∞ ∞ 60 50 –

S1 1 2 « 5 6 7 8 9 10 11 12 13 14 » К-во Просмотров: 432 Бесплатно скачать Реферат: Нахождение кратчайшего маршрута между двумя городами по существующей сети дорог >>> Скачать <<< Меню Поиск