Практикум по курсу "Алгоритмизация и программирование". Часть 2. Андрианова А.А - 118 стр.

А.А. Андрианова, Л.Н. Исмагилов, Т.М. Мухтарова                   .
непосредственно предшествующая v на кратчайшем пути.
    Для решения задачи требуется вспомогательный массив X размера n. С
его помощью будут помечаться вершины, которые уже были просмотрены,
поэтому начальные значения элементов массива равны нулю. Массив T пер-
воначально должен заполняться бесконечными значениями, поскольку длина
кратчайшего пути пока неизвестна.
    Для начальной вершины s H[s]=0 (начальной вершине ничего не пред-
шествует), T[s]=0 (путь s->s имеет длину 0), X[s]=1 (вершина просмот-
рена). Фиксируется вершина v=s.
    Для зафиксированной вершины перебираем все смежные ей непросмот-
ренные вершины (переменная u). Если длина пути из s в u через v (T[v]
+g.a[v][u]) (длина кратчайшего пути до v плюс вес ребра v->u) меньше,
чем прежнее значение T[u], меняем его и запоминаем в H[u] предшествую-
щую вершину v. Далее находим минимальный элемент массива T, соответ-
ствующий непросмотренным вершинам (в переменной v запоминаем его ин-
декс). Если все оставшиеся элементы массива T равны бесконечности, можно
сделать вывод, что требуемого пути не существует (в этом случае функция
возвращает значение 0). Если найденный минимум соответствует вершине t,
то задача решена (в этом случае функция возвращает значение 1). В против-
ном случае помечаем вершину v как пройденную и осуществляем перебор
смежных ей вершин.
    Рассмотрим процесс решения задачи поиска кратчайшего пути из верши-
ны 1 в вершину 6 на графе, представленном на рис. 7.6 (таблица 3).




                           Рис. 7.6. Пример взвешенного графа.



                                           118