単一ソース最短パス (ダイクストラ アルゴリズム) php 実装

症例のスコアリングに単一ソースの最短経路アルゴリズムが使用される医療プロジェクトを実行します。単一ソース最短経路のダイクストラ アルゴリズムの考え方は次のとおりです:
i から j への最短経路 (Vi...Vk,Vj) がある場合、Vk は Vj の前の頂点です。 。したがって、(Vi...Vk) も i から k への最短経路でなければなりません。ダイクストラは、最短経路の長さを増加させながら、最短経路を次々に生成するアルゴリズムです。たとえば、ソース頂点 V0 の場合、最初に直接隣接する頂点の中で最も長さが短い頂点 Vi を選択します。その後、V0 から Vj 頂点までの最短距離 dist[j]=min{dist[j] が現在わかっています。 ,dist[i]+cost[i][j]}。 G=、ソース点は V0、U={V0} はマークされた頂点のセットを表し、dist[i] は V0 から i までの最短距離を記録し、cost[i][j] はエッジを表すと仮定します。私はjにかかります。
1. V-U から dist[i] 値が最小の頂点 i を選択し、i を U に加算します。

2. i に直接隣接する頂点の dist 値を更新します。 (dist[j]=min{dist[j],dist[i]+cost[i][j]})

3. U=V がわかったら停止します。 P h PHP のユニークな性質を利用したコードは次のとおりです。

例を図に示します。 0
0 = & gt; 4: 10

0 = & gt ;3:60

0=>2:30
0=>1:70

転載元: Kangrui の部族 » 単一ソースの最短パスPHP の実装

🎜 🎜🎜 🎜