札记之PHP实现Dijkstra算法[优先队列]

迪杰斯特拉(Dijkstra)算法是典型最短路径算法，用于计算一个节点到其他节点的最短路径。
它的主要特点是以起始点为中心向外层层扩展(广度优先搜索思想)，直到扩展到终点为止。

图示

算法思路

• 指定一个节点，例如我们要计算 ‘A’ 到其他节点的最短路径；
• 定义两个数组（$distance，$previous), distance包含已求出的最短路径点(以及相应的最短长度)，previous包含最短顶点的前一个顶点
• 采用优先队列，顶点之间的距离从小到大入队，从小到大出队挨个进行比较；
• 通过前置顶点结果集找出终点对应点的集合；

PHP代码实现

//优先队列
class PriorityList 
{
    public $next;
    public $data;

    function __construct($data) 
    {
        $this->next = null;
        $this->data = $data;
    }
}

class PriorityQueue 
{
    private $size;
    private $liststart;
    private $comparator;
    
    function __construct($comparator) 
    {
        $this->size = 0;
        $this->liststart = null;
        $this->comparator = $comparator;
    }
    
    function enqueue($data) 
    {
        $this->size = $this->size + 1;
        if ($this->liststart == null) {
            $this->liststart = new PriorityList($data);
            return;
        }
        
        $lastnode = null;
        $added = false;
        $node = $this->liststart;
        $comparator = $this->comparator;

        $newnode = new PriorityList($data);
        while ($node) {
            if ($comparator($newnode, $node) < 0) {
                // 如果新节点小于其他节点，则排最前面
                $newnode->next = $node;
                if ($lastnode == null) {
                    $this->liststart = $newnode;
                } else {
                    $lastnode->next = $newnode;
                }
                $added = true;
                break;
            }
            $lastnode = $node;
            $node = $node->next;
            
            if (!$added) {
                $lastnode->next = $newnode;
            }
        }
    }
    
    function debug()
    {
        $i = 0;
        $node = $this->liststart;
        
        if (!$node) {
            print "<< No nodes >>\n";
            return;
        }
        while ($node) {
            print "[$i]=" . $node->data[1] . " (" . $node->data[0] . ")\n";
            $node = $node->next;
            $i++;
        }
    }
    
    function size()
    {
        return $this->size;
    }

    function peak() 
    {
        return $this->liststart->data;
    }
    
    function remove() 
    {
        $data = $this->peak();
        $this->size = $this->size - 1;
        $this->liststart = $this->liststart->next;
        return $data;
    }
}

class Edge 
{   
    public $start;
    public $end;
    public $weight;
    
    public function __construct($start, $end, $weight) 
    {
        $this->start = $start;
        $this->end = $end;
        $this->weight = $weight;
    }
}

class Graph 
{   
    public $nodes = array();
    public function addedge($start, $end, $weight = 0) 
    {
        if (!isset($this->nodes[$start])) {
            $this->nodes[$start] = array();
        }
        array_push($this->nodes[$start], new Edge($start, $end, $weight));
    }
    
    public function removenode($index)
    {
        array_splice($this->nodes, $index, 1);
    }
   
    public function pathsFrom($from) 
    {
        $dist = array();
        $visited = $previous = array();
        //起始点
        $dist[$from] = 0;
        //入优先队列
        $queue = new PriorityQueue("compareWeights");
        $queue->enqueue(array($dist[$from], $from));
        
        $nodes = $this->nodes;
        while ($queue->size() > 0) {
            //获取顶点，距离
            list($distance, $vertex) = $queue->remove();
            if (isset($visited[$vertex])) {
                continue;
            }

            $visited[$vertex] = True;
            if (!isset($nodes[$vertex])) {
                print "WARNING: '$vertex' is not found in the node list\n";
            }

            foreach ($nodes[$vertex] as $edge) {
                //距离比较
                $alt = $dist[$vertex] + $edge->weight;
                $end = $edge->end;
                if (!isset($dist[$end]) || $alt < $dist[$end]) {
                    $previous[$end] = $vertex;
                    $dist[$end] = $alt;
                    $queue->enqueue(array($dist[$end], $end));
                }
            }
        }
        return array($dist, $previous);
    }
    
    //获取前置顶点
    public function pathsTo($nodeDistance, $toNode) 
    {
        $current = $toNode;
        $path = array();
        
        if (isset($nodeDistance[$current])) {
            array_push($path, $toNode);
        }
        while (isset($nodeDistance[$current])) {
            $nextnode = $nodeDistance[$current];
            array_push($path, $nextnode);
            
            $current = $nextnode;
        }
        
        return array_reverse($path);
    }
    
    public function getpath($from, $to) 
    {
        list($distances, $prev) = $this->pathsFrom($from);
        return $this->paths_to($prev, $to);
    }
}

function compareWeights($a, $b) 
{
    return $a->data[0] - $b->data[0];
}

$g = new Graph();
$g->addedge("a", "b", 1);
$g->addedge("a", "c", 3);
$g->addedge("a", "d", 4);

$g->addedge("b", "a", 1);
$g->addedge("b", "d", 2);

$g->addedge("c", "a", 3);
$g->addedge("c", "d", 5);

$g->addedge("d", "a", 4);
$g->addedge("d", "b", 2);
$g->addedge("d", "c", 5);

list($distances, $prev) = $g->pathsFrom("a");
var_dump($distances, $prev);
$path = $g->pathsTo($prev, "d");
print_r($path);

运行结果

array(4) {
  'a' =>
  int(0)
  'b' =>
  int(1)
  'c' =>
  int(3)
  'd' =>
  int(3)
}
array(3) {
  'b' =>
  string(1) "a"
  'c' =>
  string(1) "a"
  'd' =>
  string(1) "b"
}
Array
(
    [0] => a
    [1] => b
    [2] => d
)