Алгоритъм на Дейкстра
от Уикипедия, свободната енциклопедия
Алгоритъм на Дейкстра, наречен на името на откривателя си Едсхер Дейкстра(Edsger Dijkstra), служи за пресмятане на най-къс път в ориентиран граф с неотрицателни тегла на ребрата.
Алгоритъмът намира приложение най вече в информатиката и логистиката, където често се търси най-късото разстояние между две точки (в програма за GPS устройства, където трябва да се планира най-краткото трасе между стартовата и крайната позиция; оптимизация на транспорта; задача за търговския пътник ... )
[редактиране] Описание на алгоритъма
Това е алгоритъм (често имплементиран като рекурсивен), който във всеки възел записва дължината на пътя до актуалния възел. Ако в текущият възел е записано валидно (неотрицателно) разстояние (при предишен пробег на маршрут през графа), той бива презаписан, ако новото разстояние е по-кратко от вече записаното.
