文档章节

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

侯禹
 侯禹
发布于 2013/07/10 23:07
字数 403
阅读 280
收藏 8
 
<?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);
?>


© 著作权归作者所有

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

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

fire_to_cheat_
03/04
0
0
游戏中的人工智能之流场寻路

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

RonTang
2016/04/20
0
0
迪杰斯特拉(Dijkstra)算法描述与路径计算

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

墨痕hz
2017/11/28
0
0
迪杰斯特拉改进

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

krole
2017/05/04
75
0
基本算法——图算法之最短路径(Dijkstra)

迪杰斯特拉算法是由荷兰计算机科学家狄克斯特拉于1959 年提出的,因此又叫狄克斯特拉算法。是从一个顶点到其余各顶点的最短路径算法,针对的是非负权边,解决的是有向图中最短路径问题。迪杰...

安然若知
07/13
0
0

没有更多内容

加载失败,请刷新页面

加载更多

自定义 Maven 的 repositories

有时,应用中需要一些比较新的依赖,而这些依赖并没有正式发布,还是处于milestone或者是snapshot阶段,并不能从中央仓库或者镜像站上下载到。此时,就需要 自定义Maven的<repositories>。 ...

waylau
53分钟前
1
0
徒手写一个es6代码库

mkdir democd demonpm initnpm install -g babelnpm install -g babel-clinpm install --save-dev babel-preset-es2015-node5 在项目目录创建两个文件夹 functional-playground ......

lilugirl
53分钟前
2
0
linux定位应用问题的一些常用命令,特别针对内存和线程分析的dump命令

1.jps找出进程号,找到对应的进程号后面才好继续操作 2.linux查看进程详细信息 ps -ef | grep 进程ID 3. dump内存信息 Jmap -dump:format=b,file=YYMMddhhmm.dump pid 4.top查看cpu占用信息 ...

noob_chr
54分钟前
1
0
Android TV开发-按键焦点

写在前面 按键焦点过程了解 2.1 dispatchKeyEvent 过程了解 2.2 焦点查找请求过程了解 1.2.1 第一次获取焦点 1.2.3 按键焦点 焦点控制 焦点记忆 应用场景 参考资料 [TOC] 1. 写在前面 工...

冰雪情缘l
54分钟前
1
0
java框架学习日志-3

这章主要是补充一些ioc创建对象的方式,ioc容器在写好<bean></bean>的时候就已经创建对象了。在之前的例子中,一直都是无参的构造方法。下面给出有参的构造方法的对象的创建,没有什么难点重...

白话
56分钟前
2
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部