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, 23: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, 23: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, 23: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, 23: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, 23: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, 23: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, 23: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 23:55
php implementierung/konfiguration in Mac OS X elquejido Fragen zu Installation & Konfiguration (LAMP, WAMP & Co.) 6 02-11-2006 14:14
Frage bei Skript Implementierung Payne_of_Death PHP Developer Forum 1 21-12-2002 21:03
Leiter Implementierung (Festanstellung) Berni Jobgesuche 0 30-09-2002 17:32
Html&Php Tags anzeige ohne implementierung des Browsers DarkShadow81 PHP Developer Forum 1 10-08-2002 00: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

ADSMAN V3 - Werbe-Manager ansehen ADSMAN V3 - Werbe-Manager

ADSMAN V3 - mehr als nur ein Bannermanager! Banner, Textanzeigen und PagePeel Manager! Mit ADSMAN PRO haben Sie die Marketinglösung für eine effektive und effiziente Werbeschaltung mit messbaren Ergebnissen. Unterstützt werden Bannerformate in beliebi

25.10.2018 virtualsystem | Kategorie: PHP/ Bannerverwaltung
PHP News und Artikel Script V2

News schreiben, verwalten, veröffentlichen. Dies ist jetzt mit dem neuen PHP News & Artikel System von virtualsystem.de noch einfacher. Die integrierte Multi-User-Funktion und der WYSIWYG-Editor (MS-Office ähnliche Bedienung) ermöglichen...

25.10.2018 virtualsystem | Kategorie: PHP/ News
Top-Side Guestbook

Gästebuch auf Textbasis (kein MySQL nötig) mit Smilies, Ip Sperre (Zeit selbst einstellbar), Spamschutz, Captcha (Code-Eingabe), BB-Code, Hitcounter, Löschfunktion, Editierfunktion, Kommentarfunktion, Kürzung langer Wörter, Seiten- bzw. Blätterfunktion, V

22.10.2018 webmaster10 | Kategorie: PHP/ Gaestebuch
 Alle PHP Scripte anzeigen

Alle Zeitangaben in WEZ +2. Es ist jetzt 13:43 Uhr.