解决方案 »

  1.   

    存在有大量使用未定义变量的警告信息尤其是 output 方法中的 $path
      

  2.   

    $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']; //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;
    }
      

  3.   

    您好,版主,这个输出最短路径权值的我可以实现,我想请你帮忙做一下可以输出最短路径,比如a->b->d->f这种,谢谢啦!
      

  4.   

    调整一下算法$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
      

  5.   

    您好,楼主,我刚看了下代码和结果,发现结果不完全对,如a to d (43): a -> c -> i -> d,实际上应该是a->b->i->d。还有,,虽然实际上返回的权值正确,但是路径却是有问题的
      

  6.   

    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
      

  7.   

    版主,原谅我的反复问题,因为后台确实没有写过,新的问题哈:
    如果从客户端(ios)发送过来的两个数据比如我用$_POST['start'] 和 $_POST['end']获得,分别为起点和终点,那么怎么做才可以返回具体的那条路径,如a b d f