<?php
class Dijkstra {
    private const INFINIRY = 1e9;
    private
        $graph,
        $used = [],
        $sumWays = [],
        $path = [];

    public function __construct($graph) {
        $this->graph = $graph;
    }

    public function main($from, $to) {
        $this->init();
        $this->sumWays[$from] = 0;
        while($currNode = $this->findNearestUnusedNode())
            $this->setSumWaysToNextNodes($currNode);
        return $this->restorePath($from, $to);
    }

    private function init() {
        foreach ($this->graph->getNodes() as $node) {
            $this->used[$node] = false;
            $this->sumWays[$node] = self::INFINIRY;
        }
    }

    private function findNearestUnusedNode() {
        $nearestNode = '';
        foreach ($this->graph->getNodes() as $node)
            if (!$this->used[$node])
                if ($nearestNode == '' || $this->sumWays[$node] < $this->sumWays[$nearestNode])
                    $nearestNode = $node;
        return $nearestNode;
    }

    private function setSumWaysToNextNodes($currentNode) {
        $this->used[$currentNode] = true;
        foreach ($this->graph->getEdges($currentNode) as $nextNode => $length)
            if (!$this->used[$nextNode]) {
                $newSumWays = $this->sumWays[$currentNode] + $length;
                if ($newSumWays < $this->sumWays[$nextNode]) {
                    $this->sumWays[$nextNode] = $newSumWays;
                    $this->path[$nextNode] = $currentNode;
                }
            }
    }

    private function restorePath($from, $to) {
        $path = $to;
        while ($to != $from) {
            $to = $this->path[$to];
            $path = $to.$path;
        }
        return $path;
    }
}