Поиск самого дешевого маршрута на PHP алгоритмом Дейкстры

//Поиск самого дешевого маршрута на PHP алгоритмом Дейкстры

Задача

Написать на PHP функцию поиска самого дешевого маршрута. Функция должна получать на входе три параметра: название населенного пункта отправления, название населенного пункта прибытия, а также список, каждый элемент которого представляет собой названия неких двух населенных пунктов и стоимость проезда от одного населенного пункта до другого. На выходе функция должна возвращать самый дешевый маршрут между населенными пунктами отправления и прибытия, в виде списка транзитных населенных пунктов (в порядке следования), а также общую стоимость проезда.

Поиск кротчайшего пути

Задача о кратчайшем пути является одной из классических задач теории графов.

Существует несколько популярных алгоритмов поиска кротчайшего пути, которые можно применить для поиска самого дешевого маршрута:

  1. алгоритм Дейкстры — находит кратчайший путь от одной из вершин графа до всех остальных. Алгоритм работает только для графов без рёбер отрицательного веса.
  2. алгоритм Беллмана-Форда — находит кратчайшие пути от одной вершины графа до всех остальных во взвешенном графе. Вес ребер может быть отрицательным.
  3. алгоритм Флойда-Уоршелла — находит кратчайшие пути между всеми вершинами взвешенного ориентированного графа.
  4. алгоритм Джонсонанаходит кратчайшие пути между всеми парами вершин взвешенного ориентированного графа.
  5. алгоритм Ли (волновой алгоритм) — находит путь между вершинами графа, содержащий минимальное количество промежуточных вершин (ребер). Используется для поиска кратчайшего расстояния на карте в стратегических играх.
  6. алгоритм поиска A*находит маршрут с наименьшей стоимостью от одной вершины (начальной) к другой (целевой, конечной), используя алгоритм поиска по первому наилучшему совпадению на графе.

Реализация поиска самого дешевого маршрута на PHP алгоритмом Дейкстры

Тестовый пример для следующего графа

graph

Результат

 

By | 2017-10-30T16:43:12+00:00 16.12.2015|Categories: PHP|Один комментарий
  • Лев

    Большое спасибо :)