Поиск по графу php

Содержание

Поиск самого дешевого маршрута на PHP алгоритмом Дейкстры
Поиск самого дешевого маршрута на PHP алгоритмом Дейкстры
Задача
Поиск кротчайшего пути
PHP: Алгоритм поиск в ширину
Обход графа или как проехать из . в . на Php
PHP: Алгоритм Дейкстры — поиск кратчайшего пути

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

Задача

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

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

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

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

Источник

PHP: Алгоритм поиск в ширину

Поиск в наборе данных с помощью алгоритма «Поиск в ширину». Ищет путь с минимальным количеством переходов.

Сначала нужно представить данные в виде невзвешенных графов. Граф моделирует набор связей между элементами из набора.

В качестве примера сделаем поиск пути между станциями метро. В php граф можно представить в виде массива. Ключ — это уникальное название станции метро. Значение — это список станций, куда можно отправиться с текущей станции (ключа). Пересадочные станции — это разные станции. Отличие от обычных только в том, что они расположены близко друг к другу.

$graph = [ . 'Пушкинская' => [ 'Владимирская', 'Технологический институт 1', 'Звенигородская' ], 'Технологический институт 1' => [ 'Пушкинская', 'Балтийская', 'Технологический институт 2' ], . 'Технологический институт 2' => [ 'Сенная площадь', 'Фрунзенская', 'Технологический институт 1' ], 'Фрунзенская' => [ 'Технологический институт 2', 'Московские ворота' ], . ];

Функция проверяет есть ли путь между указанными станциями. Возвращает true или false.

function isPathExists( $from, $to ) < $checked = []; $queue = []; if( !isset( $this->graph[ $from ] ) ) < return false; >$queue[] = $this->graph[ $from ]; while( sizeof( $queue ) > 0 ) < $node = array_pop( $queue ); foreach( $node as $station ) < if( !array_key_exists( $station, $checked ) ) < array_unshift( $queue, $this->graph[ $station ] ); > $checked[ $station ] = true; if( $station == $to ) < return true; >> > return false; > var_dump( isPathExists( 'Зенит', 'Купчино' ) ); // > bool(true) var_dump( isPathExists( 'Купчино', 'Зенит' ) ); // > bool(true) var_dump( isPathExists( 'Купчино', 'Станция метро 3/4' ) ); // > bool(false)

Функция возвращает путь между указанными станциями.

function getPath( $from, $to ) < $checked = []; $queue = []; $queue[] = $this->graph[ $from ]; $path = []; foreach( $this->graph[ $from ] as $nextStation ) < $path[ $nextStation ] = [ $from ]; >while( sizeof( $queue ) > 0 ) < $node = array_pop( $queue ); foreach( $node as $station ) < if( !array_key_exists( $station, $checked ) ) < array_unshift( $queue, $this->graph[ $station ] ); foreach( $path as $prevStation => $subPath ) < if( $prevStation == $station AND $station != $from AND $station != $to ) < foreach( $this->graph[ $station ] as $nextStation ) < $path[ $nextStation ] = array_merge( [ $prevStation ], $subPath ); >unset( $path[ $prevStation ] ); > > > $checked[ $station ] = true; if( $station == $to ) < $path = $path[ $to ]; array_unshift( $path, $to ); return array_reverse( $path ); >> > return []; > var_dump( getPath( ‘Зенит’, ‘Купчино’ ) ); // > array(14) < [0]=>string(10) «Зенит» [1]=> string(20) «Приморская» [2]=> string(32) «Василеостровская» [3]=> string(25) «Гостиный двор» [4]=> string(31) «Невский проспект» [5]=> string(27) «Сенная площадь» [6]=> string(49) «Технологический институт 2» [7]=> string(22) «Фрунзенская» [8]=> string(33) «Московские ворота» [9]=> string(22) «Электросила» [10]=> string(21) «Парк Победы» [11]=> string(20) «Московская» [12]=> string(16) «Звёздная» [13]=> string(14) «Купчино» > var_dump( getPath( ‘Купчино’, ‘Зенит’ ) ); // > array(14) < [0]=>string(14) «Купчино» [1]=> string(16) «Звёздная» [2]=> string(20) «Московская» [3]=> string(21) «Парк Победы» [4]=> string(22) «Электросила» [5]=> string(33) «Московские ворота» [6]=> string(22) «Фрунзенская» [7]=> string(49) «Технологический институт 2» [8]=> string(27) «Сенная площадь» [9]=> string(31) «Невский проспект» [10]=> string(25) «Гостиный двор» [11]=> string(32) «Василеостровская» [12]=> string(20) «Приморская» [13]=> string(10) «Зенит» > var_dump( getPath( ‘Купчино’, ‘Станция метро 3/4’ ) ); // > array(0)

Код был обновлён. Предыдущий рейтинг:

Источник

Обход графа или как проехать из . в . на Php

Здравствуйте, уважаемый разработчики. Пишу эту заметку после длительной паузы: как всегда нехватка времени или попросту неумение им распоряжаться. Но главное я опять с вами и сегодня я расскажу вам немного о графах, а точнее о поиске кратчайшего маршрута. Будем разбирать на примере поиска маршрута между станциями метро Московского метрополитена. И в конце заметки вас будет ждать маленький пример, наглядно демонстрирующий решение.

