Информационный сервер для программистов: Исходники со всего света. Паскальные исходники со всего света
  Powered by Поисковый сервер Яndex: Найдется ВСЁ!
На Главную Pascal Форум Информер Страны мира
   Математика    >>    deiksgr
   
 
 Алгоритм Дейкстры для кратчайшего пути в графе   Alexander Rublinetsky 04.07.1997

Объяснение Алгоритма Дейкстры нахождения кратчайшего пути в графе



1k 
 

Hello, Sly! Tue Jul 01 1997, at 15:02, Sly Golovanov wrote All: > Алгоритм Дейкстры нахождения кратчайшего пути в графе объясните > кто-нибудь, плз. Hу не имею я доступа к библиотеке! Деpжи цитату: ============================================================ Задача: В ориентированной, неориентированной или смешанной (т. е. такой, где часть дорог имеет одностороннее движение) сети V найти кратчайший путь из заданной вершины i во все остальные вершины. Решение (Дейкстpа, 1959 г.) Алгоритм использует три массива из N (= числу вершин сети) чисел каждый. Первый массив A содержит метки с двумя значения: 0 (вершина еще не рассмотрена) и 1 (вершина уже рассмотрена); второй массив B содержит расстояния - текущие кратчайшие рас- стояния от до соответствующей вершины; третий массив с содержит номера вершин - k-й элемент С[k] есть номер предпоследней вершины на текущем кратчайшем пути из Vi в Vk. Матрица расстояний D[i,k] задает длины дуге D[i,k]; если такой дуги нет, то D[i,k] присваивается большое число Б, равное "машинной бесконечности". Теперь можно описать * Алгоритм Дейкстры * 1 (инициализация). В цикле от 1 до N заполнить нулями массив A; заполнить числом i массив C; перенести i-ю строку матрицы D в массив B, A[i]:=1; C[i]:=0 (i - номер стартовой вершины) 2 (общий шаг). Hайти минимум среди неотмеченных (т. е. тех k, для которых A[k]=0); пусть минимум достигается на индексе j, т. е. B[j]<=B[k] Затем выполняются следующие операции: A[j]:=1; если B[k]>B[j]+D[j,k], то (B[k]:=B[j]+D[j,k]; C[k]:=j) (Условие означает, что путь Vi ... Vk длиннее, чем путь Vi...Vj Vk). (Если все A[k] отмечены, то длина пути от Vi до Vk равна B[k]. Теперь надо) перечислить вершины, входящие в кратчайший путь). 3 (выдача ответа). (Путь от Vi до Vk выдается в обратном порядке следующей процедурой:) 3.1. z:=C[k]; 3.2. Выдать z; 3.3. z:=C[z]. Если z = О, то конец, иначе перейти к 3.2. Для выполнения алгоритма нужно N раз просмотреть массив B из N элементов, т. е. алгоритм Дейкстры имеет квадратичную сложность: O(n2). ============================================================ Hа всякий случай деpжи еще и более общий алгоpитм Флойда-Уоpшелла -- находит кpатчайшие пути из всех во все: ============================================