Дискретная математика

162 вершину Vp2 такую, что и т.д. до тех пор, пока не дойдем до веришиы и. Утверждаем, что цепь Zo(v,u)='{v „,Vpi,...,u} ( длина которой равна А„) является кратчайшей. Для доказательства этого утверждения рассмотрим произвольную цепь из v в м: Z={v^vu,...,vi^,u}. Её длина будет /x(Z). Согласно правилу расстановки индексов будут выполняться следующие неравенства; /J(VKH VIA); LH-0^^(VB,U); Суммируя эти неравенства, получаем; L „<£JU(VI,VJ)=M(Z). Таким образом, Л, меньше или равна длине любой цепи соединяющей вершины V и к, но Я„~/л(1о), т.е. цепь Zo (v,u) обладает минимальной длиной. Путиик, дороги нет, дорогу делаешь ты, Мачадо' § 18. Алгоритм Дейкстры нахождения кратчайших путей от заданной вершины орграфа Отметим, что имеется много различных алгоритмов нахождения кратчайших цепей в графе, а также кратчайших путей в орграфе. Эти алгоритшы отличаются друг от друга как числом необходимых операций (временной сложностью), так и возможностями применения. Например, алгоритм Беллмана - Форда позволяет находить кратчайшую цепь (путь) в графе (орграфе), в котором веса или длины рёбер (дуг) могут быть как положительные, тж и отрицательные. Алгоритм Дейкстры более эффективен (имеет меньшую временную сложность), чем алгоритм Беллмана - Форда, но веса рёбер (дуг) должны быть положительными. Учитывая, что во многих случаях выполняете^ положительность весов, приведём алгоритм Дейкстры согласно [17]. Считаем, что граф задан списками смежных вершин. Пусть G~(V,X) - взвешенный орграф с п вершинами, для каждой дуги которого введен неотрицательный вес (длина) fu (Vi,Vj). Определим пхп весовую матрицу М= т,-. если г-/ если V/ и Vj не соединены дугой, V,- ,VJ). если из V/ идет дуга в VJ . ) Испанский поэт.