2017自如技术大赛研发组题目七：单源最短路径算法问题
7. 自如今年年底就会拥有50W间房子，大家知道每间房房子都是需要配置完才能出租给自如客的，整个房租的配置过程是很复杂的，每天都需要大量的物流师傅将家电，家具等物品从仓库送到需要配置的每个房间。为了能在更多的时间配置更多的房子，我要不断的优化物流从仓库A到房间G的路径或者仓库B到房间E的距离，请写出一种算法给你任意图中两点，计算出两点之间的最短距离。
注：A B C D E F G H 都可能是仓库或者房间，点与点之间是距离
示例：
输入：AE
输出：最短距离：22
【PHP实现】
注：A B C D E F G H 都可能是仓库或者房间，点与点之间是距离
示例：
输入：AE
输出：最短距离：22
【PHP实现】
<?php
/**
* Class Road
* 两点间最短路径计算类
* User: 郑凯
* Date: 2017/12/2
* Time: 19:48
* Dijkstra 算法，迪科斯彻算法（Dijkstra），又称为单源最短路径算法。
* Dijstra算法是运用贪心的策略，从源点开始，不断地通过相联通的点找出到其他点的最短距离。
*/
class Road {
//节点对应的字母名
public $pointName = array(
0 => "A",
1 => "B",
2 => "C",
3 => "D",
4 => "E",
5 => "F",
6 => "G",
7 => "H",
);
//地图上的点已经点之间的路径长度
public $points = array(
"A" => array(
"A" => 0,
"B" => 15,
"C" => 6,
"D" => 0,
"E" =>0,
"F" =>25,
"G" =>0,
"H" =>0
),
"B" => array(
"A" => 15,
"B" => 0,
"C" => 9,
"D" => 0,
"E" =>7,
"F" =>0,
"G" =>0,
"H" =>0
),
"C" => array(
"A" => 6,
"B" => 9,
"C" => 0,
"D" => 11,
"E" =>0,
"F" =>0,
"G" =>0,
"H" =>0
),
"D" => array(
"A" => 0,
"B" => 0,
"C" => 11,
"D" => 0,
"E" =>12,
"F" =>0,
"G" =>0,
"H" =>5
),
"E" => array(
"A" => 0,
"B" => 7,
"C" => 0,
"D" => 12,
"E" =>0,
"F" =>5,
"G" =>0,
"H" =>7
),
"F" => array(
"A" => 25,
"B" => 0,
"C" => 0,
"D" => 0,
"E" =>5,
"F" =>0,
"G" =>12,
"H" =>0
),
"G" => array(
"A" => 0,
"B" => 0,
"C" => 0,
"D" => 0,
"E" =>0,
"F" =>12,
"G" =>0,
"H" =>17
),
"H" => array(
"A" => 0,
"B" => 0,
"C" => 0,
"D" => 5,
"E" =>7,
"F" =>0,
"G" =>17,
"H" =>0
),
);
//有向图存储
private $graph = array(
array(0,15,6,0,0,25,0,0),
array(15,0,9,0,7,0,0,0),
array(6,9,0,11,0,0,0,0),
array(0,0,11,0,12,0,0,5),
array(0,7,6,12,0,5,0,7),
array(25,0,6,0,5,0,12,0),
array(0,0,0,0,0,12,0,17),
array(0,0,0,5,7,25,17,0)
);
//设置一个无穷大距离的数字
private $soBig = 999999;
private $path = array();
private function getOptimalPath($a, $b)
{
if($a == $b){
return "start and end could not be one point";
}
//读取已经选择的点
$idx = array_keys($this->points);
$a = array_search($a, $idx);
$b = array_search($b, $idx);
//存储路径上节点距离$a点的最小距离
$c = array();
$path = array();
//初始化距离起点最近的节点的最小距离
for($i=1;$i<8;$i++)
{
if($this->graph[$a][$i]>0)
{
$c[$i] = $this->graph[$a][$i];
$path[$i]['name'] = $this->pointName[$a];
$path[$i]['key'] = $a;
}
else
{
$c[$i] = $this->soBig;
}
}
//用于存储已经选择的节点
$selected = array($a);
$all = array(1,2,3,4,5,6,7);
unset($all[$a-1]);
$others = $all;
// n-1次循环完成转移节点任务
for($i=0;$i<count($this->graph)-1;$i++)
{
//查找剩余节点中距离起点最近的节点v
$current_min = $this->soBig;
$current_min_v = 0;
foreach($others as $k=>$v)
{
if($c[$v] < $current_min)
{
$current_min = $c[$v];
$current_min_v = $v;
}
}
//从$others更新顶点到$selected中
array_push($selected,$current_min_v);
array_splice($others,array_search($current_min_v,$others),1);
//更新最短路径
foreach($others as $k=>$u)
{
if($this->graph[$current_min_v][$u]!=0&&$c[$u]>$c[$current_min_v]+$this->graph[$current_min_v][$u])
{
$path[$u]['name'] = $this->pointName[$current_min_v];
$path[$u]['key'] = $current_min_v;
$c[$u] = $c[$current_min_v]+$this->graph[$current_min_v][$u];
}
}
}
$this->getRoadLine($path,$b,$a);
$finalPath = $this->pointName[$a];
foreach(array_reverse($this->path) as $x => $y){
$finalPath.=$y;
}
$finalPath.=$this->pointName[$b];
return $c[$b]." ".$finalPath;
}
//获取路径信息
public function getRoadLine($path,$b,$a)
{
if($path[$b]['key'] !== $a){
$this->path = $path[$b]['name'];
$this->getRoadLine($path,$path[$b]['key'],$a);
}
}
public function getResult($towPoint){
return $this->getOptimalPath(substr($towPoint,0,1),substr($towPoint, -1));
}
}
//获取输入变量
$params = trim(fgets(STDIN), " \t\n\r\0\x0B");
$road = new Road();
echo $road->getResult($params);
