Дейкстра алгоритмі – 1959 жылы голланд ғалымы Эдгер Дейкстра ойлап тапқан Графтық алгоритм. Графтың бір төбесінен барлық басқаларына дейінгі ең қысқа жолдарды табады. Алгоритм теріс салмақты жиектері жоқ Графтар үшін ғана жұмыс істейді. Алгоритм программалауда кеңінен қолданылады, мысалы, оны OSPF және IS-IS маршруттау хаттамалары қолданады. Формальды анықтама Теріс салмақ доғалары жоқ G(V,E) өлшенген бағытталған графы берілген. G графының кейбір а шыңынан осы графтың барлық басқа шыңдарына дейінгі ең қысқа жолдарды табыңыз.
Мысалдар Нұсқа 1. Мәскеу облысындағы қалаларды байланыстыратын автомобиль жолдарының желісі берілген. Кейбір жолдар бір жол. А қаласынан аймақтың әрбір қаласына дейінгі ең қысқа жолдарды табыңыз (егер сіз тек жолдармен қозғала алсаңыз).
2-нұсқа. Әлемде қалалар арасында бірнеше рейстер бар, әрқайсысының құны белгілі. А-дан В-ға рейс құны В-дан А-ға рейс құнына тең болмауы мүмкін. Копенгагеннен Барнаулға дейінгі ең аз шығын бағытын (мүмкін трансферттермен) табыңыз.
Бейресми түсініктеме V төбесіндегі әрбір шыңға белгі тағайындалған — осы шыңнан a дейінгі ең аз белгілі қашықтық.
Алгоритм кезең-кезеңімен жұмыс істейді - әр қадамда ол бір шыңға «барады» және белгілерді азайтуға тырысады. Алгоритм барлық шыңдарға барған кезде аяқталады.
