Online PHP editor | refs for 36R1K

<?php class Graph { private $graph = []; private $nodes = []; public function __construct(array $edges) { foreach ($edges as $edge => $weight) { $start = $edge[0]; $end = $edge[1]; $this->graph[$start][$end] = $weight; $this->graph[$end][$start] = $weight; $this->nodes[$start] = [ 'L' => INF, 'Q' => null, 'final' => false, ]; $this->nodes[$end] = [ 'L' => INF, 'Q' => null, 'final' => false, ]; } } public function find($start, $end, $initStartNode = true) { if ($initStartNode) { $this->initStartNode($start); } $nodes = $this->getNextNodes($start); $startLength = $this->getLength($start); foreach($nodes as $node => $weight) { $currentLength = $this->getLength($node); if ($startLength + $weight < $currentLength) { $this->setLength($node, $startLength + $weight); $this->setFromNode($node, $start); } } $nextNode = $this->getNextMinimumNode(); if (is_null($nextNode)) { return $this->getNodes(); } $this->setFinal($nextNode); $this->find($nextNode, $end, false); // var_dump($this->getGraph()); var_dump($this->getNodes()); // die(); } protected function getNextMinimumNode() { $nodes = $this->getNodes(); $min = INF; $minNode = null; foreach ($nodes as $node => $data) { if ($data['final']) { continue; } $nodeLength = $this->getLength($node); if ($nodeLength < $min) { $min = $nodeLength; $minNode = $node; } } return $minNode; } protected function initStartNode($node) { $this->setLength($node, 0); $this->setFromNode($node, '-'); $this->setFinal($node); } protected function getNextNodes($node) { return $this->graph[$node]; } protected function setLength($node, $value) { $this->nodes[$node]['L'] = $value; } protected function getLength($node) { return $this->nodes[$node]['L']; } protected function setFromNode($node, $value) { $this->nodes[$node]['Q'] = $value; } protected function setFinal($node) { $this->nodes[$node]['final'] = true; } public function getGraph() { return $this->graph; } public function getNodes() { return $this->nodes; } } $g = new Graph([ 'AB' => 5, 'AC' => 2, 'CB' => 2, 'CD' => 8, 'BE' => 7, 'DE' => 1, ]); $result = $g->find('A', 'E'); var_dump($result); // var_dump($g->getGraph()); // var_dump($g->getNodes());