Разработка сайтов и программного обеспечения, системное администрирование, обучение программированию и работе с СУБД MySQL

in english

Реализация алгоритма Дейкстры

Главная Проекты Реализация алгоритма Дейкстры

программа - алгоритм Дейкстры

Эта программа с исходником. Может помочь в решении задач. Использован алгоритм Дейкстры нахождения кратчайшего пути в графе.

Задача:

В ориентированной, неориентированной или смешанной (т. е. такой, где часть дорог имеет одностороннее движение) сети V найти кратчайший путь из заданной вершины i во все остальные вершины.

Алгоритм использует три массива из 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 выдается в обратном порядке следующей процедурой:)
    1. 3.1. z:=C[k];
    2. 3.2. Выдать z;
    3. 3.3. z:=C[z]. Если z = О, то конец, иначе перейти к 3.2.

Для выполнения алгоритма нужно N раз просмотреть массив B из N элементов, т. е. алгоритм Дейкстры имеет квадратичную сложность: O(n2).

Более общий алгоpитм Флойда-Уоpшелла

находит кpатчайшие пути из всех во все:

for k:=1 to N do
   for i:=1 to N do
      for j:=1 to N do
         d[i,j]:=min(d[i,j], d[i,k]+d[k,j]);

Здесь d[i,j] - сначала длина дуги [i,j], а в конце - длина кpатчайшего пути.

Литература

В.М.Бондаpев, В.И.Рублинецкий, Е.Г.Качко. Основы пpогpаммиpования. Хаpьков/Ростов-на-Дону, 1997

 

Скачать программу и исходники

Реклама:

Метки: алгоритмы, Дейкстра.

Комментарии:

Воланд:
Помогите мне решить такую задачю по теме Алгоритм дейкстры.Вот такая задача надо ее решить и все.В ориентированной, неориентированной или смешанной (т. е. такой, где часть дорог имеет одностороннее движение) сети найти кратчайший путь из заданной вершины i во все остальные вершины.
Воланд:
Помогите мне решить такую задачю по теме Алгоритм дейкстры.Вот такая задача надо ее решить и все.В ориентированной, неориентированной или смешанной (т. е. такой, где часть дорог имеет одностороннее движение) сети найти кратчайший путь из заданной вершины i во все остальные вершины.
имя:

e-mail (не публикуется):

комментарий:

© Ткачев Филипп, 2005—2017
Программист, веб-разработка и прикладное ПО.
Все права защищены.