Пример алгоритма Дейктры
Алгоритм Дейкстры — один из наиболее известных методов нахождения кратчайших путей между вершинами графа. Вот простая реализация на PHP, иллюстрирующая работу этого алгоритма:
<?php
// Граф представлен матрицей смежности
$graph = [
[0, 7, 9, 0, 0],
[7, 0, 10, 15, 0],
[9, 10, 0, 11, 0],
[0, 15, 11, 0, 6],
[0, 0, 0, 6, 0]
];
// Функция реализации алгоритма Дейкстры
function dijkstra($graph, $startVertex)
{
// Количество вершин в графе
$numVertices = count($graph);
// Массив расстояний от стартовой вершины до всех остальных вершин
$distances = array_fill(0, $numVertices, INF); // Изначально расстояния бесконечны
$visited = array_fill(0, $numVertices, false); // Флаг посещённых вершин
// Расстояние до самой себя равно нулю
$distances[$startVertex] = 0;
for ($i = 0; $i < $numVertices - 1; ++$i) {
// Ищем минимальную дистанцию среди непосещенных вершин
$minDistance = INF;
$u = null;
foreach ($distances as $v => $dist) {
if (!$visited[$v] && $dist <= $minDistance) {
$minDistance = $dist;
$u = $v;
}
}
// Отмечаем найденную вершину как посещённую
$visited[$u] = true;
// Обновляем расстояния до соседних вершин
foreach ($graph[$u] as $v => $weight) {
if ($weight > 0 && !$visited[$v]) { // Если есть ребро и вершина ещё не посещалась
$newDist = $distances[$u] + $weight;
if ($newDist < $distances[$v]) {
$distances[$v] = $newDist;
}
}
}
}
return $distances;
}
// Пример запуска алгоритма
$startVertex = 0; // Стартовая вершина
$result = dijkstra($graph, $startVertex);
echo "Кратчайшие пути от вершины №{$startVertex}:\n";
foreach ($result as $vertex => $distance) {
echo "Вершина {$vertex}: расстояние = {$distance}\n";
}Как работает этот код?
- Матрица смежности: Мы задаём матрицу весов рёбер графа (
$graph). Например,graph[i][j]показывает длину ребра между вершиной i и j. Значение0означает отсутствие связи. - Функция Dijkstra: Она принимает два аргумента — сам граф и начальную вершину. Алгоритм последовательно выбирает ближайшую доступную вершину и обновляет кратчайшие пути ко всем её соседям.
- Результат: После завершения цикла алгоритм возвращает массив кратчайших расстояний от начальной вершины до каждой вершины графа.
Этот пример подходит для простых графов и небольших входных данных. Для больших графов потребуется оптимизация структуры хранения и выбор приоритетной очереди.