首页 / 算法 / 用php实现flody算法输出
用php实现flody算法输出
内容导读
互联网集市收集整理的这篇技术教程文章主要介绍了用php实现flody算法输出，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含9363字，纯文字阅读大概需要14分钟。
内容图文
以下是我实现的flody算法，可是我在写output()函数时输不出来结果，请高手帮帮忙，写出来，不尽感激！ /**
* PHP 实现图邻接矩阵
*
* @author zhaojiangwei
* @since 2011/10/31 17:23
*/
class MGraph{
private $vexs; //顶点数组
private $arc; //边邻接矩阵,即二维数组
private $arcData; //边的数组信息
private $direct; //图的类型(无向或有向)
private $infinity = 65535;//代表无穷,即两点无连接,建带权值的图时用,本示例不带权值
public function MGraph($vexs, $arc, $direct = 0){
$this->vexs = $vexs;
$this->arcData = $arc;
$this->direct = $direct;
$this->initalizeArc();
$this->createArc();
}
private function initalizeArc(){
foreach($this->vexs as $value){
foreach($this->vexs as $cValue){
$this->arc[$value][$cValue] = ($value == $cValue ? 0 : $this->infinity);
}
}
}
//创建图 $direct:0表示无向图,1表示有向图
private function createArc(){
foreach($this->arcData as $key=>$value){
$strArr = str_split($key);
$first = $strArr[0];
$last = $strArr[1];
$this->arc[$first][$last] = $value;
if(!$this->direct){
$this->arc[$last][$first] = $value;
}
}
}
//floyd算法
public function floyd(){
$path = array();//路径数组
$distance = array();//距离数组
foreach($this->arc as $key=>$value){
foreach($value as $k=>$v){
$path[$key][$k] = $k;
$distance[$key][$k] = $v;
}
}
for($j = 0; $j < count($this->vexs); $j ++){
for($i = 0; $i < count($this->vexs); $i ++){
for($k = 0; $k < count($this->vexs); $k ++){
if($distance[$this->vexs[$i]][$this->vexs[$k]] > $distance[$this->vexs[$i]][$this->vexs[$j]] + $distance[$this->vexs[$j]][$this->vexs[$k]]){
$path[$this->vexs[$i]][$this->vexs[$k]] = $path[$this->vexs[$i]][$this->vexs[$j]];
$distance[$this->vexs[$i]][$this->vexs[$k]] = $distance[$this->vexs[$i]][$this->vexs[$j]] + $distance[$this->vexs[$j]][$this->vexs[$k]];
}
}
}
}
return array($path, $distance);
//return $path;
}
public function output($i,$j)
{
if($i == $j)
return;
if($path[$this->vexs[$i]][$this->vexs[$j]] == 0)
echo $j;
else{
output($i,$path[$this->vexs[$i]][$this->vexs[$j]]);
output($path[$this->vexs[$i]][$this->vexs[$j]],$j);
}
}
}
?>
require 'mGraph.php';
$a = array('a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i');
$b = array('ab'=>'10', 'af'=>'11', 'bg'=>'16', 'fg'=>'17', 'bc'=>'18', 'bi'=>'12', 'ci'=>'8', 'cd'=>'22', 'di'=>'21', 'dg'=>'24', 'gh'=>'19', 'dh'=>'16', 'de'=>'20', 'eh'=>'7','fe'=>'26');
//键为边,值权值
$test = new MGraph($a, $b);
echo "
";
print_r($test->floyd());
echo "";
/*$u = a;
$v = g;
if($distance[$this->vexs[$u]][$this->vexs[$v]] == $infinity)
echo "NO Path";
else{
echo $u;
output($u,$v);
}*/
$test->output(a,f);
?>
回复讨论(解决方案)
存在有大量使用未定义变量的警告信息
尤其是 output 方法中的 $path是floyd吧？
没研究过1楼，那你可以帮我写下输出函数吗
$a = array('a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i');$b = array('ab'=>'10', 'af'=>'11', 'bg'=>'16', 'fg'=>'17', 'bc'=>'18', 'bi'=>'12', 'ci'=>'8', 'cd'=>'22', 'di'=>'21', 'dg'=>'24', 'gh'=>'19', 'dh'=>'16', 'de'=>'20', 'eh'=>'7','fe'=>'26');$d = floyd($a, $b);echo $d['a']['g']; //26echo $d['b']['h']; //35function floyd($a, $b) { $a = array_flip($a); $n = count($a); $D = array_fill(0, $n, array_fill(0, $n, 0xffff)); foreach($b as $k=>$v) { $D[$a[$k{0}]][$a[$k{1}]] = $v; $D[$a[$k{1}]][$a[$k{0}]] = $v; } for($k=0; $k<$n; $k++) { for($i=0; $i<$n; $i++) { if($k == $i) $D[$k][$i] = 0; for($j=0; $j<$n; $j++) { if($D[$i][$k]+$D[$k][$j]<$D[$i][$j]) $D[$i][$j]=$D[$i][$k]+$D[$k][$j]; } } } $a = array_flip($a); for($i=0; $i<$n; $i++) $D[$i] = array_combine($a, $D[$i]); $D = array_combine($a, $D); return $D;}您好，版主，这个输出最短路径权值的我可以实现，我想请你帮忙做一下可以输出最短路径，比如a->b->d->f这种，谢谢啦！
调整一下算法
$a = array('a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i');$b = array('ab'=>'10', 'af'=>'11', 'bg'=>'16', 'fg'=>'17', 'bc'=>'18', 'bi'=>'12', 'ci'=>'8', 'cd'=>'22', 'di'=>'21', 'dg'=>'24', 'gh'=>'19', 'dh'=>'16', 'de'=>'20', 'eh'=>'7','fe'=>'26');$d = floyd($a, $b);//查看一下;foreach($a as $i) { foreach($a as $j) { $t = $d[$i][$j]; printf("%s to %s (%d): %s\n", $i, $j, $t['v'], join(' -> ', $t['st'])); }}function floyd($a, $b) { foreach($a as $i) { foreach($a as $j) $d[$i][$j] = array( 'v' => $i == $j ? 0 : 0xffff, 'st' => array($i, $j)); } foreach($b as $k=>$v) { $d[$k{0}][$k{1}]['v'] = $v; $d[$k{1}][$k{0}]['v'] = $v; } foreach($a as $k) { foreach($a as $i) foreach($a as $j) if($d[$i][$j]['v'] > $d[$i][$k]['v'] + $d[$k][$j]['v']) { $d[$i][$j]['v'] = $d[$i][$k]['v'] + $d[$k][$j]['v']; array_splice($d[$i][$j]['st'], -1, 0, $k); } } return $d;}a to a (0): a -> aa to b (10): a -> ba to c (28): a -> b -> ca to d (43): a -> c -> i -> da to e (37): a -> d -> f -> ea to f (11): a -> fa to g (26): a -> b -> ga to h (44): a -> d -> f -> ha to i (22): a -> b -> ib to a (10): b -> ab to b (0): b -> bb to c (18): b -> cb to d (33): b -> c -> i -> db to e (42): b -> d -> f -> h -> eb to f (21): b -> a -> fb to g (16): b -> gb to h (35): b -> d -> f -> g -> hb to i (12): b -> ic to a (28): c -> b -> ac to b (18): c -> bc to c (0): c -> cc to d (22): c -> dc to e (42): c -> d -> ec to f (39): c -> b -> fc to g (34): c -> b -> gc to h (38): c -> d -> hc to i (8): c -> id to a (43): d -> c -> i -> ad to b (33): d -> c -> i -> bd to c (22): d -> cd to d (0): d -> dd to e (20): d -> ed to f (41): d -> c -> e -> g -> fd to g (24): d -> gd to h (16): d -> hd to i (21): d -> ie to a (37): e -> d -> f -> ae to b (42): e -> d -> f -> h -> be to c (42): e -> d -> ce to d (20): e -> de to e (0): e -> ee to f (26): e -> fe to g (26): e -> d -> f -> h -> ge to h (7): e -> he to i (41): e -> d -> if to a (11): f -> af to b (21): f -> a -> bf to c (39): f -> b -> cf to d (41): f -> c -> e -> g -> df to e (26): f -> ef to f (0): f -> ff to g (17): f -> gf to h (33): f -> d -> e -> hf to i (33): f -> b -> ig to a (26): g -> b -> ag to b (16): g -> bg to c (34): g -> b -> cg to d (24): g -> dg to e (26): g -> d -> f -> h -> eg to f (17): g -> fg to g (0): g -> gg to h (19): g -> hg to i (28): g -> b -> ih to a (44): h -> d -> f -> ah to b (35): h -> d -> f -> g -> bh to c (38): h -> d -> ch to d (16): h -> dh to e (7): h -> eh to f (33): h -> d -> e -> fh to g (19): h -> gh to h (0): h -> hh to i (37): h -> d -> ii to a (22): i -> b -> ai to b (12): i -> bi to c (8): i -> ci to d (21): i -> di to e (41): i -> d -> ei to f (33): i -> b -> fi to g (28): i -> b -> gi to h (37): i -> d -> hi to i (0): i -> i谢谢楼主，我今天试一下！
您好，楼主，我刚看了下代码和结果，发现结果不完全对，如a to d (43): a -> c -> i -> d，实际上应该是a->b->i->d。还有，，虽然实际上返回的权值正确，但是路径却是有问题的
array_splice($d[$i][$j]['st'], -1, 0, $k);
改为
$d[$i][$j]['st'] = array_merge($d[$i][$k]['st'], array_slice($d[$k][$j]['st'], 1));
得
a to a (0): a -> aa to b (10): a -> ba to c (28): a -> b -> ca to d (43): a -> b -> i -> da to e (37): a -> f -> ea to f (11): a -> fa to g (26): a -> b -> ga to h (44): a -> f -> e -> ha to i (22): a -> b -> ib to a (10): b -> ab to b (0): b -> bb to c (18): b -> cb to d (33): b -> i -> db to e (42): b -> g -> h -> eb to f (21): b -> a -> fb to g (16): b -> gb to h (35): b -> g -> hb to i (12): b -> ic to a (28): c -> b -> ac to b (18): c -> bc to c (0): c -> cc to d (22): c -> dc to e (42): c -> d -> ec to f (39): c -> b -> a -> fc to g (34): c -> b -> gc to h (38): c -> d -> hc to i (8): c -> id to a (43): d -> i -> b -> ad to b (33): d -> i -> bd to c (22): d -> cd to d (0): d -> dd to e (20): d -> ed to f (41): d -> g -> fd to g (24): d -> gd to h (16): d -> hd to i (21): d -> ie to a (37): e -> f -> ae to b (42): e -> h -> g -> be to c (42): e -> d -> ce to d (20): e -> de to e (0): e -> ee to f (26): e -> fe to g (26): e -> h -> ge to h (7): e -> he to i (41): e -> d -> if to a (11): f -> af to b (21): f -> a -> bf to c (39): f -> a -> b -> cf to d (41): f -> g -> df to e (26): f -> ef to f (0): f -> ff to g (17): f -> gf to h (33): f -> e -> hf to i (33): f -> a -> b -> ig to a (26): g -> b -> ag to b (16): g -> bg to c (34): g -> b -> cg to d (24): g -> dg to e (26): g -> h -> eg to f (17): g -> fg to g (0): g -> gg to h (19): g -> hg to i (28): g -> b -> ih to a (44): h -> e -> f -> ah to b (35): h -> g -> bh to c (38): h -> d -> ch to d (16): h -> dh to e (7): h -> eh to f (33): h -> e -> fh to g (19): h -> gh to h (0): h -> hh to i (37): h -> d -> ii to a (22): i -> b -> ai to b (12): i -> bi to c (8): i -> ci to d (21): i -> di to e (41): i -> d -> ei to f (33): i -> b -> a -> fi to g (28): i -> b -> gi to h (37): i -> d -> hi to i (0): i -> i内容总结
以上是互联网集市为您收集整理的用php实现flody算法输出全部内容，希望文章能够帮你解决用php实现flody算法输出所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。
内容备注
版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。
内容手机端
扫描二维码推送至手机访问。
来源：【匿名】