Алгоритм Дейкстры: различия между версиями
Перейти к навигации
Перейти к поиску
KEV (обсуждение | вклад) (Создана новая страница размером '''Алгоритм Дейкстры'''(E.Dijkstra) - алгоритм отыскания [[кратчайший путь|кратча...) |
KEV (обсуждение | вклад) Нет описания правки |
||
| Строка 1: | Строка 1: | ||
'''Алгоритм Дейкстры'''([[E.Dijkstra]]) | '''Алгоритм Дейкстры'''([[E.Dijkstra]]) — алгоритм отыскания [[кратчайший путь|кратчайшего пути]] ([[цепь|цепи]]) во [[взвешенный орграф|взвешенном орграфе]] ([[граф|графе]]) без [[контур|контуров]] ([[цикл|циклов]]) отрицательной длины с трудоемкостью <math>{\mathcal O}(|\,V\,|^2)</math>, предложенный Э.Дейкстрой в | ||
1959 г. | 1959 г. | ||
==Литература== | ==Литература== | ||
* Ахо А., Хопкрофт Дж., Ульман Дж. Построение и анализ вычислительных алгоритмов. | * Ахо А., Хопкрофт Дж., Ульман Дж. Построение и анализ вычислительных алгоритмов. — М.: Мир, 1979. | ||
* Кристофидес Н. Теория графов. Алгоритмический подход. | * Кристофидес Н. Теория графов. Алгоритмический подход. — М.: Мир, 1978. | ||
Текущая версия от 13:14, 17 ноября 2010
Алгоритм Дейкстры(E.Dijkstra) — алгоритм отыскания кратчайшего пути (цепи) во взвешенном орграфе (графе) без контуров (циклов) отрицательной длины с трудоемкостью [math]\displaystyle{ {\mathcal O}(|\,V\,|^2) }[/math], предложенный Э.Дейкстрой в 1959 г.
Литература
- Ахо А., Хопкрофт Дж., Ульман Дж. Построение и анализ вычислительных алгоритмов. — М.: Мир, 1979.
- Кристофидес Н. Теория графов. Алгоритмический подход. — М.: Мир, 1978.