文档章节

关于迪杰斯特拉算法(最短路)的PHP实现

侯禹
 侯禹
发布于 2013/07/10 23:07
字数 403
阅读 262
收藏 8
点赞 0
评论 0
 
<?php
class dijistra
{
 public $inf=0x7fffffff;//最开始把不同的边赋值无限大
 public $MaxV=10000;//最大点数
 public $N,$M;
 public $froms;
 public $tos;
 public $ws;
 public $dist=array();
 public $path=array();
 public $p=array();
 public $map=array();
 
 function dijkstra($s)
 {
  for($i=0;$i<=$this->N;$i++)//对于每个点,设置为没访问过,和设置距离
  {
   $this->p[$i]=false;
   $this->dist[$i]=$this->map[$s][$i];
   $this->path[$i]=$s;
  }
  /*设置出入点的参数*/
  $this->dist[$s]=0;
  $this->path[$s]=$s;
  $this->p[$s]=true;
  
  for($i=1;$i<=$this->N;$i++)//开始扫点
  {
   $min=$this->inf;
   $k=0;
   for($j=1;$j<=$this->N;$j++)
   {
    if(!$this->p[$j]&&$this->dist[$j]<$min)
    {
     $min=$this->dist[$j];
     $k=$j;
    }
   }
   
   if($k == 0)
   {
    print_r("bu tong <br>");
    return;
   }
   
   $this->p[$k]=true;
   
   for($j=1;$j<=$this->N;$j++)
   {
    if(!$this->p[$j]&&$this->map[$k][$j]!=$this->inf
    &&$this->dist[$j]>$this->dist[$k]+$this->map[$k][$j])
    {
     $this->dist[$j]=$this->dist[$k]+$this->map[$k][$j];
     $this->path[$j]=$k;
    }
   }
  }
 }
 
 function init()
 {
  for($i=0;$i<=$this->N;$i++)//初始化将每两个点之间的边权先赋为无穷大
  {
   for($j=0;$j<=$this->N;$j++)
   {
    if($i==$j) $this->map[$i][$j]=0;
    else $this->map[$i][$j]=$this->inf;
   }   
  }
  for($i=0;$i<$this->M;$i++)//对于给出的两点的边权,更换成边权
  {
   $frompre=$this->froms[$i];
   $topre=$this->tos[$i];
   $valuepre=$this->ws[$i];
   
   $this->map[$frompre][$topre]
   =$this->map[$topre][$frompre]
   =$valuepre;
  }
 }
 
 function main($N,$M,$froms,$tos,$ws)
 {
  $this->N=$N;
  $this->M=$M;
  $this->froms=$froms;
  $this->tos=$tos;
  $this->ws=$ws;
  $this->init();//初始化
  $this->dijkstra(1);
  for($i=1;$i<=$this->N;$i++)
  {
   echo "dist[".$i."]   =   ".$this->dist[$i]."<br>";
  }
 }
} 
?>
<?php
$N=4;//点的个数
$M=4;//边的个数
$froms=array('1','1','2','1');//边开始点
$tos=array('2','3','3','4');//边到达点
$ws=array('3','4','0','2');//边权
$d = new dijistra();
$d->main($N,$M,$froms,$tos,$ws);
?>


© 著作权归作者所有

共有 人打赏支持
侯禹
粉丝 94
博文 49
码字总数 34362
作品 0
海淀
程序员
1.1.1最短路(Floyd、Dijstra、BellmanFord)

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

fire_to_cheat_ ⋅ 03/04 ⋅ 0

游戏中的人工智能之流场寻路

流场简介 流场,一般为网格图,网格中的每一个节点包含一个向量,该向量是物体在该位置时期望的速度。 流场寻路 利用流场的速度信息指导大量物体同时进行寻路。换句话说,如何生成可以寻路的...

RonTang ⋅ 2016/04/20 ⋅ 0

迪杰斯特拉(Dijkstra)算法描述与路径计算

1.迪杰斯特拉算法描述 迪杰斯特拉算法是基于LLDP(一种由IEEE802.1AB[11]定义的链路层发现协议)获取信息,是一个从顶点到其余各顶点的最短路径算法,解决的是有向图中最短路径问题。迪杰斯特...

墨痕hz ⋅ 2017/11/28 ⋅ 0

迪杰斯特拉改进

在迪杰斯特拉基础上,增加两个限制,1.限制经过的节点个数。2.必须经过某些点。两个问题分开来都可以解决。第一个是在迪杰斯特拉算法上增加一个数组存储经过的边。第二个用贪心,求每一段的最...

watertiger ⋅ 2017/05/04 ⋅ 0

迪杰斯特拉算法

定义  Dijkstra(迪杰斯特拉)算法是典型的单源最短路径算法,用于计算一个节点到其他所有节点的最短路径。主要特点是以起始点为中心向外层层扩展,直到扩展到终点为止。Dijkstra算法是很有代...

疯狂的艺术家 ⋅ 2012/05/30 ⋅ 0

像名字一样容易忘记的Dijkstra

