文档章节

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

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

 

<?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();
?>


© 著作权归作者所有

共有 人打赏支持
侯禹
粉丝 94
博文 49
码字总数 34362
作品 0
海淀
程序员
USACO2.4 Overfencing(maze1)

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

jzzlee ⋅ 2012/06/30 ⋅ 0

HDU 3832 Earth Hour 【最短路好题 + 思维】

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

Anxdada ⋅ 01/17 ⋅ 0

Dijkstra算法--单源最短路径

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

Hacker_ZhiDian ⋅ 2017/02/07 ⋅ 0

HDU 1599 find the mincost route 【最短路之最小环模板】

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

Anxdada ⋅ 01/17 ⋅ 0

1.1.1最短路(Floyd、Dijstra、BellmanFord)

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

fire_to_cheat_ ⋅ 03/04 ⋅ 0

Jzoj3177 安全监控

选举越来越近了,所以总统Amabo Kcarab准备在美国计划一次旅行,并在WDC和LA进行演讲。特务为了能够保护总统的安全,需要时刻监控所有总统会经过的城市(包括WDC和LA)。 当然,为了使预算不...

JacaJava ⋅ 01/10 ⋅ 0

最短路径算法

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

Hosee ⋅ 2016/01/14 ⋅ 0

ACM复习专项

资料整理 ACM训练营 邝斌的ACM模板 牛客网哈理工ACM教学视频 视频网盘资料(密码:kntr) 第一阶段:练习经典常用算法 最短路(Floyd、Dijstra、BellmanFord) 最小生成树(先写个prim、kru...

fire_to_cheat_ ⋅ 03/04 ⋅ 0

Ipad也怕冷?!

今天,说一Ipad充不了电,我想才没买好久,这么快电池就坏了呀。难道买到歪货了? 它的表现是充电线一接上去,电池指示有反应,也有"闪电"标志,就是充不进去电。本来想打客服的,还是先问问...

gisweis ⋅ 2015/01/31 ⋅ 0

bzoj2662 [BeiJing wc2012]冻结

Description “我要成为膜法少女!” “那么,以灵魂为代价,你希望得到什么?” “我要将有关膜法和奇迹的一切,封印于卡片之中„„” 在这个愿望被实现以后的世界里,人们享受着膜法卡片(...

aziint ⋅ 2017/12/29 ⋅ 0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

从 Confluence 5.3 及其早期版本中恢复空间

如果你需要从 Confluence 5.3 及其早期版本中的导出文件恢复到晚于 Confluence 5.3 的 Confluence 中的话。你可以使用临时的 Confluence 空间安装,然后将这个 Confluence 安装实例升级到你现...

honeymose ⋅ 今天 ⋅ 0

Java8新增的DateTimeFormatter与SimpleDateFormat的区别

两者最大的区别是,Java8的DateTimeFormatter也是线程安全的,而SimpleDateFormat并不是线程安全。 在并发环境下使用SimpleDateFormat 为了能够在多线程环境下使用SimpleDateFormat,有这三种...

人觉非常君 ⋅ 今天 ⋅ 0

多线程如何控制执行顺序

线程的生命周期说明: 当线程被创建并启动以后,它既不是一启动就进入了执行状态,也不是一直处于执行状态,在线程的生命周期中,它要经过新建(New)、就绪(Runnable)、运行(Running)、...

MarinJ_Shao ⋅ 今天 ⋅ 0

用ZBLOG2.3博客写读书笔记网站能创造今日头条的辉煌吗?

最近两年,著名的自媒体网站今日头条可以说是火得一塌糊涂,虽然从目前来看也遇到了一点瓶颈,毕竟发展到了一定的规模,继续增长就更加难了,但如今的今日头条规模和流量已经非常大了。 我们...

原创小博客 ⋅ 今天 ⋅ 0

MyBatis四大核心概念

本文讲解 MyBatis 四大核心概念(SqlSessionFactoryBuilder、SqlSessionFactory、SqlSession、Mapper)。 MyBatis 作为互联网数据库映射工具界的“上古神器”,训有四大“神兽”,谓之:Sql...

waylau ⋅ 今天 ⋅ 0

以太坊java开发包web3j简介

web3j(org.web3j)是Java版本的以太坊JSON RPC接口协议封装实现,如果需要将你的Java应用或安卓应用接入以太坊,或者希望用java开发一个钱包应用,那么用web3j就对了。 web3j的功能相当完整...

汇智网教程 ⋅ 今天 ⋅ 0

2个线程交替打印100以内的数字

重点提示: 线程的本质上只是一个壳子,真正的逻辑其实在“竞态条件”中。 举个例子,比如本题中的打印,那么在竞态条件中,我只需要一个方法即可; 假如我的需求是2个线程,一个+1,一个-1,...

Germmy ⋅ 今天 ⋅ 0

Django第一期

安装Django 去https://www.djangoproject.com/download/ 下载最新版的Django,然后解压放到Anaconda\Lib\site-packages目录下,然后cmd进入此目录,输入安装命令: python setup.py install ...

大不了敲一辈子代码 ⋅ 今天 ⋅ 0

Springboot2 之 Spring Data Redis 实现消息队列——发布/订阅模式

一般来说,消息队列有两种场景,一种是发布者订阅者模式,一种是生产者消费者模式,这里利用redis消息“发布/订阅”来简单实现订阅者模式。 实现之前先过过 redis 发布订阅的一些基础概念和操...

Simonton ⋅ 今天 ⋅ 0

error:Could not find gradle

一.更新Android Studio后打开Project,报如下错误: Error: Could not find com.android.tools.build:gradle:2.2.1. Searched in the following locations: file:/D:/software/android/andro......

Yao--靠自己 ⋅ 昨天 ⋅ 0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

返回顶部
顶部