Алгоритм Дейкстри

Алгоритм Дейкстри
Час виконання алгоритму
КласАлгоритм пошуку
Структура данихГраф
Найгірша швидкодія

Алгоритм Дейкстри — алгоритм на графах, відкритий Дейкстрою. Знаходить найкоротший шлях від однієї вершини графа до всіх інших вершин. Класичний алгоритм Дейкстри працює тільки для графів без циклів від'ємної довжини.

Формулювання задачі

Варіант 1. Дана мережа автомобільних доріг, що з'єднують міста Львівської області. Знайти найкоротшу відстань від Львова до кожного міста області, якщо рухатись можна тільки по дорогах.

Варіант 2. Дана карта велосипедних доріжок Латвії та Білорусі. Знайти мінімальну відстань, яку треба проїхати, щоб дістатися від Риги до Бобруйська.

Варіант 3. Є план міста з нанесеними на нього місцями розміщення пожежних частин. Знайти найближчу до кожного дому пожежну станцію.

інші мови
Bahasa Indonesia: Algoritme Dijkstra
srpskohrvatski / српскохрватски: Dijkstrin algoritam
Simple English: Dijkstra's algorithm
slovenščina: Dijkstrov algoritem
Tiếng Việt: Thuật toán Dijkstra