為什么80%的碼農都做不了架構師？>>> ??

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

轉載于:https://my.oschina.net/MrHou/blog/143896

總結

以上是生活随笔為你收集整理的关于迪杰斯特拉算法（最短路）的PHP实现的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。