Алгоритъм на Дейкстра
от Уикипедия, свободната енциклопедия
Алгоритъм на Дейкстра (по името на откривателя си Едсхер Дейкстра) служи за пресмятане на най-къс път в насочен граф с неотрицателни тегла по ребрата.
Алгоритъмът намира приложение най вече в информатиката и логистиката, където често се търси най-късото разстояние между две точки (в програма за GPS устройства, където трябва да се планира най-краткото трасе между стартовата и крайната позиция; оптимизация на транспорта; задача за търговския пътник ... )
[редактиране] Описание на алгоритъма
Това е алгоритъм (често имплементиран като рекурсивен), който във всеки възел записва дължината на пътя до актуалния възел. Ако в текущият възел е записано валидно (неотрицателно) разстояние (при предишен пробег на маршрут през графа), той бива презаписан, ако новото разстояние е по-кратко от вече записаното.
[редактиране] Външни препратки
- Анимация, показваще действието на алгоритма
- The Boost Graph Library (BGL)
- Javascript имплементация на алгоритъма
- Interactive Implementation of Dijkstra's Algorithm
- Проблемът за най-късо трасе: Алгоритъм на Дейкстра
- Dijkstra's Algorithm Applet
| Тази статия е мъниче. Можете да помогнете на Уикипедия, като я разширите. Просто щракнете на редактиране и добавете онова, което знаете. | 

