дейкстра

gistfile1.php

<?php

/**
 * Нахождение кратчайшего пути между двумя произвольными вершинами в графе
 * http://ru.wikipedia.org/wiki/Алгоритм_Дейкстры
 */
class Dijkstra
{
    private $_graph  = array();
    private $_nodes  = array();
    private $_result = array();

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

    public function calc($from, $to)
    {
        // сбрасываем предыдущие результаты
        $this->_nodes = $this->_result = array();
        foreach ($this->_graph as $path) {
            $this->_nodes[$path[0]][$path[1]] = $this->_nodes[$path[1]][$path[0]] = $path[2];
        }
        $this->_nodes[$from][$from] = 0; // чтобы лишний раз не считать

        $currentWeight = 0;
        $src           = $from;

        while ($this->_nodes) {
            $node = $this->_nodes[$src]; // берем ноду
            asort($node); // сортируем по весу

            // пробегаемся по всем ее соседям и пересчитываем их вес
            foreach ($node as $dest => $weight) {
                if (!isset($this->_result[$dest]) || ($currentWeight + $weight) < $this->_result[$dest]) {
                    $this->_result[$dest] = $currentWeight + $weight; // находим наименьшее растояние до этой точки
                }
            }
            unset($this->_nodes[$src]); // отмечаем как посчитанную

            // переходим к следующей вершине
            $node = array_intersect_key($node, $this->_nodes); // исключаем уже посещенные точки
            $src  = $node ? key($node) : key($this->_nodes); // если дальше нет свободной ноды то берем просто следующую непосчитанную из графа (???)
            $currentWeight = isset($this->_result[$src]) ? $this->_result[$src] : 0; // растояние до этой ноды от старта
        }

        return $this->_result[$to];
    }
}



$graph1 = array(
    array(1, 2, 7),
    array(1, 3, 9),
    array(1, 6, 14),
    array(2, 3, 10),
    array(2, 4, 15),
    array(3, 4, 11),
    array(3, 6, 2),
    array(4, 5, 6),
    array(5, 6, 9),
);

$graph2 = array(
    array("Barcelona", "Narbonne", 250),
    array("Narbonne", "Marseille", 260),
    array("Narbonne", "Toulouse", 150),
    array("Narbonne", "Geneve", 550),
    array("Marseille", "Geneve", 470),
    array("Toulouse", "Paris", 680),
    array("Toulouse", "Geneve", 700),
    array("Geneve", "Paris", 540),
    array("Geneve", "Lausanne", 64),
    array("Lausanne", "Paris", 536),
);

$dijkstra1 = new Dijkstra($graph1);
print $dijkstra1->calc(1, 5); // => 20

$dijkstra2 = new Dijkstra($graph2);
print $dijkstra2->calc('Barcelona', 'Lausanne'); // => 864