пользователей: 21231
предметов: 10456
вопросов: 177504
Конспект-online
зарегистрируйся или войди через vk.com чтобы оставить конспект.
РЕГИСТРАЦИЯ ЭКСКУРСИЯ


Поиск кратчайшего расстояния между двумя вершинами. Алгоритм Дейкстры.

http://graphonline.ru/

Алгоритм Дейкстры

Он основан на методе помечивании вершин, т е в ходе алгоритма каждой вершине приписывается метка, сначала она ночит временный характер, затем становится постоянной. Постоянная метка вершины равна длине кратчайшего пути от исходной вершины к данной.

Допустим найти кр.путь от S к T

1) λ(S) = 0 - постоянная метка

λ(х) = бесконечность, для любого х, не равному S - временные метки

z = S

2) Рассмотрим мн-во γ(z) = [x | (z,x) = U(с верхним подчеркиванием)]

Если λ(x) - временная, то обновляем эту метку: λ(X) = min [λ(x), λ(z) + C(z, x)], где С - вес ребра. Находим новые значения метки

3) Среди всех вершин с временными метками находим вершину с минимальной веткой. Пусть - λ(y0) = min [λ(x)]  λ(x) - временная

Затме метку λ(y) обьявляем постоянной. Теперь это будет текущая вершина

4) Если z = T(Совпадает), то переходим на шаг 5, иначе на шаг 2

5) Конец

λ(T) -длина кратчайшего пути, а сам путь можно восстановить по меткам.


18.06.2015; 02:03
хиты: 41
рейтинг:0
Точные науки
математика
логика и основания математики
для добавления комментариев необходимо авторизироваться.
  Copyright © 2013-2016. All Rights Reserved. помощь