$list = [
[1,3,10],
[1,5,30],
[1,6,100],
[2,3,5],
[3,4,50],
[4,6,10],
[5,6,60],
[5,4,20]
];
$point_num = 6;
$a = []; //总数组
$b = []; //当前最短路径
$c = []; //已经遍历的顶点
$max_v = 10000;
for ($i=1; $i <=$point_num ; $i++) {
for ($j=1; $j <=$point_num ; $j++) {
$a[$i][$j] = $max_v;
}
}
foreach ($list as $v) {
$a[$v[0]][$v[1]] = $v[2];
}
//计算顶点1到各个顶点的最短路径
$b = $a[1];
$c[] = 1;
cal($a, $b, $c, $max_v);
function cal($a, $b, $c, $max_v){
$min_k = find_min($b, $c);
if ($min_k == -1) {
var_dump($b);exit;
}
$c[] = $min_k;
$tmp = $a[$min_k];
foreach ($tmp as $k => $v) {
if ($v == $max_v) {
continue;
}
if ($v + $b[$min_k] < $b[$k]) {
$b[$k] = $v + $b[$min_k];
}
}
cal($a, $b, $c, $max_v);
}
function find_min($b, $c){
$min_k = -1;
foreach ($b as $k => $v) {
if (in_array($k, $c)) {
continue;
}
if ($min_k == -1) {
$min_k = $k;
continue;
}
if ($v < $b[$min_k]) {
$min_k = $k;
continue;
}
}
return $min_k;
}
最短路径-PHP简单实现
©著作权归作者所有,转载或内容合作请联系作者
- 文/潘晓璐 我一进店门，熙熙楼的掌柜王于贵愁眉苦脸地迎上来，“玉大人，你说我怎么就摊上这事。” “怎么了？”我有些...
- 文/花漫 我一把揭开白布。 她就那样静静地躺着，像睡着了一般。 火红的嫁衣衬着肌肤如雪。 梳的纹丝不乱的头发上，一...
- 文/苍兰香墨 我猛地睁开眼，长吁一口气：“原来是场噩梦啊……” “哼！你这毒妇竟也来了？” 一声冷哼从身侧响起，我...
推荐阅读更多精彩内容
- 1.几个定义 1.1 最短路径 定义从节点u到节点v的最短路径权重δ(u, v)如下： 从节点u到节点v的最短路径...
- 直接说基础语法，也许大家不会感兴趣。前言之后的这一章，给大家介绍一下我最近写出来的一个小功能。用python语言实...
- 【3·17】子贡欲去告朔之饩羊。子曰：“赐也！尔爱其羊，我爱其礼。” 告朔：朔，农历每月初一为朔日。告朔，古代制度...
