Dijkstra kürzester Pfad in PHP implementiert

In diesem Artikel wird hauptsächlich der in PHP implementierte Dijkstra-Kürzeste-Pfad-Algorithmus vorgestellt, das Konzept und die Funktion des Dijkstra-Kürzeste-Pfad-Algorithmus kurz beschrieben und die Implementierung von Dijkstra in PHP anhand spezifischer Beispiele analysiert (Dijkstra) Algorithmus für den kürzesten Weg, Freunde in Not können sich darauf beziehen

Dieser Artikel beschreibt den in PHP implementierten Dijkstra-Algorithmus für den kürzesten Weg. Teilen Sie es wie folgt mit allen als Referenz:

1. Zu lösende Probleme

Problem mit dem kürzesten Weg aus einer Hand, in einem gegebenen Fall gerichtet Das Problem, den kürzesten Weg von einem Scheitelpunkt (einzelner Quellscheitelpunkt) zu allen anderen Scheitelpunkten im Diagramm zu finden. In der Abbildung unten gibt es an jeder Kante ein Gewicht, und wir hoffen, den kürzesten Weg von A zu allen anderen Eckpunkten (B/C/D/E/F/G) zu finden.

2. Problemanalyse (die Unterstruktur des kürzesten Weges ist ebenfalls optimal)

Wenn P (A,G) ist der kürzeste Weg vom Scheitelpunkt A nach G. Unter der Annahme, dass D und F die Mittelpunkte auf diesem Weg sind, muss P(D,F) der kürzeste Weg von D nach F sein. Wenn P(D,F) nicht der kürzeste Weg von D nach F ist, muss es von einem bestimmten Knoten M aus einen anderen Weg von D nach F geben, der P(A,B...M...F,G) ermöglichen kann ) schneller als P (A,G) ist klein und widersprüchlich.

Mit dieser Eigenschaft können wir den Dijkstra-Algorithmus verstehen.

3. Dijkstra-Algorithmus

Dijkstra-Algorithmus, auch Dijkstra-Algorithmus genannt, auch Single-Source-Shortest-Path-Algorithmus genannt, Die sogenannte Single-Source ist das Problem, den kürzesten Weg von einem Knoten zu allen erreichbaren Knoten in einem gerichteten Graphen zu finden. Das Problem wird unter der Annahme beschrieben, dass G = (V, E) ein gerichteter Graph ist, V den Scheitelpunkt und E die Kante darstellt. Jede seiner Kanten (i, j) gehört zu E und hat ein nicht negatives Gewicht W (I, j). Um einen Knoten v0 in G anzugeben, muss jeder Link von v0 nach G mit vj verbunden werden (vj gehört zu V). kürzester gerichteter Weg (oder weisen Sie darauf hin, dass es ihn nicht gibt). Der Algorithmus von Dijstra verwendet eine gierige Strategie, die vom Quellpunkt ausgeht und durch verbundene Punkte kontinuierlich die kürzeste Entfernung zu anderen Punkten findet.

Dijkstras gierige Anwendung nutzt die Eigenschaften in (2), um kontinuierlich die „nächsten“ Knoten auszuwählen und alle möglichen Verbindungen jedes Knotens zu erkunden, wobei sie sich Schicht für Schicht nach außen ausdehnt, wobei der Startpunkt das Zentrum darstellt, bis er sich erstreckt der Endpunkt. Erweitern Sie für Quellpunkt A schrittweise und aktualisieren Sie die Scheitelpunktinformationen direkt neben i gemäß dist[j]=min{dist[j],dist[i]+matrix[i][j]}.

Algorithmusbeschreibung

1) Algorithmusidee:

Angenommen, G=(V,E) ist ein gewichteter gerichteter Graph. Die Scheitelpunktmenge V ist In zwei Gruppen unterteilt. Die erste Gruppe ist die Scheitelpunktmenge, für die der kürzeste Pfad gefunden wurde (dargestellt durch S). ​​Zunächst gibt es nur einen Quellpunkt in S. Anschließend wird jeder kürzeste Pfad gefunden und dem hinzugefügt Setze S, bis alle Scheitelpunkte zu S hinzugefügt werden und der Algorithmus endet. Die zweite Gruppe ist die verbleibende Menge von Scheitelpunkten, für die der kürzeste Pfad nicht bestimmt wurde (dargestellt durch U). in der Reihenfolge zunehmender kürzester Pfadlänge. Während des Verbindungsprozesses wird die Länge des kürzesten Pfads vom Quellpunkt v zu jedem Scheitelpunkt in S immer so beibehalten, dass sie nicht größer ist als die Länge des kürzesten Pfads vom Quellpunkt v zu jedem Scheitelpunkt in U. Darüber hinaus entspricht jeder Scheitelpunkt einem Abstand. Der Abstand des Scheitelpunkts in S ist die kürzeste Weglänge von v zu diesem Scheitelpunkt. Der Abstand des Scheitelpunkts in U ist der aktuelle Weg von v zu diesem Scheitelpunkt, der nur die Scheitelpunkte in umfasst S als Zwischenscheitelpunkte.

2) Algorithmusschritte:

a. Anfangs enthält S nur den Quellpunkt, also S={v}, und der Abstand von v ist 0. U enthält andere Scheitelpunkte außer v, das heißt: U={andere Scheitelpunkte}. Wenn v eine Kante mit Scheitelpunkt u in U hat, hat den normalen Gewichtswert v, Dann ist das Gewicht von

b. Wählen Sie einen Scheitelpunkt k von U mit dem kleinsten Abstand v und addieren Sie k zu S (der ausgewählte Abstand ist die kürzeste Weglänge von v nach k).

c. Ändern Sie den Abstand jedes an k angrenzenden Scheitelpunkts in U, wenn der Abstand vom Quellpunkt v zum Scheitelpunkt u (vorbei an Scheitelpunkt k) größer ist Originalabstand (nicht nach dem Passieren von Scheitelpunkt k) kurz, ändern Sie den Abstandswert von Scheitelpunkt u. Der geänderte Abstandswert ist der Abstand von Scheitelpunkt k plus dem Gewicht der Kante zwischen k und u.

d. Wiederholen Sie die Schritte b und c, bis alle Eckpunkte in S enthalten sind.

4. Algorithmus PHP-Implementierung

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

Aufrufklasse:

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

Ausführungsergebnis:

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

Das obige ist der detaillierte Inhalt vonDijkstra kürzester Pfad in PHP implementiert. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!