Dijkstra算法是经典的求解一个顶点到其他顶点的最短距离的算法。每次学习的时候总是觉得思路简单明了,但每当要用到时,就忘记了实现的细节。归根结底还是应用的少。相信做地图导航的应该对其...

dugangabc ⋅ 2016/02/06 ⋅ 0

java实现Dijkstra算法求最短路径

Dijkstra(迪杰斯特拉)算法是典型的最短路径路由算法,用于计算一个节点到其他所有节点的最短路径。主要特点是以起始点为中心向外层层扩展,直到扩展到终点为止。 Dijkstra一般的表述通常有两...

zaizai_loong ⋅ 2013/09/08 ⋅ 2

优秀博客推荐:各种数据结构与算法知识入门经典(不断更新)

基本算法 贪心算法:贪心算法 作者:独酌逸醉 贪心算法精讲 作者:3522021224 递归和分治:递归与分治策略 作者:zhoudaxia 图论 图的遍历(DFS和BFS): 图的遍历 作者:jefferent 最小生成...

索隆 ⋅ 2011/12/03 ⋅ 0

数学:Dijkstra算法

一.最短路径的最优子结构性质 该性质描述为:如果P(i,j)={Vi....Vk..Vs...Vj}是从顶点i到j的最短路径,k和s是这条路径上的一个中间顶点,那么P(k,s)必定是从k到s的最短路径。下面证明该性质的...

pricker ⋅ 2015/09/12 ⋅ 0

Bellman-Ford和松弛技术

适用条件 有向图 但是没有负环 比之迪杰斯特拉 在于他可以计算负的权值边 负环是什么 环 负环就是至少有一条边是负数 松弛技术 这里是发现了2+2=4<5,所以B点更新为4 所以不能是负环,因为这...

qq_36523667 ⋅ 01/18 ⋅ 0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

大数据工程师需要精通算法吗,要达到一个什么程度呢?

机器学习是人工智能的一个重要分支,而机器学习下最重要的就是算法,本文讲述归纳了入门级的几个机器学习算法,加大数据学习群:716581014一起加入AI技术大本营。 1、监督学习算法 这个算法由...

董黎明 ⋅ 32分钟前 ⋅ 0

Kylin 对维度表的的要求

1.要具有数据一致性,主键值必须是唯一的;Kylin 会进行检查,如果有两行的主键值相同则会报错。 2.维度表越小越好,因为 Kylin 会将维度表加载到内存中供查询;过大的表不适合作为维度表,默...

无精疯 ⋅ 35分钟前 ⋅ 0

58到家数据库30条军规解读

军规适用场景:并发量大、数据量大的互联网业务 军规:介绍内容 解读:讲解原因,解读比军规更重要 一、基础规范 (1)必须使用InnoDB存储引擎 解读:支持事务、行级锁、并发性能更好、CPU及...

kim_o ⋅ 38分钟前 ⋅ 0

代码注释中顺序更改 文件读写换行

`package ssh; import com.xxx.common.log.LogFactory; import com.xxx.common.log.LoggerUtil; import org.apache.commons.lang3.StringUtils; import java.io.*; public class DirErgodic ......

林伟琨 ⋅ 46分钟前 ⋅ 0

linux实用操作命令

参考 http://blog.csdn.net/qwe6112071/article/details/50806734 ls [选项] [目录名 | 列出相关目录下的所有目录和文件 -a 列出包括.a开头的隐藏文件的所有文件-A 同-a,但不列出"."和"...

简心 ⋅ 今天 ⋅ 0

preg_match处理中文符号 url编码方法

之前想过直接用符号来替换,但失败了,或者用其他方式,但有有些复杂,这个是一个新的思路,亲测可用 <?php$str='637朗逸·超速新风王(300)(白光)'; $str=iconv("UTF-8","GBK",$s...

大灰狼wow ⋅ 今天 ⋅ 0

DevOps 资讯 | PostgreSQL 的时代到来了吗 ?

PostgreSQL是对象-关系型数据库,BSD 许可证。拼读为"post-gress-Q-L"。 作者: Tony Baer 原文: Has the time finally come for PostgreSQL?(有删节) 近30年来 PostgreSQL 无疑是您从未听...

RiboseYim ⋅ 今天 ⋅ 0

github太慢

1:用浏览器访问 IPAddress.com or http://tool.chinaz.com 使用 IP Lookup 工具获得github.com和github.global.ssl.fastly.net域名的ip地址 2:/etc/hosts文件中添加如下格式(IP最好自己查一...

whoisliang ⋅ 今天 ⋅ 0

非阻塞同步之 CAS

为解决线程安全问题,互斥同步相当于以时间换空间。多线程情况下,只有一个线程可以访问同步代码。这种同步也叫阻塞同步(Blocking Synchronization). 这种同步属于一种悲观并发策略。认为只...

长安一梦 ⋅ 今天 ⋅ 0

云计算的选择悖论如何对待?

人们都希望在工作和生活中有所选择。但心理学家的调查研究表明,在多种选项中进行选择并不一定会使人们更快乐,甚至不会产生更好的决策。心理学家Barry Schwartz称之为“选择悖论”。云计算为...

linux-tao ⋅ 今天 ⋅ 0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

返回顶部
顶部