求获取最短路径方案

Question

我的笨方法。不晓得是不是。<?php
//好像不能解决重复查询问题
//建立从A到Z的数组
//象征着26个人的集合
$array=range("A","Z");//给他们赋于随机的关系 ,得到$res，包含各个关系对
//试验用
srand ((float)microtime()*1000000);
$res=array();
for($i=0;$i<50;$i++){
    shuffle($array);
    $res[]=array($array[0],$array[1]);
}//设计类
class getLink {
  var $marr=array("A");//已遍历成员
  var $seek=array();//从起点A开始的,所有可用路径
  var $tmp=array("['A']"=>"A");//该级父成员的临时数组
  var $times=0;//查找次数
  var $sort=array(); //从A到目的地的所有路径  //开始查找所有路径
  function getRes($des){
       global $res;
       while($this->times<=26){//26次，防止意外事件
           $tmp=array();
           $this->times++;
           foreach($res as $k=>$v){
               foreach($this->tmp as $key=>$val){
                  if(in_array($val,$v)){
                      $an=($v[0]==$val)?$v[1]:$v[0];
                      if(!in_array($an,$this->marr)){
                           $nkey=$key."['$an']";
                           if(preg_match("/$des/",$nkey)){
                              $this->sort[]=$nkey;
   }
                           $tmp[$nkey]=$an;
                           $this->marr[]=$an;
                           eval("\$this->seek$nkey=array();");
      }
          }
      }
           }
           $this->tmp=$tmp;
       }
  }  //输出所有A到目的地的路径
  function p(){
     print_r($this->sort);
  }  //输出所有从A出发的路径
  function p1(){
     print_r($this->seek);
  }  //输出所有成员的关系
  function p2(){
     global $res;
     print_r($res);
  }
}//创建新的对象
$n=new getLink;
//查找
$n->getRes("Z");
//输出所有A到目的地的路径
$n->p();
//输出所有从A出发的路径
$n->p1();
//输出所有成员的关系
$n->p2();?>

Answer 1

错了
<?php
//好像不能解决重复查询问题
//建立从A到Z的数组
//象征着26个人的集合
$array=range("A","Z");//给他们赋于随机的关系 ,得到$res，包含各个关系对
//试验用
srand ((float)microtime()*1000000);
$res=array();
for($i=0;$i<50;$i++){
    shuffle($array);
    $res[]=array($array[0],$array[1]);
}
//设计类
class getLink {
  var $seek=array();//从起点A开始的,所有可用路径
  var $tmp=array("['A']"=>"A");//该级父成员的临时数组
  var $times=0;//查找次数
  var $sort=array(); //从A到目的地的所有路径  //开始查找所有路径
  function getRes($des){
       global $res;
       while($this->times<=26){//26次，防止意外事件
           $tmp=array();
           $this->times++;
           foreach($res as $k=>$v){
               foreach($this->tmp as $key=>$val){
                  if(in_array($val,$v)){
                      $an=($v[0]==$val)?$v[1]:$v[0];
                      if(!preg_match("/$an/",$key)){
                           $nkey=$key."['$an']";
                           if(preg_match("/\['".$des."']$/",$nkey)){
                              $this->sort[]=$nkey;
   }
                           $tmp[$nkey]=$an;
                           eval("\$this->seek$nkey=array();");
      }
      else{
                           break;
      }
          }
      }
           }
           $this->tmp=$tmp;
       }
  }
  //输出所有A到目的地的路径
  function p(){
     print_r($this->sort);
  }  //输出所有从A出发的路径
  function p1(){
     print_r($this->seek);
  }  //输出所有成员的关系
  function p2(){
     global $res;
     print_r($res);
  }
}//创建新的对象
$n=new getLink;
//查找
$n->getRes("Z");
//输出所有A到目的地的路径
$n->p();
//输出所有从A出发的路径
$n->p1();
//输出所有成员的关系
$n->p2();?>

Answer 2

<?php
/** 节点类
 * 构造函数要求传入一个数组
 * 用于传递节点的信息
 * 第一个元素表示节点名，其他元素表示相邻的节点名
 **/
class NODE {
  var $name = ''; // 节点名
  var $data = array(); // 相邻的节点名
  function node($array) {
    $this->name = $array[0];
    array_shift($array);
    $this->data = $array;
  }
}/** 连通图类 **/
class TU {
  var $stack = array();
  var $dict = array();
  var $out = array();
  function TU($array) {
    foreach($array as $value)
      $this->stack[] = new NODE($value);
  }
  function init() {
    $this->dict = array();
    $this->out = array();
  }
  /**
   * 方法 locate
   * 传入节点名，返回节点对象
   **/
  function locate($node_name) {
    foreach($this->stack as $key=>$value) {
      if($value->name == $node_name) {
        return $value;
      }
    }
    return false;
  }
  /** 
   * 方法 find
   * 传入起止节点名，输出可能的路线
   **/
  function find($start, $end) {
    array_push($this->out, $start);
    array_push($this->dict, $start);
    $node = $this->locate($start);
    if($node->name == $end) {
      echo join(" - ",$this->out)."<br>";
      array_pop($this->out);
      array_pop($this->dict);
      return;
    }
    if(empty($node->data)) {
      echo join(" - ",$this->out)." | stop<br>";
      array_pop($this->out);
      array_pop($this->dict);
      return;
    }
    foreach($node->data as $v)
      if(! in_array($v, $this->dict))
        $this->find($v, $end); // 递归调用find方法
    array_pop($this->out);
    array_pop($this->dict);
  }
}$p = new TU(array(
  array("A","B","E"),
  array("B","A","C"),
  array("E","A","K"),
  array("C","B","D","J"),
  array("J","C","H","Z","K"),
  array("K","E","J"),
  array("D","C","F"),
  array("F","D","L"),
  array("H","C","E"),
  array("Z","J","L"),
  array("L","F","Z"))
);$p->find("A","D");
?>

Answer 3

多谢楼上的几位：）
还存在一个问题，也就是zairwolf(君子兰) 所提到的。
现实中这是个交友网站的寻找朋友所引出的问题。
里面的用户朋友关系信息是存储在数据库，而且用户量可能会很大。那么像下面这样的数组改如何建立呢？
$p = new TU(array(
  array("A","B","E"),
  array("B","A","C"),
  array("E","A","K"),
  array("C","B","D","J"),
  array("J","C","H","Z","K"),
  array("K","E","J"),
  array("D","C","F"),
  array("F","D","L"),
  array("H","C","E"),
  array("Z","J","L"),
  array("L","F","Z"))
);

Answer 4

phpx的帅得像人渣在phpe说出了问题的关键：“其实他对问题是如何在数据库中存储这些关系. 在读取时能高效的生成一个"图"的数据结构..”
可惜小弟到现在还没有解决。

Answer 5

$p = new TU(array(
  array("A","B","E"),
  array("B","A","C"),
  .....
);这样的数组在数据库中是很容易存放的
姓名     朋友
A        B,E
B        A,C
.......