PHPで実装されたダイクストラ最短経路

この記事では、主に PHP に実装されたダイクストラ最短経路アルゴリズムを紹介し、ダイクストラ最短経路アルゴリズムの概念と機能を簡単に説明し、具体的な例に基づいて PHP に実装されたダイクストラ最短経路アルゴリズムを分析します (最短の関連手順と操作スキル)。パス アルゴリズム。必要な友人はそれを参照できます

この記事では、PHP で実装されたダイクストラ最短パス アルゴリズムについて説明します。参考のために皆さんと共有してください。詳細は次のとおりです:

1. 解決すべき問題

単一ソース最短経路問題、1 つの頂点 (単一ソース頂点) から他のすべての頂点までの最短経路を見つける指定された有向グラフのパス問題。下の図では、各エッジに重みがあり、A から他のすべての頂点 (B/C/D/E/F/G) までの最短パスを見つけたいと考えています。

2. 問題分析（最短経路の部分構造も最適）

頂点AからGまでの最短経路がP(A,G)のとき、DとFは次であるとする。パス上の中間点、つまり P(D,F) は、D から F への最短パスでなければなりません。 P(D,F) が D から F への最短パスではない場合、P(A,B...M...F,G を実現できる、特定のノード M から D への別のパスが存在する必要があります) ) P (A,G) より速いのは小さくて矛盾します。

このような性質により、ダイクストラのアルゴリズムを理解することができます。

3. ダイクストラ アルゴリズム

ダイクストラ アルゴリズム、ダイクストラ アルゴリズム (ダイクストラ) とも呼ばれ、単一ソース最短経路アルゴリズムとも呼ばれます。いわゆる単一ソースは、頂点から始まる有向グラフ内にあり、この頂点から到達可能なすべての頂点までの最短パス。 この問題は、G = (V, E) が有向グラフであり、V が頂点を表し、E がエッジを表すと仮定して説明されます。その各エッジ (i, j) は E に属し、非負の重み W (I, j) を持ちます。 G 内のノード v0 を指定するには、v0 から G までのすべてのリンクを vj (vj は V に属します) に接続する必要があります。最短の有向パス (または、それが存在しないことを指摘)。 Dijstra のアルゴリズムは、ソース ポイントから開始して、接続されたポイントを介して他のポイントまでの最短距離を常に見つけるという貪欲な戦略を使用します。

Dijkstra の貪欲なアプリケーションは、(2) のプロパティを使用して、「最も近い」ノードを継続的に選択し、各ノードの可能なすべてのリンクを探索し、始点を中心に終点まで外側にレイヤーごとに拡張します。ソース点 A については、dist[j]=min{dist[j],dist[i]+matrix[i][j]} に従って、徐々に拡張し、i に直接隣接する頂点情報を更新します。

アルゴリズムの説明

1) アルゴリズムのアイデア:

G=(V,E) が重み付き有向グラフであると仮定し、グラフ内の頂点セット V を 2 つのグループに分割します。最初のグループは、見つかった頂点のセット (S で表されます。最初は S にソース点が 1 つだけあります。後で最短パスが見つかるたびに、すべての頂点が S に追加されるまで、そのパスがセット S に追加されます。アルゴリズム)終了)、2 番目のグループは、最短パスが決定されていない残りの頂点セットです (U で表されます)。2 番目のグループの頂点は、最短パスの長さの増加順に S に追加されます。結合プロセス中、ソース点 v から S の各頂点までの最短パスの長さは、ソース点 v から U の任意の頂点までの最短パスの長さ以下に常に維持されます。さらに、各頂点は距離に対応します。S の頂点の距離は、v からこの頂点までの最短パス長です。U の頂点の距離は、v からこの頂点までの現在のパスです。中間頂点としての S。

2) アルゴリズムのステップ:

a. 最初は、S にはソース点のみが含まれており、つまり S={v}、v の距離は 0 です。 U には v 以外の他の頂点が含まれます。つまり、U={other vertices} です。v が U に頂点 u を持つエッジを持っている場合、u が の出力エッジ隣接点でない場合、 は通常の重み値を持ちます。 v の場合、 の重みは ∞ です。

b. 最小距離 v を持つ頂点 k を U から選択し、k を S に追加します (選択した距離は v から k までの最短経路長です)。

c. k を新たに考慮した中間点として、ソース点 v から頂点 u までの距離 (頂点 k を通過しない) が元の距離より長い場合、k に隣接する U の各頂点の距離を変更します。頂点 k まで) 短い場合は、頂点 u の距離値を変更します。変更された距離値は、頂点 k の距離に k と u の間のエッジの重みを加えたものになります。

d. すべての頂点が S に含まれるまで、手順 b と c を繰り返します。

4. アルゴリズムPHP実装

<?php
class Dijkstra
{
  private $G;
  public function __construct()
  {
    //有向图存储
    $this->G = array(
      array(0,1,2,0,0,0,0),
      array(0,0,0,1,2,0,0),
      array(0,0,0,0,0,2,0),
      array(0,0,0,0,0,1,3),
      array(0,0,0,0,0,0,3),
      array(0,0,0,0,0,0,1),
      array(0,0,0,0,0,0,0),
    );
  }
  public function calculate()
  {
    // 存储已经选择节点和剩余节点
    $U = array(0);
    $V = array(1,2,3,4,5,6);
    // 存储路径上节点距离源点的最小距离
    $d = array();
    //初始化图中节点与源点0的最小距离
    for($i=1;$i<7;$i++)
    {
      if($this->G[0][$i]>0)
      {
        $d[$i] = $this->G[0][$i];
      }
      else
      {
        $d[$i] = 1000000;
      }
    }
    // n-1次循环完成转移节点任务
    for($l=0;$l<6;$l++)
    {
      // 查找剩余节点中距离源点最近的节点v
      $current_min = 100000;
      $current_min_v = 0;
      foreach($V as $k=>$v)
      {
        if($d[$v] < $current_min)
        {
          $current_min = $d[$v];
          $current_min_v = $v;
        }
      }
      //从V中更新顶点到U中
      array_push($U,$current_min_v);
      array_splice($V,array_search($current_min_v,$V),1);
      //更新
      foreach($V as $k=>$u)
      {
        if($this->G[$current_min_v][$u]!=0&&$d[$u]>$d[$current_min_v]+$this->G[$current_min_v][$u])
        {
          $d[$u] = $d[$current_min_v]+$this->G[$current_min_v][$u];
        }
      }
    }
    foreach($d as $k => $u)
    {
      echo $k.&#39;=>&#39;.$u.&#39;<br>&#39;;
    }
  }
}
?>

呼び出しクラス:

$D = new Dijkstra;
$D->calculate();

実行結果:

1=>1
2=>2
3=>2
4=>3
5=>3
6=>4

以上がPHPで実装されたダイクストラ最短経路の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。