狄克斯特拉算法

定义

加权图运算图路径最低代价算法。主要包含四个步骤
1.找出最便宜的节点，即在最短时间内到达的节点。
2.更新该节点的邻居节点的开销，
3.重复这个过程。
4.计算最终路径。

代码模拟：

$arr_node = array(
    "start",
    "a",
    "b",
    "c",
    "d",
    "e",
    "finish"
);

$done = array();


$map = array();
$map["start"]["a"] = 2;
$map["start"]["b"] = 3;
$map["a"]["d"] = 6;
$map["a"]["e"] = 4;
$map["b"]["a"] = 4;
$map["b"]["c"] = 9;
$map["b"]["e"] = 7;
$map["c"]["finish"] = 1;
$map["d"]["e"] = 5;
$map["e"]["finish"] = 3;
$map["finish"] = array();


$parent = array();
$parent["a"] = "start";
$parent["b"] = "start";
$parent["c"] = "null";
$parent["d"] = "null";
$parent["e"] = "null";
$parent["finish"] = "null";


$costs["a"] = 2;
$costs["b"] = 3;
$costs["c"] = 99;
$costs["d"] = 99;
$costs["e"] = 99;
$costs["finish"] = 99;

function find_lowest_cost_node($costs, $done)
{
    $lowest_cost = 99;
    $lowest_cost_node = null;
    foreach ($costs as $key => $value) {
        $cost = $value;
        if ($cost < $lowest_cost && !in_array($key, $done)) {
            $lowest_cost = $cost;
            $lowest_cost_node = $key;
        }
    }
    return $lowest_cost_node;
}


$node = find_lowest_cost_node($costs, $done);

while ($node) {
    $cost = $costs[$node];
    $neighbors = $map[$node];

    foreach (array_keys($neighbors) as $item) {
        $new_cost = $cost + $neighbors[$item];
        if ($costs[$item] > $new_cost) {
            $costs[$item] = $new_cost;
            $parent[$item] = $node;
        }
    }

    array_push($done, $node);

    $node = find_lowest_cost_node($costs, $done);

}
$total = 0;
$backNode = "finish";
while ($backNode != "start") {
    $total += $map[$parent[$backNode]][$backNode];

    echo $backNode.PHP_EOL;
    $backNode = $parent[$backNode];
}
var_export($parent);
var_export($total);