<?php
$graph = new Graph();
$graph->addNode('1');
$graph->addNode('2');
$graph->addNode('3');
$graph->addNode('4');
$graph->addNode('5');
$graph->addEdge('1', '2', 100);
$graph->addEdge('1', '4', 1);
$graph->addEdge('4', '5', 1);
$graph->addEdge('5', '3', 1);
$graph->addEdge('3', '2', 1);
$result = $graph->findShortestPath('1', '2');
print_r($result);
class Graph
{
private array $nodes = []; // Массив для хранения узлов и их соединений (ребер)
private array $matrix = []; // Массив для хранения матричного представления графа
// Добавляет узел в граф
public function addNode(string $node): void
{
if (!isset($this->nodes[$node])) {
$this->nodes[$node] = [];
}
}
// Добавляет ребро между двумя узлами с указанным весом
public function addEdge(string $from, string $to, int $weight): void
{
$this->nodes[$from][$to] = $weight;
$this->nodes[$to][$from] = $weight;
}
// Находит кратчайший путь между начальным и конечным узлами
public function findShortestPath(string $start, string $end): array
{
$visited = []; // Массив для хранения статуса посещения каждого узла
$distances = []; // Массив для хранения текущего кратчайшего расстояния до каждого узла
$previousNodes = []; // Массив для хранения предыдущего узла в пути для каждого узла
$nodes = array_keys($this->nodes);
// Инициализация массивов значениями по умолчанию
foreach ($nodes as $node) {
$visited[$node] = false;
$previousNodes[$node] = null;
$distances[$node] = INF;
}
$distances[$start] = 0;
$currentNode = $start;
// Основной цикл для обработки каждого узла
while ($currentNode !== null) {
$neighbors = $this->nodes[$currentNode];
$currentDistance = $distances[$currentNode];
// Обработка соседей текущего узла
foreach ($neighbors as $neighbor => $weight) {
$newDistance = $currentDistance + $weight;
// Обновление расстояния до соседа, если найден более короткий путь
if ($newDistance < $distances[$neighbor]) {
$distances[$neighbor] = $newDistance;
$previousNodes[$neighbor] = $currentNode;
}
}
// Отмечаем текущий узел как посещенный
$visited[$currentNode] = true;
// Находим следующий непосещенный узел с кратчайшим расстоянием
$currentNode = null;
$minDistance = INF;
foreach ($nodes as $node) {
if (!$visited[$node] && $distances[$node] < $minDistance) {
$currentNode = $node;
$minDistance = $distances[$node];
}
}
}
// Восстанавливаем кратчайший путь из массива предыдущих узлов
$path = [];
$currentNode = $end;
while ($currentNode !== null) {
$path[] = $currentNode;
$currentNode = $previousNodes[$currentNode];
}
// Разворачиваем путь и возвращаем его вместе с общим весом
$path = array_reverse($path);
return [
'path' => $path,
'totalWeight' => $distances[$end],
];
}
}
?>