最短路径算法-Dijkstra
<?php
//最短路径算法,核心思路是广度遍历
//一个p(a,b)表示a到b的最短距离路径，m,n是最短路径上的2个点，则p(a,m) p(m,n)一定是a到n的最短路径
//反证法：设q是a到n的最短距离，则有p(a,q) + p(q,n) < p(a,m) + p(m,n)
//p(a,q) + p(q,n) + (n,b) < p(a,m)+ p(m,n) + p(n,b) 即，p(a,q) + p(q,n) + p(n,b) < p(a,b)
//因为p(a,b)是最短距离，q不能比最短距离还短，所以，p(a,m) p(m,n)一定是最短距离
//使用二维数据来表示1个点到其它点之间的距离，为0表示无穷大
//aa = 0 ab = 2 ac = 0 ad = 1 ae = 5 af = 0 ag = 0
define("INT_MAX", 1000000);
$key_alphabet = array(0=>'a', 1=>'b', 2=>'c', 3=>'d', 4=>'e', 5=> 'f', 6=>'g');
$arr = array(
array(0, 2, 0, 1, 5, 0, 0), //a
array(2, 0, 4, 0, 0, 0, 0), //b
array(0, 4, 0, 0, 2, 0, 0), //c
array(1, 0, 0, 0, 2, 1, 0), //d
array(5, 0, 2, 2, 0, 0, 4), //e
array(0, 0, 0, 1, 0, 0, 3), //f
array(0, 0, 0, 0, 4, 3, 0), //g
);
$ready_array = array(0); //最短路径集合
$future_array = array(1, 2, 3, 4, 5, 6); //未加入最短路径集合
$d = array();
$d_path = $key_alphabet[0] . '->';
//初始化图中节点与源点0的最小距离
for ($i = 1; $i < 7; $i++) {
if ($arr[0][$i] > 0) {
$d[$i]['value'] = $arr[0][$i];
$d[$i]['path'] = $d_path . $key_alphabet[$i];
} else {
$d[$i]['value'] = INT_MAX;
$d[$i]['path'] = '';
}
}
// n-1次循环完成转移节点任务
for ($j = 1; $j < 7; $j++) {
// 查找剩余节点中距离源点最近的节点v
$current_min = INT_MAX;
$current_min_v = 0;
foreach ($future_array as $k => $v) {
if ($d[$v]['value'] < $current_min) {
$current_min = $d[$v]['value'];
$current_min_v = $v;
}
}
//$d_path .= $key_alphabet[$current_min_v] . '->';
//ab ac ad ae af ag 报存最短路径
//$d[$current_min_v]['path'] = $d_path;
$d[$current_min_v]['value'] = $current_min;
//array_push($d_path, $d_path.$key_alphabet[$current_min_v] .'->');
//从V中更新顶点到U中
array_push($ready_array, $current_min_v);
array_splice($future_array, array_search($current_min_v, $future_array), 1);
//var_dump($future_array);
//更新
foreach ($future_array as $k => $u) {
if ($arr[$current_min_v][$u] != 0 && $d[$u]['value'] > $d[$current_min_v]['value'] + $arr[$current_min_v][$u]) {
$d[$u]['value'] = $d[$current_min_v]['value'] + $arr[$current_min_v][$u];
$d[$u]['path'] = $d[$current_min_v]['path'] . '->' . $key_alphabet[$u];
}
}
}
var_dump($d);
//打印最短路径
function print_short_path($d, $begin)
{
echo $begin . "为起点的图的最短路径为：";
for ($i = 0; $i< 7; $i++) {
if($d[$i]!=INT_MAX)
echo $d[$i] ."=" . $d[$i];
else {
echo $d[$i] . "是无最短路径的";
}
}
}
//print_short_path($d, 6);
//var_dump('最短路径是: ' . $d_path );
//var_dump("最短路径是: " . $d[6]);
// foreach ($ready_array as $k => $u) {
// var_dump($k . '=>' . $key_alphabet[$u]);
// }
获得a点到各个点的最短路径和距离
array(6) {
[1]=>
array(2) {
["value"]=>
int(2)
["path"]=>
string(4) "a->b"
}
[2]=>
array(2) {
["value"]=>
int(5)
["path"]=>
string(10) "a->d->e->c"
}
[3]=>
array(2) {
["value"]=>
int(1)
["path"]=>
string(4) "a->d"
}
[4]=>
array(2) {
["value"]=>
int(3)
["path"]=>
string(7) "a->d->e"
}
[5]=>
array(2) {
["value"]=>
int(2)
["path"]=>
string(7) "a->d->f"
}
[6]=>
array(2) {
["value"]=>
int(5)
["path"]=>
string(10) "a->d->f->g"
}
}
