php-resource



Zurück   PHP-Scripte PHP-Tutorials PHP-Jobs und vieles mehr > Entwicklung > PHP Developer Forum
 

Login

 
eingeloggt bleiben
star Jetzt registrieren   star Passwort vergessen
 

 

 


PHP Developer Forum Hier habt ihr die Möglichkeit, eure Skriptprobleme mit anderen Anwendern zu diskutieren. Seid so fair und beantwortet auch Fragen von anderen Anwendern. Dieses Forum ist sowohl für ANFÄNGER als auch für PHP-Profis! Fragen zu Laravel, YII oder anderen PHP-Frameworks.

Antwort
 
LinkBack Themen-Optionen Thema bewerten
  #1 (permalink)  
Alt 16-09-2014, 22:00
narutos
 Registrierter Benutzer
Links : Onlinestatus : narutos ist offline
Registriert seit: Sep 2014
Beiträge: 23
narutos befindet sich auf einem aufstrebenden Ast
Standard 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.
Mit Zitat antworten
  #2 (permalink)  
Alt 16-09-2014, 22:01
narutos
 Registrierter Benutzer
Links : Onlinestatus : narutos ist offline
Registriert seit: Sep 2014
Beiträge: 23
narutos befindet sich auf einem aufstrebenden Ast
Standard

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;
      }
   } 
Mit Zitat antworten
  #3 (permalink)  
Alt 16-09-2014, 22:01
narutos
 Registrierter Benutzer
Links : Onlinestatus : narutos ist offline
Registriert seit: Sep 2014
Beiträge: 23
narutos befindet sich auf einem aufstrebenden Ast
Standard

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;
      }
   } 
Mit Zitat antworten
  #4 (permalink)  
Alt 16-09-2014, 22:02
narutos
 Registrierter Benutzer
Links : Onlinestatus : narutos ist offline
Registriert seit: Sep 2014
Beiträge: 23
narutos befindet sich auf einem aufstrebenden Ast
Standard

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;
      }
   } 
Mit Zitat antworten
  #5 (permalink)  
Alt 16-09-2014, 22:03
narutos
 Registrierter Benutzer
Links : Onlinestatus : narutos ist offline
Registriert seit: Sep 2014
Beiträge: 23
narutos befindet sich auf einem aufstrebenden Ast
Standard

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);
      }
   } 
Mit Zitat antworten
  #6 (permalink)  
Alt 16-09-2014, 22:04
narutos
 Registrierter Benutzer
Links : Onlinestatus : narutos ist offline
Registriert seit: Sep 2014
Beiträge: 23
narutos befindet sich auf einem aufstrebenden Ast
Standard

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. 
Mit Zitat antworten
  #7 (permalink)  
Alt 16-09-2014, 22:05
narutos
 Registrierter Benutzer
Links : Onlinestatus : narutos ist offline
Registriert seit: Sep 2014
Beiträge: 23
narutos befindet sich auf einem aufstrebenden Ast
Standard

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.
Mit Zitat antworten
Antwort

Lesezeichen


Aktive Benutzer in diesem Thema: 1 (Registrierte Benutzer: 0, Gäste: 1)
 

Ähnliche Themen
Thema Autor Forum Antworten Letzter Beitrag
A* und Dijkstra-Algos in PHP TobWen PHP Developer Forum 55 08-03-2007 22:55
php implementierung/konfiguration in Mac OS X elquejido Fragen zu Installation & Konfiguration (LAMP, WAMP & Co.) 6 02-11-2006 13:14
Frage bei Skript Implementierung Payne_of_Death PHP Developer Forum 1 21-12-2002 20:03
Leiter Implementierung (Festanstellung) Berni Jobgesuche 0 30-09-2002 16:32
Html&Php Tags anzeige ohne implementierung des Browsers DarkShadow81 PHP Developer Forum 1 09-08-2002 23:58

Themen-Optionen
Thema bewerten
Thema bewerten:

Forumregeln
Es ist Ihnen nicht erlaubt, neue Themen zu verfassen.
Es ist Ihnen nicht erlaubt, auf Beiträge zu antworten.
Es ist Ihnen nicht erlaubt, Anhänge hochzuladen.
Es ist Ihnen nicht erlaubt, Ihre Beiträge zu bearbeiten.

BB-Code ist an.
Smileys sind an.
[IMG] Code ist an.
HTML-Code ist aus.
Trackbacks are an
Pingbacks are an
Refbacks are an


PHP News

ebiz-trader 7.5.0 mit PHP7 Unterstützung veröffentlicht
ebiz-trader 7.5.0 mit PHP7 Unterstützung veröffentlichtDie bekannte Marktplatzsoftware ebiz-trader ist in der Version 7.5.0 veröffentlicht worden.

28.05.2018 | Berni

Wissensbestand in Unternehmen
Wissensbestand in UnternehmenLebenslanges Lernen und Weiterbilden sichert Wissensbestand in Unternehmen

25.05.2018 | Berni


 

Aktuelle PHP Scripte

PHP Server Monitor

PHP Server Monitor ist ein Skript, das prüft, ob Ihre Websites und Server betriebsbereit sind.

11.09.2018 Berni | Kategorie: PHP/ Security
PHP WEB STATISTIK ansehen PHP WEB STATISTIK

Die PHP Web Statistik bietet Ihnen ein einfach zu konfigurierendes Script zur Aufzeichnung und grafischen und textuellen Auswertung der Besuchern Ihrer Webseite. Folgende zeitlichen Module sind verfügbar: Jahr, Monat, Tag, Wochentag, Stunde Folgende son

28.08.2018 phpwebstat | Kategorie: PHP/ Counter
Affilinator - Affilinet XML Produktlisten Skript

Die Affilinator Affilinet XML Edition ist ein vollautomatisches Skript zum einlesen und darstellen der Affili.net (Partnerprogramm Netzwerk) Produktlisten und Produktdaten. Im Grunde gibt der Webmaster seine Affilinet PartnerID ein und hat dann unmittelb

27.08.2018 freefrank@ | Kategorie: PHP/ Partnerprogramme
 Alle PHP Scripte anzeigen

Alle Zeitangaben in WEZ +2. Es ist jetzt 21:08 Uhr.