Implementierung des Dijkstra-Algorithmus

Hi

Ich habe den Dijkstra-Algorithmus implementiert. Mich würde interessieren, ob ich das richtig gemacht habe. Ich muss das Programm leider auf mehrere Einträge aufteilen.

PHP-Code:

   /**
    * Gewichtete Kante.
    * Container
    */
   class Edge
   {
      private $destinationNode;
      private $cost;
      
      /**
       * @param Node $destinationNode Ziel der gerichteten Kante.
       * @param number $cost Kosten (Gewicht)
       */
      function __construct(Node $destinationNode, $cost)
      {
         $this->destinationNode = $destinationNode;
         $this->cost = $cost;
      }
      /**
       * @return Node
       */
      function getDestinationNode()
      {
         return $this->destinationNode;
      }
      /**
       * @return number
       */
      function getCost()
      {
         return $this->cost;
      }
   } 


PHP-Code:

   /**
    * Knoten für Dijkstra.
    * Container.
    */
   class Node
   {
      private $label;
      private $outgoingEdges = []; // Ausgehende Kanten auf Nachbarsknoten
      
      /**
       * @param string $label eindeutige Knoten-ID
       */
      function __construct($label)
      {
         $this->label = $label;
      }
      /**
       * @return string
       */
      function getLabel()
      {
         return $this->label;
      }
      /**
       * Ausgehende Kante auf Nachbarsknoten.
       * @param Edge $edge
       */
      function addOutgoingEdge(Edge $edge)
      {
         $this->outgoingEdges[] = $edge;
      }
      /**
       * @return array
       */
      function getOutgoingEdges()
      {
         return $this->outgoingEdges;
      }
   } 


PHP-Code:

   class Dijkstra
   {
      private $startLabel;
      private $items;
      
      /**
       * @param string $startLabel Eindeutige ID jenes Knotens, zu dem die $items ermittelt wurden.
       * @param array $items
       */
      function __construct($startLabel, array $items)
      {
         $this->startLabel = $startLabel;
         $this->items = $items;
      }
      /**
       * @param string $destinationLabel Eindeutige ID jenes Knotens, zu dem der küzeste Pfad gefunden werden soll.
       * @return null|array Nodes
       *    null, falls der Zielknoten vom Startknoten aus nicht erreichbar ist.
       */
      function getShortestPathTo($label)
      {
      // was passiert wenn label nicht existiert?
         $node = $this->items[$label]['node']; // Zielknoten
         $nodes = [$node];
         while($label = $this->items[$label]['predLabel'])
         {
            $node = $this->items[$label]['node'];
            array_unshift($nodes, $node); // Knoten vorne einfügen
         }
         if($node->getLabel() != $this->startLabel) // Kontrolle, ob Startknoten erreicht
         {
            return null;
         }
         return $nodes;
      }
   } 


PHP-Code:

   class Graph
   {
      private $nodes = []; // Liste aller Graphen-Knoten, assoziatives Array, der key ist das label (eindeutige ID) des Knotens
      
      /**
       * Neuen Knoten anlegen.
       * @param string $label eindeutige ID des Knotens
       */
      function addNode($label)
      {
         $this->nodes[$label] = new Node($label);
      }
      /**
       * Neue Kante anlegen.
       * @param string $startLabel eindeutige ID des Startknotens
       * @param string $destinationLabel eindeutige ID des Zielknotens
       * @param number $cost >= 0 Kosten (Gewicht)
       * @throws Exception Wenn Start- oder Zielknoten nicht zuvor mittels addNode definiert wurden.
       */
      function addEdge($startLabel, $destinationLabel, $cost)
      {
         if(!array_key_exists($startLabel, $this->nodes))
         {
            throw new Exception('startLabel not exists');
         }
         if(!array_key_exists($destinationLabel, $this->nodes))
         {
            throw new Exception('destinationLabel not exists');
         }
         $this->nodes[$startLabel]->addOutgoingEdge(new Edge($this->nodes[$destinationLabel], $cost));
      }
      /**
       * @param string $startLabel Eindeutige ID jenes Knotens, zu dem die Knoten-d-Werte ermittelt werden sollen.
       * @throws Exception Wenn der Startknoten nicht zuvor mittels addNode definiert wurden.
       */
      function dijkstra($startLabel)
      {         
         // Initialisierung:
         $items = [];                             // Man könnte die Parameter d und pred auch als
         foreach($this->nodes as $label => $node) // Eigenschaften in der Klasse Node aufnehmen.  
         {                                        // Das Problem ist jedoch, dass jeder 
            $items[$label] =                      // Graph-Algorithmus andere Parameter benötigt. 
            [                                     // Node müsste also mit jedem neuen Algorithmus 
               'node' => $node,                   // verändert werden (verstößt gegen das 
               'd' => INF,                        // never-touch-a-running-system-Prinzip) und 
               'predLabel' => null                // würde immer größer werden (Gottes-Klasse).
            ];                                    // Darum gibt es in den Algorithmen statt 
         }                                        // dessen einen Warpper um node-Objekte.
         $labels = array_keys($this->nodes);

         // 1. Schritt:
         if(!array_key_exists($startLabel, $items))
         {
            throw new Exception('startLabel not exists');
         }
         $items[$startLabel]['d'] = 0;
         
         // alle weiteren Schritte:
         while(count($labels) > 0)
         {
            // Den Knoten mit dem kleinsten D aus $labels extrahieren:
            $minDItem = null;
            foreach($labels as $label)
            {
               if
               (
                  $minDItem === null ||
                  $items[$label]['d'] < $minDItem['d']
               )
               {
                  $minDItem = $items[$label];
               }
            }
            $minDItemLabel = $minDItem['node']->getLabel();
            $labels = array_diff($labels, [$minDItemLabel]);
            
            // Nachbarsknoten von $minDItem:
            foreach($minDItem['node']->getOutgoingEdges() as $edge)
            {
               // Nachbarsknoten von $minDItem, die sich noch in $labels befinden:
               $minDNeighbourLabel = $edge->getDestinationNode()->getLabel();
               if(in_array($minDNeighbourLabel, $labels))
               {
                  $minDNeighbourItem = &$items[$minDNeighbourLabel];
                  $d = $minDItem['d'] + $edge->getCost();    // Knotenkosten + Kantenkosten zum Nachbarsknoten
                  if                                         // Bei extrem hohen Werten kann d auch INF werden. Auch
                  (                                          // in diesem Fall gibt es eine Verbindung zwischen den
                     is_infinite($minDNeighbourItem['d']) || // Knoten. Da INF < INF jedoch false liefert, muss hier
                     $d < $minDNeighbourItem['d']            // extra noch auf is_infinite kontrolliert werden.
                  )
                  {
                     $minDNeighbourItem['d'] = $d;
                     $minDNeighbourItem['predLabel'] = $minDItemLabel;
                  }
               }
            }
         }
         print_r($items);
         // Macht man mehrere Abfragen mit unterschiedlichen Zielknoten, jedoch immer mit
         // gleichem Startknoten, muss man diese Methode nicht immer wieder neu aufrufen.
         // Dann reicht es, von den Knoten einen Snapshot zu machen und diesen einem 
         // eigenen Objekt zu übergeben:
         return new Dijkstra($startLabel, $items);
      }
   } 


