PHP的SPFA,由于是之前的c代码,风格你懂的........(夹带php队列实现)
博客专区 > 侯禹 的博客 > 博客详情
PHP的SPFA,由于是之前的c代码,风格你懂的........(夹带php队列实现)
侯禹 发表于4年前
PHP的SPFA,由于是之前的c代码,风格你懂的........(夹带php队列实现)
  • 发表于 4年前
  • 阅读 25
  • 收藏 0
  • 点赞 0
  • 评论 0

【腾讯云】如何购买服务器最划算?>>>   

<?php
echo "<meta http-equiv='Content-Type' content='text/html;charset=utf-8'>";
error_reporting( E_ALL&~E_NOTICE );
define("Inf",0x7fffffff);
define("MaxV",10000);
define("MaxE",10000);
class Edge
{
 var $to,$nex,$w;
 function __construct($to,$nex,$w)
 {
  $this->to=$to;
  $this->nex=$nex;
  $this->w=$w;
 } 
}
class A
{
 public $N,$M;
 public $edge = array();
 public $size;
 public $head = array();
 public $dist = array();
 public $cot = array();
 public $vst = array();
 public $path = array();
 
 function InsertEdge($from,$to,$w)
 {
  $this->edge[$this->size] = new Edge($to,$this->head[$from],$w);
  $this->head[$from] = $this->size++; 
 }
 
 function spfa($s)
 {
  $from;
  $to;
  $que = new queue(30);
  
  for($i=0;$i<=$this->N;$i++){
   $this->path[$i]=$i;
   $this->dist[$i]=Inf;
  }
  $this->path[$s]=0;
  $this->dist[$s]=0;
  $que->InQ($s);
  $this->vst[$s]=1;
  while($que->QIsFull()!=0)
  {
   $from=$que->getFrontDate();
   //$que.pop();
   //array_shift($que);
   $que->OutQ();
   $vst[$from]=0;
   $cot[$from]++;
   if($this->cot[$from]>=$this->N)
    return 0;
   for($i=$this->head[$from];$i+1;$i=$this->edge[i]->next)
   //当head=-1的时候,停止,证明其没有
   {
    $to=$this->edge[$i].to;
    if($this->dist[$to]>$this->dist[$from]+$this->edge[$i]->w)
    {
     $this->dist[$to] = $this->dist[$from] + $this->edge[$i]->w;
     if(!$this->vst[$to])
      $this->$que->InQ($to);
      $this->vst[$to]=1;
    }
   }
  }
  for($i=1;$i<=$N;$i++)
  echo "dist".$this->i."  =  ".$this->dist[i]."<br>";
  return 1;
 }
 
 function init()
 {
  $from;
  $to;
  $w;
  $this->size=0;
  //memset(head,-1,sizeof(head));
  for($i=0;$i<count($this->head);$i++)
   $this->head[i] = -1;
 }
 
 function main()
 {
  $this->init();
  $this->M = 3;
  $this->N = 3;
  
  $from = 1;
  $w = 3 ;
  $to = 2;
  $this->InsertEdge($from,$to,$w);
  
  $from = 2;
  $w = 1 ;
  $to = 3;
  $this->InsertEdge($from,$to,$w);
  
  $from = 3;
  $w = 3 ;
  $to = 2;
  $this->InsertEdge($from,$to,$w);
  
  
  
  if(!$this->spfa(1))
  echo "存在负环回路";
  else echo "存在最短路径";
  return 0;
 }
}
 
class queue{  
    protected $front;//队头  
    protected $rear;//队尾  
    protected $queue=array('0'=>'队尾');//存储队列  
    protected $maxsize;//最大数  
      
    public function __construct($size){  
        $this->initQ($size);  
    }  
    //初始化队列  
    private function initQ($size){  
        $this->front=0;  
        $this->rear=0;  
        $this->maxsize=$size;  
    }  
    //判断队空  
    public function QIsEmpty(){  
        return $this->front==$this->rear;  
    }  
    //判断队满  
    public function QIsFull(){  
        return ($this->front-$this->rear)==$this->maxsize;  
    }  
    //获取队首数据  
    public function getFrontDate(){  
        return $this->queue[$this->front]->getData();  
    }  
    //入队  
    public function InQ($data){  
        if($this->QIsFull())echo $data.":满了!(队满不能入队,请等待!)<br>";  
        else {  
            $this->front++;  
            for($i=$this->front;$i>$this->rear;$i--){  
                //echo $data;  
                if($this->queue[$i])unset($this->queue[$i]);  
                $this->queue[$i]=$this->queue[$i-1];  
            }  
            $this->queue[$this->rear+1]=new data($data); 
        }  
    }  
    //出队  
    public function OutQ(){  
        if($this->QIsEmpty())echo "队空不能出队!<br>";  
        else{  
            unset($this->queue[$this->front]);  
            $this->front--;
   }
 }
}
class data {  
    //数据  
    private $data;  
      
    public function __construct($data){  
        $this->data=$data;  
    }  
      
    public function getData(){  
        return $this->data;  
    }  
    public function __destruct(){ 
    }  
}  
?>
<?php
 $a = new A();
 $a->main();
?>


标签: php SPFA 算法 ACM
共有 人打赏支持
粉丝 93
博文 49
码字总数 34362
×
侯禹
如果觉得我的文章对您有用,请随意打赏。您的支持将鼓励我继续创作!
* 金额(元)
¥1 ¥5 ¥10 ¥20 其他金额
打赏人
留言
* 支付类型
微信扫码支付
打赏金额:
已支付成功
打赏金额: