优先级队列（小顶堆）的dijkstra算法

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();