文档章节

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

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


© 著作权归作者所有

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

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

Hosee
2016/01/14
2.2K
0
SPFA 算法详解

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

sshpp
2017/07/20
0
0
POJ ~ 3159 ~ Candies (Dijkstra + 优先队列 + 链式前向星 or 栈式SPFA)(差分约束)

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

ZscDst
01/31
0
0
1.1.1最短路(Floyd、Dijstra、BellmanFord)

转载自hr_whisper大佬的博客 一、Dijkstra 比较详细的迪杰斯特拉算法讲解传送门 Dijkstra单源最短路算法,即计算从起点出发到每个点的最短路。所以Dijkstra常常作为其他算法的预处理。 使用邻...

fire_to_cheat_
03/04
0
0
PHP 手册学习-基础语法

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

SibylY
2016/02/22
22
0

没有更多内容

加载失败,请刷新页面

加载更多

Univalsal_ImageLoader源码结构与创建者模式 初步小结

最近在回归看Univalsal_ImageLoader源码,本想自己也实现试试写一个,看源码是为了学习看能否使用,助于自己可以写出有自己逻辑结构的代码。 首先我们初始化ImageLoader的配置初始化的时候,...

DannyCoder
41分钟前
0
0
计算卷积神经网络浮点数运算量

前言 本文主要是介绍了,给定一个卷积神经网络的配置之后,如何大概估算它的浮点数运算量。 相关代码:CalFlops,基于MXNet框架的 Scala 接口实现的一个计算MXNet网络模型运算量的demo。 正文...

Ldpe2G
今天
3
0
Sql语言与MySql数据库

1. 数据库简介 1. 数据库,就是存储数据的仓库,只能通过sql语言来访问,数据库也是一个文件系统。通常,MySQL、Oracle等数据库,也被称为关系型数据库,其保存的不仅仅只是数据,还包括数据...

江左煤郎
今天
2
0
IDEA 取消自动import .*

打开设置 > Editor > Code Style > Java > Scheme Default > Imports ① 将 Class count to use import with "*" 改为 99 (导入同一个包的类超过这个数值自动变为 * ) ② 将 Names count ......

乔老哥
今天
3
0
PostGIS学习笔记(开篇)

PostGIS事实上算是笔者开始写博客的第一篇内容。而事实上那篇博文的内容并不丰富,笔者对PostGIS的了解仍然不多,然而17年在OSGeo课程学习时对PostGIS又有了进一步了解,并逐步发现它的强大。...

胖胖雕
今天
4
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部