<?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)
{
$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);
}
}
// var_dump($this->getGraph());
var_dump($this->getNodes());
die();
}
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());
preferences:
30.9 ms | 402 KiB | 5 Q