align = " justify"> Описана загальна схема є неповною, оскільки вона не визначає черговості, в якій вибираються вершини u і v для перевірки умови мінімальності відстані. Ця черговості, як буде показано нижче, дуже сильно впливає на ефективність алгоритму. Опишемо тепер більш детально методи знаходження відстані від фіксованої вершини, званої джерелом, його завжди будемо позначати через s, до всіх інших вершин графа.
Спочатку представимо алгоритм для загального випадку, в якому передбачається тільки відсутність контурів з негативною завдовжки. З ці алгоритмом зазвичай пов'язують імена Л.Р. Форда і Р.Е. Беллмана. br/>
2.2 Математичний метод розв'язання задачі
Алгоритм Дейкстри (Dijkstra s algorithm) - алгоритм на графах, винайдений нідерландським ученим Е. Дейкстрой в 1959 році. Знаходить найкоротша відстань від однієї з вершин графа до всіх інших. Алгоритм працює тільки для графів без ребер негативного ваги. Алгоритм широко застосовується в програмуванні і технологіях, наприклад, його використовує протокол OSPF для усунення кільцевих маршрутів.
Алгоритм Дейкстри (Dijkstra) призначений для вирішення задачі Пошук найкоротших шляхів у графі.
Важливим фактом, що дозволяє виключити перебір, є те, що якщо у нас є найкоротший шлях від v до w, що проходить через вершину y, назвемо його, то його перша частина від v до y, теж буде найкоротшим шляхом. Дійсно, якби це було не так, тобто існував би шлях довжини меншої, ніж, то можна було б поліпшити оптимальний шлях, замінивши в ньому на (Див. # Малюнок 1).
В алгоритмі Дейкстри, ми, ітераційно підтримуємо дві множини вершин:
безліч вершин, до яких ми вже знайшли найкоротший шлях, асоційованих з вартостями найкоротших шляхів від стартової вершини до них.
безліч вершин, які досяжні одним ребром з безлічі вершин Visited, асоційованих з верхніми оцінками вартості шляху до них.
На кожній ітерації, ми вибираємо з досяжних вершин вершину v, саму найближчу до стартовою вершині s, і переносимо її з безлічі ToVisit в безліч Visited, збільшуємо безліч В«кандидатівВ» ToVisit її сусідами, і перераховуємо верхню оцінку віддаленості вершин з ToVisit до вершини s.
В ілюстрації виконання алгоритму, ми показуємо зміна на кожній ітерації хеш-таблиць Visited і ToVisit, а наприкінці зображений вхідний граф, де суцільними лініями намальовані наявні ребра з асоційованими довжинами, а пунктиром - знайдені найкоротші шляхи.
Важливо, що алгоритм працездатний тільки в разі позитивних відстаней, в іншому випадку, можна спробувати використовувати алгоритм Флойда-Уоршолла.
Код алгоритму, представлений у вигляді функції на мові Python.
def dijkstra (G, start_n...
