文档章节

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

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


© 著作权归作者所有

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

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

Hosee ⋅ 2016/01/14 ⋅ 0

实习日志(二)

一下是本人最近的一些感受和SB一样的想法和问题,欢迎各位大神多多指教! 原本自己做网站感觉还好,但是在工作了为了企业建站,做为一份工作,就很多大的不同。 DTcms的代码风格和我们常用的...

笨小熊 ⋅ 2014/07/04 ⋅ 2

PHP 手册学习-基础语法

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

SibylY ⋅ 2016/02/22 ⋅ 0

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

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

ZscDst ⋅ 01/31 ⋅ 0

SPFA 算法详解

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

sshpp ⋅ 2017/07/20 ⋅ 0

Linux下常用轻量级队列服务比较

Linux IPC: IPC进程间通信(Inter-Process Communication)就是指多个进程之间相互通信,交换信息的方法。 系统消息队列功能是这些方法中的其中一种。使用此队列不需要额外安装服务,是系统内...

苗雨顺 ⋅ 2014/03/24 ⋅ 1

PHP 自 5.2 到 5.6 中新增的功能详解[转]

本文将会介绍自 PHP5.2 起,直至 PHP5.6 中增加的新特征。 PHP5.2 以前:autoload, PDO 和 MySQLi, 类型约束 PHP5.2:JSON 支持 PHP5.3:弃用的功能,匿名函数,新增魔术方法,命名空间,后期...

W_Lu ⋅ 2014/02/07 ⋅ 2

怎么一步步编写简单的PHP的Framework(十一)

好几天没更新了,今天刚发了money,继续写一下吧。 之前讲了怎么让实现跳转和请求的转发,当然,也只是很简单的说了一下,更深的内容需要你自己去读一下具体框架的实现。 现在跳转和转发有了...

阳光test ⋅ 2012/11/30 ⋅ 0

为什么 PHPer 应当学习 Golang

熟悉我的朋友应当知道,近些年的大部分时间我的工作都会多少和 PHP 相关。随着 PHP 有着越来越深入的了解,以及遇到越来越多的不同业务时,使用 PHP 总会让我有一种莫名的无力感。当然,并不...

龙鸟 ⋅ 2012/11/28 ⋅ 4

RabbitMQ官方中文入门教程(PHP版) 第一部分:Hello World

RabbitMQ是一个消息代理。它的核心原理非常简单:接收和发送消息。你可以把它想像成一个邮局:你把信件放入邮箱,邮递员就会把信件投递到你的收件人处。在这个比喻中,RabbitMQ是一个邮箱、邮...

tree2013 ⋅ 2016/11/11 ⋅ 0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

解决yum安装报错Protected multilib versions

使用yum安装报错Protected multilib versions原因是因为多个库不能共存,不过更新的话也并不行,但是可以在安装命令后面加上如下一段命令: --setopt=protected_multilib=false 案例: 比如需...

北岩 ⋅ 29分钟前 ⋅ 0

为什么要学习Typescript???

简单来说 目前的typescript就是未来的javascript 为什么?? 这要从ECMA-262标准的第4版说起 对了 我们说的ES5 其实是ECMAScript3.1这个替代性建议被扶正了而已... 那么 第4版标准是什么? 看看...

hang1989 ⋅ 33分钟前 ⋅ 0

linux安装ipfs

一、下载ipfs # cd /usr/local/ipfs/ # wget https://dist.ipfs.io/go-ipfs/v0.4.15/go-ipfs_v0.4.15_linux-amd64.tar.gz # tar -zxvf go-ipfs_v0.4.15_linux-amd64.tar.gz 二、安装ipfs # ......

八戒八戒八戒 ⋅ 39分钟前 ⋅ 0

jvm程序执行慢诊断手册

生产环境最多的几种事故之一就是程序执行慢,如果是web服务的话,表现就是响应时间长。本文分享,从业多年形成的排查守则。 诊断步骤 系统资源查看 首先是系统资源查看,而且必须是在第一步。...

xpbob ⋅ 40分钟前 ⋅ 0

YII2 advanced 高级版本项目搭建-添加API应用以及多应用

一、YII安裝 安裝yii可以用composer安裝,也可以在yii中文社区下载归档文件安装 composer安装就不介绍了,因为要安装composer,比较麻烦,当然安装了composer是最好的,以后安装yii的插件要用...

botkenni ⋅ 40分钟前 ⋅ 0

在jdk1.8的环境下模拟永久代内存溢出

相信不少小伙伴在看深入理解Java虚拟机的时候,作者给我们举例一个demo来发生PermGen space 1、通过List不断添加String.intern(); 2、通过设置对应的-XX:PermSize与-XX:MaxPermSize(更快看到...

虾几把写 ⋅ 今天 ⋅ 0

开发OpenDaylight组件的完整流程

在前面介绍学习了OpenDaylight的几个重要模块后,这里再来介绍下完整开发一个模块的过程。 OSGI的bundles提供被其他OSGI组件调用的服务。这个教程中展示的是Data Packet Service去解析数据包...

wangxuwei ⋅ 今天 ⋅ 0

Java序列化和反序列化

1、什么是序列化和反序列化 序列化:把对象转换为字节序列的过程。 反序列化:把字节序列恢复成对象的过程。 2、被序列化的类需要实现serializable接口,只是为了标注该对象是可以被序列化的...

IT-Mamba ⋅ 今天 ⋅ 0

流式构建原理

流式构建需要达到分钟级的数据更新频率,Kylin采用类似于Spark Streaming的做法,每隔数分钟进行一次微构建。这边的构建需要考虑到一个延迟因素,分布式网络存在延迟等因素,该时间段的数据有...

无精疯 ⋅ 今天 ⋅ 0

在maven项目工程编写solr代码,需要的依赖

solrJ <dependency> <groupId>org.apache.solr</groupId> <artifactId>solr-solrj</artifactId> <version>6.6.2</version> </dependency> <dependency> <groupId>org.apache.httpcomponents<......

爱运动的小乌龟 ⋅ 今天 ⋅ 0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

返回顶部
顶部