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

.

.

1 2 …

_j

… –

рис. 5

После реализации n шагов алгоритма определение по матрицам D_n и S_n кратчайшего пути между узлами i и j выполняется по следующим правилам .

1. Расстояние между узлами i и j равно элементу d_ij в матрице D_n.

2. Промежуточные узлы пути от узла i до узла j определяем по матрице S_n. Пусть s_ij = k, тогда имеем путь i → j → k. Если далее s_ik = k и s_ki = j, тогда считаем, что весь путь определен, так как найдены все промежуточные узлы. В противном случае повторяем описанную процедуру для путей от узла i к узлу k и от узла k к узлу j.

3. Численное решение показательного примера

Найдем для сети, показанной на рисунке 5, кратчайшие пути между любыми двумя узлами. Расстояния между узлами этой сети проставлены на рисунке возле соответствующих ребер. Ребро (3,5) ориентировано, поэтому не допускается движение от узла 5 к узлу 3. Все остальные ребра допускают движение в обе стороны.

Шаг 0. Начальное решение матрицы D₀ и S₀ строятся непосредственно по заданной схеме

сети. Матрица D₀ симметрична, за исключением пары элементов d₃₅ и d₅₃, где d₃₅ = ∞ (поскольку невозможен переход от узла 5 к узлу 3).

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

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