Итак, поехали. У нас имеется неориентированный граф (в метро можно проехать как от станции-источник до станции-назначение, так и наоборот). Описывать мы его будем совсем просто и очень понятно: массив, ключи которого – это станции-источник, а значения для этого ключа – станции, в которые из источника мы можем попасть. К примеру,

php $graph = array(  'Севастопольская' => array('Чертановская', 'Нахимовский проспект', 'Каховская') ); ?>

Из станции Севастопольская мы можем попасть в Чертановскую, Нахимовский проспект и в Каховскую. Единственный недостаток подобного метода описания неориентированного графа – это избыточность, но она с лихвой нивелируется простотой и наглядностью записи.

Давайте я для нетерпеливых приведу пример кода, а потом прокомментирую некоторые моменты.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93

Строки 9-31, содержащие функцию, самые интересные и в них заключается всю изюминка алгоритма по поиску в глубину. Алгоритмы можно вкратце описать так: для вершины, которую мы еще не посетили, нужно отыскать все еще не посещенные смежные вершины и повторить поиск для них. Данная реализация взята из документации к Python, который я понемногу изучаю, и немного изменена.

Строки 33-53 описывают граф, в котором мы и будем искать кратчайший путь (я не стал описывать все станции метро, коих больше двухсот – для наглядного примера подобного участка должно хватить).

Строки 58-72 проверяют были ли переданы данные через форму, проверяют их корректность (значения, полученные из формы, должны содержаться в нашем графе) и выводят результат в виде ненумерованного списка с подсвеченными первой и последней вершинами.

В довершении мы выводим форму, состоящую из двух select-ов, содержащих станции метро и кнопки “Поехали!”, после нажатии на которую и происходит поиск по графу.

Вместо заключения хочется отметить, что графы очень интересная тема дискретной математики, позволяющая решать большое множество сложных и не очень задач.

Поменьше багов вам в коде и удачи 🙂

Источник

PHP: Алгоритм Дейкстры — поиск кратчайшего пути

Поиск самого выгодного (быстрого, дешёвого: зависит от выбранного веса) пути с помощью алгоритма на взвешенных графах. «Алгоритм Дейкстры» находит кратчайшие пути от одной из вершин графа до всех остальных.

Для примера найдём самый быстрый путь из точки A в точку D.

Каждая точка — это узел (node). Линия, соединяющая точки — это ребро. Между точками указан вес — время для перехода от точки к точке.

$target = 'D'; // Граф для моделирования связи между узлами (определения соседей) $graph = [ 'A' => [ // из А можно попасть в точки B и C 'B' => 9, 'C' => 3, ], 'C' => [ 'B' => 4, 'D' => 7, ], 'B' => [ 'D' => 1, ], 'D' => [] ]; // Хранит время, которое потребуется для перехода к узлу от начального узла A $times = [ 'B' => 9, // Из точки А в точку B можно добраться за 9 минут 'C' => 3, 'D' => INF // Неизвестно (равно бесконечности) время, которое потребуется, чтобы добраться из точки А в точку D ]; // Хранит родителя - узел из которого пришли $parents = [ 'B' => 'A', // В точку B пришли из точки А 'C' => 'A', 'D' => null, // Неизвестно как попасть в точку D ];

Во процессе работы алгоритма будут обновляться массивы times и parents. В каждой итерации алгоритм ищет узел, до которого можно добраться за минимальное время и обновляет общее время.

class dijkstra < private $checked; public function __construct() < $this->checked = []; > function findFastestNode( $times ) < $minTime = INF; $fastestNode = null; foreach( $times as $n =>$time ) < if( $time < $minTime AND !in_array( $n, $this->checked ) ) < $minTime = $time; $fastestNode = $n; >> return $fastestNode; > public function find( $graph, $times, $parents, $target ) < $node = $this->findFastestNode( $times ); while( $node != null ) < $time = $times[ $node ]; $neighbors = $graph[ $node ]; foreach( $neighbors as $neighborNode =>$neighborTime ) < $newTime = $time + $neighborTime; if( $times[ $neighborNode ] >$newTime ) < $times[ $neighborNode ] = $newTime; $parents[ $neighborNode ] = $node; >> array_push( $this->checked, $node ); $node = $this->findFastestNode( $times ); > echo '', var_dump( $times ) ,'
 '; // > array(3) < // >["B"]=> // > int(7) // > ["C"]=> // > int(3) // > ["D"]=> // > int(8) // > > // В результате: // минимальное время из точки A в точку B равно 7 // минимальное время из точки A в точку С равно 3 // минимальное время из точки A в точку D равно 8 echo '
 ', var_dump( $parents ) ,'
 '; // > array(3) < // >["B"]=> // > string(1) "C" // > ["C"]=> // > string(1) "A" // > ["D"]=> // > string(1) "B" // > > // В результате: // в точку D пришли из точки B // в точку B пришли из точки C // в точку C пришли из точки A // Маршрут А -> С -> B -> D за минимальное время = 8 return $times[ $target ]; > > $alg = new dijkstra(); $minTime = $alg->find( $graph, $times, $parents, $target ); echo 'Минимальное время из А в '. $target .' составляет: '. $minTime ; // > Минимальное время из А в D составляет: 8
 Источник