image.png

<?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”

}

}