Floyd,最短路还真是比较多的说
博客专区 > 侯禹 的博客 > 博客详情
Floyd,最短路还真是比较多的说
侯禹 发表于4年前
Floyd,最短路还真是比较多的说
  • 发表于 4年前
  • 阅读 78
  • 收藏 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();
?>


标签: Floyd php ACM 算法
共有 人打赏支持
粉丝 93
博文 49
码字总数 34362
×
侯禹
如果觉得我的文章对您有用,请随意打赏。您的支持将鼓励我继续创作!
* 金额(元)
¥1 ¥5 ¥10 ¥20 其他金额
打赏人
留言
* 支付类型
微信扫码支付
打赏金额:
已支付成功
打赏金额: