Теоретическая часть. 1. Построение кратчайшего пути между двумя вершинами
1. Построение кратчайшего пути между двумя вершинами. Для построения такого пути нужно вначале определить кратчайшие расстояния от фиксированной начальной вершины до всех вершин графа, а затем восстановить кратчайший путь от этой вершины до заданной конечной вершины. Для определения кратчайших расстояний от фиксированной начальной вершины до всех вершин ориентированного графа воспользуемся алгоритмом Форда-Беллмана. Обозначим через C – матрицу весов дуг графа (вес несуществующей дуги в задачах поиска минимума расстояний считаем равным +¥), D – массив кратчайших расстояний от начальной вершины s до всех вершин графа (полагаем Begin for For ton-2 do For do for end. Количество итераций k вычислений массива D можно уменьшить, сравнивая массивы на текущей и предыдущей итерации (аналогично, алгоритмам сортировки). Если значения массива D не изменились на данной итерации, то вычисления заканчиваются. Алгоритм восстановления кратчайшего пути от начальной вершины s до конечной вершины t использует механизм стека. В нём применяются следующие обозначения: 1) СТЕК 2) Begin СТЕК: =Æ; СТЕК
|
).
do 
; 
;
do 
– поместить вершину v в стек;
СТЕК – извлечь вершину v из стека.
; 
;
