Алгоритъм на Дейкстра
From Wikipedia, the free encyclopedia
Алгоритъмът на Дейкстра, наречен на автора си Едсхер Дейкстра (Edsger Dijkstra), служи за пресмятане на най-къс път от даден връх до всички останали върхове на граф с неотрицателни тегла на ребрата.
![Thumb image](http://upload.wikimedia.org/wikipedia/commons/thumb/5/57/Dijkstra_Animation.gif/220px-Dijkstra_Animation.gif)
Графът може да бъде ориентиран или неориентиран. Резултатът от работата на алгоритъма е дърво на най-късите пътища с начало дадения връх. Алгоритъмът се използва още за намиране на най-къс път от един даден връх до друг даден връх; в този случай алгоритъмът спира работа, след като е намерил най-краткия път между тези два върха.
Пример: Всяка пътна карта може да се разглежда като граф. Върховете на графа са градовете, а ребрата са шосетата между градовете.
Алгоритъмът на Дейкстра се основава на една идея, наречена релаксация: във всеки момент от работата на алгоритъма за всеки връх се пази информация за най-късия път, намерен до момента; ако след това алгоритъмът намери по-добър път, тази информация се актуализира. Същата идея се използва и в други алгоритми, аналогични на алгоритъма на Дейкстра: за търсене на най-широк път, за построяване на минимално покриващо дърво и др. Ето защо алгоритъмът на Дейкстра и неговите аналози се използват широко в практиката, например в мрежовите протоколи за маршрутизация, най-вече в IS-IS и OSPF, както и в програмите за GPS устройства с цел оптимизация на транспорта.
Алгоритъмът на Дейкстра работи само ако теглата на ребрата са неотрицателни. За графи, в които има ребра с отрицателни тегла, са разработени други алгоритми: алгоритъмът на Белман—Форд и алгоритъмът на Флойд—Уоршал.