PHP 实现迪杰斯特拉算法, 并由小顶堆优化
- PHP
- class DEdge
- {
- public $nextIndex, $length;
- public function __construct($nextIndex, $length)
- {
- $this->nextIndex = $nextIndex;
- $this->length = $length;
- }
- }
- class DNode
- {
- public $index, $distance, $edges = [];
- public function __construct($index, $distance)
- {
- $this->index = $index;
- $this->distance = $distance;
- }
- public function addEdge(DEdge $edge)
- {
- $this->edges[] = $edge;
- }
- }
- class Dijkstra
- {
- protected $origin;
- protected $graph = [], $dGraph = [], $heap = [], $visited = [], $heapVisited = [];
- public function __construct(array $graph, $origin)
- {
- $this->graph = $graph;
- $this->origin = $origin;
- $this->visited[$origin] = true;
- $this->initializeGraph();
- $this->initializeHeap();
- $this->calculateDistance();
- }
- public function printDistance()
- {
- foreach ($this->dGraph as $dNodes) {
- var_dump([$dNodes->index, $dNodes->distance]);
- }
- }
- protected function initializeGraph()
- {
- foreach ($this->graph as $index => $edges) {
- $dNode = new DNode($index, $edges[$this->origin]);
- foreach ($edges as $toIndex => $edge) {
- $dNode->addEdge(new DEdge($toIndex, $edge));
- }
- $this->dGraph[$dNode->index] = $dNode;
- }
- }
- protected function initializeHeap()
- {
- foreach ($this->dGraph as $index => $node) {
- if ($index != $this->origin && $node->distance != INF) {
- $this->addToHeap($node);
- }
- }
- }
- protected function calculateDistance()
- {
- while (($nearestNode = $this->heapPop()) != null) {
- foreach ($nearestNode->edges as $edge) {
- if ($this->dGraph[$edge->nextIndex]->distance>
- $nearestNode->distance + $edge->length) {
- $this->dGraph[$edge->nextIndex]->distance =
- $nearestNode->distance + $edge->length;
- if (!isset($this->heapVisited[$edge->nextIndex])) {
- $this->addToHeap($this->dGraph[$edge->nextIndex]);
- } else {
- $this->keepHeap($this->heapVisited[$edge->nextIndex]);
- }
- }
- }
- }
- }
- protected function heapPop()
- {
- $heapCount = count($this->heap);
- if ($heapCount> 0) {
- $this->swap(0, $heapCount - 1);
- }
- $pop = array_pop($this->heap);
- $this->keepHeap(0, false);
- return $pop;
- }
- protected function keepHeap($startAt, $up = true)
- {
- if ($up) {
- while ($startAt> 0) {
- $parentIndex = intval(($startAt - 1) / 2);
- if ($this->heap[$parentIndex]->distance> $this->heap[$startAt]->distance) {
- $this->swap($parentIndex, $startAt);
- $startAt = $parentIndex;
- $this->heapVisited[$this->heap[$startAt]->index] = $startAt;
- } else {
- break;
- }
- }
- } else {
- $lastIndex = count($this->heap) - 1;
- while ($startAt <$lastIndex) {
- $lIndex = 2 * $startAt + 1;
- $rIndex = $lIndex + 1;
- if (isset($this->heap[$rIndex])) {
- $minIndex = $this->heap[$lIndex]->distance <$this->heap[$rIndex]->distance ? $lIndex : $rIndex;
- } else if (isset($this->heap[$lIndex])) {
- $minIndex = $lIndex;
- } else {
- break;
- }
- if ($this->heap[$startAt]->distance> $this->heap[$minIndex]->distance) {
- $this->swap($minIndex, $startAt);
- $startAt = $minIndex;
- $this->heapVisited[$this->heap[$startAt]->index] = $startAt;
- } else {
- break;
- }
- }
- }
- }
- protected function addToHeap(DNode $dNode)
- {
- $this->heap[] = $dNode;
- $this->keepHeap(count($this->heap) - 1);
- }
- protected function swap($index1, $index2)
- {
- list($this->heap[$index1], $this->heap[$index2]) =
- [$this->heap[$index2], $this->heap[$index1]];
- }
- }
- $graph = [
- [0, 4, INF, 2, INF],
- [4, 0, 4, 1, INF],
- [INF, 4, 0, 1, 3,],
- [2, 1, 1, 0, 7],
- [INF, INF, 3, 7, 0],
- ];
- $start = 0;
- $dijkstra = new Dijkstra($graph, $start);
- $dijkstra->printDistance();
来源: http://www.bubuko.com/infodetail-3123377.html