调整一下算法$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 -> a a to b (10): a -> b a to c (28): a -> b -> c a to d (43): a -> c -> i -> d a to e (37): a -> d -> f -> e a to f (11): a -> f a to g (26): a -> b -> g a to h (44): a -> d -> f -> h a to i (22): a -> b -> i b to a (10): b -> a b to b (0): b -> b b to c (18): b -> c b to d (33): b -> c -> i -> d b to e (42): b -> d -> f -> h -> e b to f (21): b -> a -> f b to g (16): b -> g b to h (35): b -> d -> f -> g -> h b to i (12): b -> i c to a (28): c -> b -> a c to b (18): c -> b c to c (0): c -> c c to d (22): c -> d c to e (42): c -> d -> e c to f (39): c -> b -> f c to g (34): c -> b -> g c to h (38): c -> d -> h c to i (8): c -> i d to a (43): d -> c -> i -> a d to b (33): d -> c -> i -> b d to c (22): d -> c d to d (0): d -> d d to e (20): d -> e d to f (41): d -> c -> e -> g -> f d to g (24): d -> g d to h (16): d -> h d to i (21): d -> i e to a (37): e -> d -> f -> a e to b (42): e -> d -> f -> h -> b e to c (42): e -> d -> c e to d (20): e -> d e to e (0): e -> e e to f (26): e -> f e to g (26): e -> d -> f -> h -> g e to h (7): e -> h e to i (41): e -> d -> i f to a (11): f -> a f to b (21): f -> a -> b f to c (39): f -> b -> c f to d (41): f -> c -> e -> g -> d f to e (26): f -> e f to f (0): f -> f f to g (17): f -> g f to h (33): f -> d -> e -> h f to i (33): f -> b -> i g to a (26): g -> b -> a g to b (16): g -> b g to c (34): g -> b -> c g to d (24): g -> d g to e (26): g -> d -> f -> h -> e g to f (17): g -> f g to g (0): g -> g g to h (19): g -> h g to i (28): g -> b -> i h to a (44): h -> d -> f -> a h to b (35): h -> d -> f -> g -> b h to c (38): h -> d -> c h to d (16): h -> d h to e (7): h -> e h to f (33): h -> d -> e -> f h to g (19): h -> g h to h (0): h -> h h to i (37): h -> d -> i i to a (22): i -> b -> a i to b (12): i -> b i to c (8): i -> c i to d (21): i -> d i to e (41): i -> d -> e i to f (33): i -> b -> f i to g (28): i -> b -> g i to h (37): i -> d -> h i 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 -> a a to b (10): a -> b a to c (28): a -> b -> c a to d (43): a -> b -> i -> d a to e (37): a -> f -> e a to f (11): a -> f a to g (26): a -> b -> g a to h (44): a -> f -> e -> h a to i (22): a -> b -> i b to a (10): b -> a b to b (0): b -> b b to c (18): b -> c b to d (33): b -> i -> d b to e (42): b -> g -> h -> e b to f (21): b -> a -> f b to g (16): b -> g b to h (35): b -> g -> h b to i (12): b -> i c to a (28): c -> b -> a c to b (18): c -> b c to c (0): c -> c c to d (22): c -> d c to e (42): c -> d -> e c to f (39): c -> b -> a -> f c to g (34): c -> b -> g c to h (38): c -> d -> h c to i (8): c -> i d to a (43): d -> i -> b -> a d to b (33): d -> i -> b d to c (22): d -> c d to d (0): d -> d d to e (20): d -> e d to f (41): d -> g -> f d to g (24): d -> g d to h (16): d -> h d to i (21): d -> i e to a (37): e -> f -> a e to b (42): e -> h -> g -> b e to c (42): e -> d -> c e to d (20): e -> d e to e (0): e -> e e to f (26): e -> f e to g (26): e -> h -> g e to h (7): e -> h e to i (41): e -> d -> i f to a (11): f -> a f to b (21): f -> a -> b f to c (39): f -> a -> b -> c f to d (41): f -> g -> d f to e (26): f -> e f to f (0): f -> f f to g (17): f -> g f to h (33): f -> e -> h f to i (33): f -> a -> b -> i g to a (26): g -> b -> a g to b (16): g -> b g to c (34): g -> b -> c g to d (24): g -> d g to e (26): g -> h -> e g to f (17): g -> f g to g (0): g -> g g to h (19): g -> h g to i (28): g -> b -> i h to a (44): h -> e -> f -> a h to b (35): h -> g -> b h to c (38): h -> d -> c h to d (16): h -> d h to e (7): h -> e h to f (33): h -> e -> f h to g (19): h -> g h to h (0): h -> h h to i (37): h -> d -> i i to a (22): i -> b -> a i to b (12): i -> b i to c (8): i -> c i to d (21): i -> d i to e (41): i -> d -> e i to f (33): i -> b -> a -> f i to g (28): i -> b -> g i to h (37): i -> d -> h i to i (0): i -> i
版主,原谅我的反复问题,因为后台确实没有写过,新的问题哈: 如果从客户端(ios)发送过来的两个数据比如我用$_POST['start'] 和 $_POST['end']获得,分别为起点和终点,那么怎么做才可以返回具体的那条路径,如a b d f
$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']; //26
echo $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;
}
$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 -> a
a to b (10): a -> b
a to c (28): a -> b -> c
a to d (43): a -> c -> i -> d
a to e (37): a -> d -> f -> e
a to f (11): a -> f
a to g (26): a -> b -> g
a to h (44): a -> d -> f -> h
a to i (22): a -> b -> i
b to a (10): b -> a
b to b (0): b -> b
b to c (18): b -> c
b to d (33): b -> c -> i -> d
b to e (42): b -> d -> f -> h -> e
b to f (21): b -> a -> f
b to g (16): b -> g
b to h (35): b -> d -> f -> g -> h
b to i (12): b -> i
c to a (28): c -> b -> a
c to b (18): c -> b
c to c (0): c -> c
c to d (22): c -> d
c to e (42): c -> d -> e
c to f (39): c -> b -> f
c to g (34): c -> b -> g
c to h (38): c -> d -> h
c to i (8): c -> i
d to a (43): d -> c -> i -> a
d to b (33): d -> c -> i -> b
d to c (22): d -> c
d to d (0): d -> d
d to e (20): d -> e
d to f (41): d -> c -> e -> g -> f
d to g (24): d -> g
d to h (16): d -> h
d to i (21): d -> i
e to a (37): e -> d -> f -> a
e to b (42): e -> d -> f -> h -> b
e to c (42): e -> d -> c
e to d (20): e -> d
e to e (0): e -> e
e to f (26): e -> f
e to g (26): e -> d -> f -> h -> g
e to h (7): e -> h
e to i (41): e -> d -> i
f to a (11): f -> a
f to b (21): f -> a -> b
f to c (39): f -> b -> c
f to d (41): f -> c -> e -> g -> d
f to e (26): f -> e
f to f (0): f -> f
f to g (17): f -> g
f to h (33): f -> d -> e -> h
f to i (33): f -> b -> i
g to a (26): g -> b -> a
g to b (16): g -> b
g to c (34): g -> b -> c
g to d (24): g -> d
g to e (26): g -> d -> f -> h -> e
g to f (17): g -> f
g to g (0): g -> g
g to h (19): g -> h
g to i (28): g -> b -> i
h to a (44): h -> d -> f -> a
h to b (35): h -> d -> f -> g -> b
h to c (38): h -> d -> c
h to d (16): h -> d
h to e (7): h -> e
h to f (33): h -> d -> e -> f
h to g (19): h -> g
h to h (0): h -> h
h to i (37): h -> d -> i
i to a (22): i -> b -> a
i to b (12): i -> b
i to c (8): i -> c
i to d (21): i -> d
i to e (41): i -> d -> e
i to f (33): i -> b -> f
i to g (28): i -> b -> g
i to h (37): i -> d -> h
i to i (0): i -> i
改为
$d[$i][$j]['st'] = array_merge($d[$i][$k]['st'], array_slice($d[$k][$j]['st'], 1));
得
a to a (0): a -> a
a to b (10): a -> b
a to c (28): a -> b -> c
a to d (43): a -> b -> i -> d
a to e (37): a -> f -> e
a to f (11): a -> f
a to g (26): a -> b -> g
a to h (44): a -> f -> e -> h
a to i (22): a -> b -> i
b to a (10): b -> a
b to b (0): b -> b
b to c (18): b -> c
b to d (33): b -> i -> d
b to e (42): b -> g -> h -> e
b to f (21): b -> a -> f
b to g (16): b -> g
b to h (35): b -> g -> h
b to i (12): b -> i
c to a (28): c -> b -> a
c to b (18): c -> b
c to c (0): c -> c
c to d (22): c -> d
c to e (42): c -> d -> e
c to f (39): c -> b -> a -> f
c to g (34): c -> b -> g
c to h (38): c -> d -> h
c to i (8): c -> i
d to a (43): d -> i -> b -> a
d to b (33): d -> i -> b
d to c (22): d -> c
d to d (0): d -> d
d to e (20): d -> e
d to f (41): d -> g -> f
d to g (24): d -> g
d to h (16): d -> h
d to i (21): d -> i
e to a (37): e -> f -> a
e to b (42): e -> h -> g -> b
e to c (42): e -> d -> c
e to d (20): e -> d
e to e (0): e -> e
e to f (26): e -> f
e to g (26): e -> h -> g
e to h (7): e -> h
e to i (41): e -> d -> i
f to a (11): f -> a
f to b (21): f -> a -> b
f to c (39): f -> a -> b -> c
f to d (41): f -> g -> d
f to e (26): f -> e
f to f (0): f -> f
f to g (17): f -> g
f to h (33): f -> e -> h
f to i (33): f -> a -> b -> i
g to a (26): g -> b -> a
g to b (16): g -> b
g to c (34): g -> b -> c
g to d (24): g -> d
g to e (26): g -> h -> e
g to f (17): g -> f
g to g (0): g -> g
g to h (19): g -> h
g to i (28): g -> b -> i
h to a (44): h -> e -> f -> a
h to b (35): h -> g -> b
h to c (38): h -> d -> c
h to d (16): h -> d
h to e (7): h -> e
h to f (33): h -> e -> f
h to g (19): h -> g
h to h (0): h -> h
h to i (37): h -> d -> i
i to a (22): i -> b -> a
i to b (12): i -> b
i to c (8): i -> c
i to d (21): i -> d
i to e (41): i -> d -> e
i to f (33): i -> b -> a -> f
i to g (28): i -> b -> g
i to h (37): i -> d -> h
i to i (0): i -> i
如果从客户端(ios)发送过来的两个数据比如我用$_POST['start'] 和 $_POST['end']获得,分别为起点和终点,那么怎么做才可以返回具体的那条路径,如a b d f