文档章节

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


© 著作权归作者所有

共有 人打赏支持
侯禹
粉丝 96
博文 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

没有更多内容

加载失败,请刷新页面

加载更多

如何删除本地服务

Microsoft Windows [版本 10.0.17134.407] (c) 2018 Microsoft Corporation。保留所有权利。 C:\WINDOWS\system32>SC 描述: SC 是用来与服务控制管理器和服务进行通信 的命令行程序。 用法:...

码农屌丝
17分钟前
1
0
Web安全学习规划

一名合格的Web安全工程师是要具备很多的知识点,不但要对网站架构熟悉,通讯协议,测试流程与测试工具使用,漏洞利用脚本编写,还有需要经验的积累等。 互联网进入下半场,竞争越发的激烈,能...

Linux就该这么学
21分钟前
1
0
爬虫Requests基本使用

Requests基本使用 安装 pip install requests 一、Requests模块请求 获取网页(不带参数) r = requests.get('http://www.chinahufei.com')r = requests.post('http://www.chinahufei.com')......

chinahufei
22分钟前
1
0
为什么要学习Python?这10个理由足够了!

摘要: 看完这十个理由,我决定买本python从入门到精通! 如果你定期关注现今的科技发展,那么你可能想知道我为什么要写这篇文章告诉人们学习Python?因为几年前我提倡Java而不是Python。 在...

阿里云官方博客
35分钟前
6
0
spring服务方式配置okhttp3

问题 如果把OKhttp以Spring服务方式配置,就解决了从配置中心运行时刷新配置参数的问题。 OkHttpConfig.java package com.zyl.config;import okhttp3.OkHttpClient;import org.springfra...

亚林瓜子
35分钟前
2
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部