文档章节

Floyd,最短路还真是比较多的说

侯禹
 侯禹
发布于 2013/07/28 23:20
字数 357
阅读 82
收藏 1

 

<?php
class Floy{
 public $INT_MAX = 0x7fffffff;
 public $maxn = 101;     //点个数
 public $map= array();//[maxn][maxn];    //邻接矩阵
 public $pre= array();//[maxn][maxn];    //pre[2][3]存储最短路径3的前一个点是2
 public $dist= array();//[maxn][maxn];
 public $n;
 
 function floyd()
 {
  for($i=1;$i<=$this->n;$i++)
  {
   for($j=1;$j<=$this->n;$j++)
   {
    $this->dist[$i][$j] = $this->map[$i][$j];
    $this->pre[$i][$j] = $i;
   }
  }
  
  for($k=1;$k<=$this->n;$k++)
  {
   for($i=1;$i<=$this->n;$i++)
   {
    for($j=1;$j<=$this->n;$j++)
    {
if($this->dist[$i][$k]!=$this->INT_MAX
&&$this->dist[$k][$j]!=$this->INT_MAX
&&$this->dist[$i][$k]+$this->dist[$k][$j]<$this->dist[$i][$j])
     {
      $this->dist[$i][$j]=$this->dist[$i][$k]+$this->dist[$k][$j];
      $this->pre[$i][$j]=$this->pre[$k][$j];
     }
    }
   }
  }
 }
 
 function main()
 {
  //freopen("IN.TXT","r",stdin);
  //scanf("%d",&n);
  $this->n = 4;
  
  $from;$to;$w;
  for($i=1;$i<=$this->n;$i++)
  {
   for($j=1;$j<=$this->n;$j++)
    $this->map[$i][$j]=$this->INT_MAX;
  }
  for($i=1;$i<=$this->n;$i++)
  $this->map[$i][$i]=0;
  /*while(scanf("%d%d%d",&from,&to,&w)!=EOF)
  {
   if(from==0)
   break;
   map[from][to]=w;
   map[to][from]=w;
  }*/
  
  /*毕竟是脚本语言,IO你懂的,我还是固化吧,HTML代码实在是。。。。,上面是C的代码*/
  
  $this->map[1][2] = 3;
  $this->map[2][1] = 3;
  
  $this->map[2][3] = 1;
  $this->map[3][2] = 1;
  
  $this->map[2][4] = 3;
  $this->map[4][2] = 3;
  
  $this->map[3][4] = 1;
  $this->map[4][3] = 1;
  
  
   
  for($i=1;$i<=$this->n;$i++)
  {
   for($j=1;$j<=$this->n;$j++)
    echo "i:".$i."j:".$j."   ".$this->map[$i][$j]."<br>";
  }
  
  echo "<br>Floyd:<br>";
  $this->floyd();
  
  for($i=1;$i<=$this->n;$i++)
  {
   for($j=1;$j<=$this->n;$j++)
   echo "i:".$i."j:".$j."   ".$this->dist[$i][$j]."<br>";
  }
  return 0;
 }
}
?>
<?php
$floy = new Floy();
$floy->main();
?>


© 著作权归作者所有

共有 人打赏支持
侯禹
粉丝 95
博文 49
码字总数 34362
作品 0
海淀
程序员
【floyd】【bitset】洛谷 P1841 [JSOI2007]重要的城市 题解

bitset玄学完美优化复杂度? 题目描述 参加jsoi冬令营的同学最近发现,由于南航校内修路截断了原来通向计算中心的路,导致去的路程比原先增加了近一公里。而食堂门前施工虽然也截断了原来通向...

wjyyy
08/24
0
0
USACO2.4 Overfencing(maze1)

首先想到的就是求图中各点之间的最短路,将每个空和两个出口作为图的点,两个直接相连的点之间的权为1,同一个点的权为0,其余不直接相连的点之间的权初始化为最大值,然后应用Floyd算法,求...

jzzlee
2012/06/30
0
0
HDU 3832 Earth Hour 【最短路好题 + 思维】

传送门 // 题意 : 给定n(n>=3)个路灯的二维平面上的位置以及他们能照射到的范围r, 如果两个路灯照射的范围有重合的地方, 那么说明这两个路灯是相连的. 问现在最多可以关闭多少个路灯使得前三...

Anxdada
01/17
0
0
Dijkstra算法--单源最短路径

在http://blog.csdn.net/hackerzhidian/article/details/54898064这一篇博客中总结了一下在求图的最短路中的一个算法-Floyd算法,Floyd算法用于求图的多源最短路径(多源最短路径:图的所有顶...

Hacker_ZhiDian
2017/02/07
0
0
HDU 1599 find the mincost route 【最短路之最小环模板】

传送门 // 求一个至少有三个点的环的路径和最小. // 由于n很小, 那么我们直接跑floyd求环, 大部分都和floyd本身很像, 只是多了一步和一个原始数组, 不能根据原数组进行更新, 因为原数组不断更...

Anxdada
01/17
0
0

没有更多内容

加载失败,请刷新页面

加载更多

OSChina 周日乱弹 —— 恨不得给你买张飞机挂票

Osc乱弹歌单(2018)请戳(这里) 【今日歌曲】 @开源中国首席灵魂师:分享张希/曹方的单曲《认真地老去》 来不及认真的年轻过,就认真的老去! 《认真地老去》- 张希/曹方 手机党少年们想听...

小小编辑
17分钟前
27
5
如何实现靠谱的分布式锁?

分布式锁,是用来控制分布式系统中互斥访问共享资源的一种手段,从而避免并行导致的结果不可控。基本的实现原理和单进程锁是一致的,通过一个共享标识来确定唯一性,对共享标识进行修改时能够...

郑加威
今天
1
0
Mac OS X下Maven的安装与配置

Mac OS X 安装Maven: 下载 Maven, 并解压到某个目录。例如/Users/robbie/apache-maven-3.3.3 打开Terminal,输入以下命令,设置Maven classpath $ vi ~/.bash_profile 添加下列两行代码,之后...

TonyStarkSir
今天
3
0
关于编程,你的练习是不是有效的?

最近由于工作及Solution项目的影响,我在重新学习DDD和领域建模的一些知识。然后,我突然就想到了这个问题,以及我是怎么做的? 对于我来说,提升技能的项目会有四种: 纯兴趣驱动的项目。即...

问题终结者
今天
4
0
打开eclipse出现an error has occurred see the log file

解决方法: 1,打开eclipse安装目录下的eclipse.ini文件; 2,打开的文本文件最后添加一行 --add-modules=ALL-SYSTEM 3,保存重新打开Eclipse。...

任梁荣
昨天
4
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部