Implementierung des Dijkstra-Algorithmus

Einklappen
X
 
  • Filter
  • Zeit
  • Anzeigen
Alles löschen
neue Beiträge

  • 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.
    Aufgrund Spams ignoriere ich h3ll.

  • #2
    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;
          }
       } 
    Aufgrund Spams ignoriere ich h3ll.

    Kommentar


    • #3
      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;
            }
         } 
      Aufgrund Spams ignoriere ich h3ll.

      Kommentar


      • #4
        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;
              }
           } 
        Aufgrund Spams ignoriere ich h3ll.

        Kommentar


        • #5
          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);
                }
             } 
          Aufgrund Spams ignoriere ich h3ll.

          Kommentar


          • #6
            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. 
            Aufgrund Spams ignoriere ich h3ll.

            Kommentar


            • #7
              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.
              Aufgrund Spams ignoriere ich h3ll.

              Kommentar

              Lädt...
              X