PHP を使用して Flody アルゴリズム出力を実装する

以下は私が実装した Flody アルゴリズムですが、output() 関数を書くときに結果を出力できません。メモするのを手伝ってください。
/**
* PHP はグラフ隣接行列を実装します
*/

class MGraph{ //頂点配列
private $arc; //エッジ隣接行列、つまり 2 次元配列 private $arcData ; // エッジの配列情報
private $direct; // グラフの種類 (無向または有向)
private $infinity = 65535;// グラフを作成するときに使用される無限大を表します。ウェイトでは、ウェイトのない
= $ arc; direct = $ direct; initalizearc（）{
foreach（$ this-＆gt; vexs as $ value）{
foreach（$ this-＆gt; vexs this->arc[$first][$last] = $value;
if (! $ this-& gt; 日記) {
$ this-& gt; Arc [$ last] [$ first] = $value; $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＆lt; count（$ this-＆gt; vexs）; $ j ++）{
for（$ i = 0; $ i＆lt; 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]]; : $j]] + $ distance[$this->vexs[$j]][$this->vexs[$k]];
.配列($path, $ distance)を返します。
// $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);
}
}



}

?>

'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 "

";  <br> print_r($test->floyd());  <br> echo "<pre class="brush:php;toolbar:false">";  <br> /*$u = a;  <br> $v = g;  <br> if($ distance[$this->vexs[$u]][$this->vexs[$v]] == $infinity) <br> echo "NO Path";  <br> else{ <br> echo $u;  <br> 出力($u,$v);  <br> }*/ <br>$test->output(a,f); <br> <br> ?> </p>
<p> </p> フロイドですか？   まだ勉強していません <br> <h2 id="階-出力関数を書くのを手伝ってくれませんか"> 1 階、出力関数を書くのを手伝ってくれませんか </h2> <p class="sougouAnswer"> <div class="code" style="position:relative; padding:0px; margin:0px;"><pre class='brush:php;toolbar:false;'>$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 から d (43) のように完全に正しくないことがわかりました。実際には 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 ));

わかりました