文档章节

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

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


© 著作权归作者所有

共有 人打赏支持
侯禹
粉丝 95
博文 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
基本算法——图算法之最短路径(Dijkstra)

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

安然若知
07/13
0
0
迪杰斯特拉改进

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

watertiger
2017/05/04
41
0

没有更多内容

加载失败,请刷新页面

加载更多

数字转换为字符的L受哪个参数影响

我们知道,如果想把金额带上本位币,一般加上L, 比如: select to_char(salary,'L99,9999.00') from employees; 下面显示如下: SALARY TO_CHAR(SALARY,'L99, 2900 ¥2,900.00 2500 ¥2,500.00 ...

tututu_jiang
28分钟前
2
0
shell编程(告警系统主脚本、告警系统配置文件、告警系统监控项目)

告警系统主脚本 先定义监控系统的各个目录,然后再去定义主脚本,因为是分布式的,所以需要每台机器都这样做,如果事先有创建好各个目录和各个脚本,那么就可以把这些目录和脚本copy到其他机...

蛋黄_Yolks
29分钟前
2
0
SAP HANA Backup and Recovery

SAP HANA Backup and Recovery Skip to end of metadata Created by Paul Power, last modified on Nov 23, 2017 Go to start of metadata Purpose System Privileges How to Perform a Back......

rootliu
30分钟前
2
0
JVM的持久代——何去何从?

本文会介绍一些JVM内存结构的基本概念,然后很快会讲到持久代,来看下Java SE 8发布后它究竟到哪去了。 基础知识 JVM只不过是运行在你系统上的另一个进程而已,这一切的魔法始于一个java命令...

java知识分子
47分钟前
2
0
Hive和HBase的区别

hive是文件的视图,hbase是建了索引的key-value表。 先放结论:Hbase和Hive在大数据架构中处在不同位置,Hbase主要解决实时数据查询问题,Hive主要解决数据处理和计算问题,一般是配合使用。...

飓风2000
53分钟前
2
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部