文档章节

PHP的SPFA,由于是之前的c代码,风格你懂的........(夹带php队列实现)

侯禹
 侯禹
发布于 2013/07/28 22:38
字数 547
阅读 28
收藏 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();
?>


© 著作权归作者所有

共有 人打赏支持
侯禹
粉丝 96
博文 49
码字总数 34362
作品 0
海淀
程序员
私信 提问
最短路径算法

单源最短路径问题 问题描述:给你一个顶点做源点,你想要知道,如何从源点到达其他所有点的最短路径。 OK,这个问题看起来没什么用。我们一般想知道的是A点到B点的最短路径,这个单源最短路径...

Hosee
2016/01/14
2.2K
0
POJ ~ 3159 ~ Candies (Dijkstra + 优先队列 + 链式前向星 or 栈式SPFA)(差分约束)

推荐一片入门博客:夜深人静写算法(四) - 差分约束 个人感觉很有用的地方,暂存一下,备查: 4、最大值 => 最小值 然后,我们将问题进行一个简单的转化,将原先的"<="变成">=",转化后的不...

ZscDst
01/31
0
0
SPFA 算法详解

适用范围:给定的图存在负权边,这时类似Dijkstra等算法便没有了用武之地,而Bellman-Ford算法的复杂度又过高,SPFA算法便 派上用场了。 我们约定有向加权图G不存在负权回路,即最短路径一定...

sshpp
2017/07/20
0
0
【图论】Python [ numpy, pandas] 实现 基础能力以及基础算法 [ dfs bfs spfa ] 经过较为严格测试

版权 copyright :散哥[tjut],程坦[tju] 转载请联系;或者有想法的找我; 输入 有数据文件输入处理部分,有比较清楚的结果输出 实现的功能 add_node 添加点, remove_node 删除点, add_ed...

散人lins
12/12
0
0
PHP 手册学习-基础语法

基本语法 PHP 标记、分割符、注释 当解析一个文件时,PHP 会寻找起始和结束标记,也就是 <?php 和 ?>,在 HTML 中分离出 PHP代码; 指令分割符:同 C 或 Perl 一样,PHP 需要在每个语句后用分...

SibylY
2016/02/22
22
0

没有更多内容

加载失败,请刷新页面

加载更多

OSChina 周三乱弹 —— 有一天考拉麻麻拉肚子了

Osc乱弹歌单(2018)请戳(这里) 【今日歌曲】 @瘟神灬念 :分享周汇洋的单曲《Man Srae(曼斯拉之舞)》:美滋滋。。。。 手机党少年们想听歌,请使劲儿戳(这里) 我听了一下 赶紧关了, ...

小小编辑
38分钟前
12
3
oh-my-zsh 自定义

GitHub 地址 基于 oh-my-zsh 的自定义配置,增加了一些个人常用插件与皮肤。 采用的是 git submodule 来维护,包括 oh-my-zsh,之所以这么搞,主要是手头有多台 linux 需要维护, 每台机器、...

郁也风
今天
6
0
Docker安装踩坑:E_FAIL 0x80004005的解决

参考 菜鸟教程--Windows Docker 安装 http://www.runoob.com/docker/windows-docker-install.html 官方文档-Install Docker Toolbox on Windows https://docs.docker.com/toolbox/toolbox_in......

karma123
今天
6
0
js垃圾回收机制和引起内存泄漏的操作

JS的垃圾回收机制了解吗? Js具有自动垃圾回收机制。垃圾收集器会按照固定的时间间隔周期性的执行。 JS中最常见的垃圾回收方式是标记清除。 工作原理:是当变量进入环境时,将这个变量标记为“...

Jack088
昨天
18
0
大数据教程(10.1)倒排索引建立

前面博主介绍了sql中join功能的大数据实现,本节将继续为小伙伴们分享倒排索引的建立。 一、需求 在很多项目中,我们需要对我们的文档建立索引(如:论坛帖子);我们需要记录某个词在各个文...

em_aaron
昨天
27
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部