* @date 2017/8/23
* @license MIT
* -------------------------------------------------------------
* æ€è·¯åˆ†æžï¼šå•æºæœ€çŸè·¯å¾„问题
* -------------------------------------------------------------
* Dijkstra 算法一般的表述通常有两ç§æ–¹å¼ï¼Œä¸€ç§ç”¨æ°¸ä¹…å’Œä¸´æ—¶æ ‡å·æ–¹å¼ï¼Œä¸€ç§æ˜¯ç”¨OPEN, CLOSE表的方å¼ï¼Œ
* 这里å‡é‡‡ç”¨æ°¸ä¹…å’Œä¸´æ—¶æ ‡å·çš„æ–¹å¼ã€‚注æ„该算法è¦æ±‚图ä¸ä¸å˜åœ¨è´Ÿæƒè¾¹ã€‚
* å› æ¤ï¼Œåœ¨åŒ…å«è´Ÿè¾¹å…¨çš„图ä¸è¦æ‰¾å‡ºæœ€çŸè·¯å¾„，å¯ä»¥ä½¿ç”¨å¦ä¸€ç§ç®—法 -- è´å…‹æ›¼-ç¦å¾·ç®—法
*/
// +--------------------------------------------------------------------------
// | 解题方å¼
// +--------------------------------------------------------------------------
/**
* DijkstraQuery
*
* @uses PHPStorm
* @version 1.0
* @author Pu ShaoWei
*/
class DijkstraQuery
{
/**
* @var array
*/
protected $graph;
/**
* @var array
*/
protected $processed;
/**
* @var int
*/
protected $infinity;
/**
* @var string
*/
protected $start;
/**
* @var string
*/
protected $end;
/**
* DijkstraQuery constructor.
*
* @param array $graph
* @param $start
* @param $end
*/
public function __construct(array $graph, $start, $end)
{
$this->graph = $graph;
$this->start = $start;
$this->end = $end;
$this->processed = array ();
$this->infinity = mt_getrandmax();
}
/**
* 最çŸè·¯å¾„
*
* @return string
*/
public function calculate()
{
$costs = $this->graph[$this->start];
$costs[$this->end] = $this->infinity;
$node = $this->findLowestCostNode($costs);
while (null !== $node) {
$cost = $costs[$node];
$neighbors = $this->graph[$node] ?? array ();
foreach ($neighbors as $neighbor => $distance) {
$newCost = $cost + $distance;
if ($costs[$neighbor] > $newCost) {
$costs[$neighbor] = $newCost;
}
}
array_push($this->processed, $node);
$node = $this->findLowestCostNode($costs);
}
return 'The shortest distance for：' . $costs[$this->end];
}
/**
* findLowestCostNode
*
* @param $costs
* @return null
*/
protected function findLowestCostNode($costs)
{
$lowestCost = $this->infinity;
$lowestCostNode = null;
foreach ($costs as $node => $cost) {
if ($cost < $lowestCost && !in_array($node, $this->processed)) {
$lowestCost = $cost;
$lowestCostNode = $node;
}
}
return $lowestCostNode;
}
}
// +--------------------------------------------------------------------------
// | éªŒè¯ me --> claire
// +--------------------------------------------------------------------------
// ∞
$graph = array (
'me' => array (
'alice' => 6,
'bob' => 2,
),
'alice' => array (
'claire' => 1,
),
'bob' => array (
'alice' => 3,
'claire' => 5,
),
'claire' => array (// 没有任何邻居
),
);
echo (new DijkstraQuery($graph, 'me', 'claire'))->calculate();