Tweet
/**
* 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;
}
}
/**
* 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;
}
}
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;
}
}
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);
}
}
// 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.
Kommentar