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. |
 |

16-09-2014, 23:00
|
narutos
Registrierter Benutzer
|
|
Registriert seit: Sep 2014
Beiträge: 23
|
|
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.
|

16-09-2014, 23:01
|
narutos
Registrierter Benutzer
|
|
Registriert seit: Sep 2014
Beiträge: 23
|
|
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; } }
|

16-09-2014, 23:01
|
narutos
Registrierter Benutzer
|
|
Registriert seit: Sep 2014
Beiträge: 23
|
|
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; } }
|

16-09-2014, 23:02
|
narutos
Registrierter Benutzer
|
|
Registriert seit: Sep 2014
Beiträge: 23
|
|
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; } }
|

16-09-2014, 23:03
|
narutos
Registrierter Benutzer
|
|
Registriert seit: Sep 2014
Beiträge: 23
|
|
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); } }
|

16-09-2014, 23:04
|
narutos
Registrierter Benutzer
|
|
Registriert seit: Sep 2014
Beiträge: 23
|
|
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.
|

16-09-2014, 23:05
|
narutos
Registrierter Benutzer
|
|
Registriert seit: Sep 2014
Beiträge: 23
|
|
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.
|
Aktive Benutzer in diesem Thema: 1 (Registrierte Benutzer: 0, Gäste: 1)
|
|
Themen-Optionen |
|
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.
HTML-Code ist aus.
|
|
|
|
PHP News
|