PHP-Code:

//         10       1
   //        |--> u -----> v
   //        |   2|˄     5|˄ 
   //        |    ||   7  ˅|6
   // Start  s <--++------ y
   // knoten |    ||       ˄
   //        |    ˅|3      |
   //        |--> x -------|
   //          5       2
   $graph = new Graph();
   $graph->addNode('s');
   $graph->addNode('u');
   $graph->addNode('v');
   $graph->addNode('x');
   $graph->addNode('y');
   $graph->addEdge('s', 'u', 10);
   $graph->addEdge('s', 'x', 5);
   $graph->addEdge('x', 'u', 3);
   $graph->addEdge('x', 'y', 2);
   $graph->addEdge('u', 'x', 2);
   $graph->addEdge('u', 'v', 1);
   $graph->addEdge('v', 'y', 5);
   $graph->addEdge('y', 'v', 6);
   $graph->addEdge('y', 's', 7);
   $dijkstra = $graph->dijkstra('s');
   var_dump($dijkstra->getShortestPathTo('u')); // [s, x, u]
   
   //         10     
   //        |--- u
   //        |    |
   //        ˅    |
   // Start  s    |2
   // knoten |    |
   //        |    ˅
   //        |--> x 
   //          5 
   /*$graph = new Graph();
   $graph->addNode('s');
   $graph->addNode('u');
   $graph->addNode('x');
   $graph->addEdge('u', 's', 10);
   $graph->addEdge('u', 'x', 2);
   $graph->addEdge('s', 'x', 5);
   $dijkstra = $graph->dijkstra('s');
   var_dump($dijkstra->getShortestPathTo('u')); // null ... es gibt keinen Pfad von s nach u*/
   
   // Start    1E308   1E308
   // knoten s ----> x ----> y
   /*$graph = new Graph();
   $graph->addNode('s');
   $graph->addNode('x');
   $graph->addNode('y');
   $graph->addEdge('s', 'x', 1E308);
   $graph->addEdge('x', 'y', 1E308);
   $dijkstra = $graph->dijkstra('s');
   $nodes = $dijkstra->getShortestPathTo('y');
   //print_r($nodes); // [s, x, y]*/
   
   //          1     2
   //        |--> u ---|
   //        |         |
   //        |         ˅
   // Start  s         z
   // knoten |         ˄
   //        |         |
   //        |--> v ---|
   //          1     2 
   /*$graph = new Graph();
   $graph->addNode('s');
   $graph->addNode('u');
   $graph->addNode('v');
   $graph->addNode('z');
   $graph->addEdge('s', 'u', 1);
   $graph->addEdge('s', 'v', 1);
   $graph->addEdge('u', 'z', 2);
   $graph->addEdge('v', 'z', 2);
   $dijkstra = $graph->dijkstra('s');*/
   //      s
   //    /   \
   //  u       v
   //  |
   //  z
   // 
   // u ist vor v definiert, darum hängt z an u.
   // Bei gleichen Kosten hängt z also am zuerst definierten Knoten u.
   //         1E308    1E308
   //        |-----> u ------|
   //        |               |
   //        |               ˅
   // Start  s               z
   // knoten |               ˄
   //        |               |
   //        |-----> v ------|
   //         1E308    1E308
   /*$graph = new Graph();
   $graph->addNode('s');
   $graph->addNode('u');
   $graph->addNode('v');
   $graph->addNode('z');
   $graph->addEdge('s', 'u', 1E308);
   $graph->addEdge('s', 'v', 1E308);
   $graph->addEdge('u', 'z', 1E308);
   $graph->addEdge('v', 'z', 1E308);
   $dijkstra = $graph->dijkstra('s');*/
   // Ergeben Summen unendlich, ist es umgekehrt. 
   // z hängt an v, weil v nach u definiert ist. 


Gegenüber dem Original-Algorithmus habe ich noch die Möglichkeit eingebaut, dass man auch mit INF-Werten arbeiten kann. Ergibt eine Berechung INF, wird der zugehörige Knoten in den aufspannenden Baum aufgenommen.

Allerdings verhält sich der Algorithmus dann ein wenig anders. Siehe Kommentare bei den Testfällen.