Dijkstra mit vielen Knoten?

Und was den Speicher angeht kommt es natürlich darauf an, was Du nun eigentlich vor hast. Wenn Du für jeden Knoten den kürzesten Pfad zu jedem anderen Knoten abspeichern willst, dann brauchst du halt schonmal N²/2 einträge, in denen Du eben die länge der kürzesten Pfade abspeicherst. Wenn Du auch gleich noch direkt den kürzesten Pfad zur Verfügung haben willst, wirds eben noch mehr.
Leider hast Du uns gar nicht gesagt, was Du tun möchtest, außer dass Du dafür gerne Dijkstra verwenden würdest.

junta

decimad schrieb:

Leider hast Du uns gar nicht gesagt, was Du tun möchtest, außer dass Du dafür gerne Dijkstra verwenden würdest.

Naja, mit dieser Graph Klasse (https://github.com/kay/PHP-Dijkstra) geht das schon ganz gut:

$dj = new Graph();

$dj->addEdge('Rome','Paris',2);
$dj->addEdge('Rome','London',3);
$dj->addEdge('Rome','Amsterdam',3);
$dj->addEdge('Paris','Paris',1);
$dj->addEdge('Paris','London',1);
$dj->addEdge('London','New York',10);
$dj->addEdge('Amsterdam','Los Angeles',8);
$dj->addEdge('Los Angeles','Tokio',2);
$dj->addEdge('New York','Tokio',3);

print_r($dj->getPath('Rome','Tokio'));

Was braucht ihr noch für Informationen, oder ist das einfach für PHP untypisch

Na was Du für ein Problem lösen möchtest (falls es mit der Bib nicht schon gelöst ist, dann wäre alles weitere ja Zeitverschwendung). Was Du jetzt als Beispiel angibst, sieht danach aus, dass Du Dir auch A* mal anschauen wollen würdest. Aber wir wissen halt nicht, ob Du nun nur den kürzesten Pfad zwischen A und B suchst, oder die kürzersten Pfade von A zu allen anderen, oder aber die kürzesten Pfade von allen Knoten zu allen Anderen. Das alles hat Auswirkungen darauf, wie lange es dauert und wieviel Speicher benötigt wird.
Alleine dass Du Dijkstra verwenden möchtest sagt halt noch nicht so viel aus.

junta

decimad schrieb:

Na was Du für ein Problem lösen möchtest (falls es mit der Bib nicht schon gelöst ist, dann wäre alles weitere ja Zeitverschwendung).

Bau es mal ein, dann sag ich bescheid ob es langsam ist.

decimad schrieb:

Aber wir wissen halt nicht, ob Du nun nur den kürzesten Pfad zwischen A und B suchst, oder die kürzersten Pfade von A zu allen anderen, oder aber die kürzesten Pfade von allen Knoten zu allen Anderen. Das alles hat Auswirkungen darauf, wie lange es dauert und wieviel Speicher benötigt wird.
Alleine dass Du Dijkstra verwenden möchtest sagt halt noch nicht so viel aus.

Für eine Berechnung nur den kürzesten Pfad zwischen A und B. Aber wenn das Teil länger läuft könnten durchaus die kürzesten Pfade von allen Knoten zu allen Anderen gesucht werden, was aber äußerst unwahrscheinlich ist.

Denk es gibt eher von diesen 1-5k Knoten 2-20 die regelmäßig abgefragt werden. Die anderen sind dann eher Exoten und würd ich nur ungern im Speicher halten.

junta

Wird es leichter/schneller wenn die Kanten kein Gewicht haben

Naja, wenn der Graph konstant ist, und das eine Server-App ist und soviele Zugriffe stattfinden, dass der Energieverbrauch oder die Auslastung eine Rolle spielen, dann würde es vielleicht Sinn ergeben, eine Art Cache über den Suchalgorithmus zu ziehen, der halt den zu Verfügung stehenden Speicher ausnutzt, falls nicht sowieso die Kombination von allem was Du brauchst in den Speicher passt. Kommt dann halt auf die Abfragemuster an. Da geht's dann in's eingemachte und es gibt bestimmt viel Forschungsarbeit zu durchforsten.

PS: Ich find's gut, wie man hier das kleine Einmaleins auffrischen kann!

Wenn die Kanten keine Gewichte bzw. alle dieselben haben, dann degeneriert Dijkstra zur Breadth-First-Suche an.
Der Container, der dir hilft, die nächsten Knoten zu generieren/verwalten wird wesentlich einfacher und natürlich sparst Du Dir eben den Speicher der Gewichte pro Kante, hehe. Auf Wikipedia ist das aber alles gut ziemlich gut zusammengefassst, btw. und mit Google-Suchen findet man davon ausgehend dann die interessantesten Dinge.

Jester

Ohne Gewichte gehts in linearer Zeit mittels Breitensuche. Für die paar Knoten sollte das übrigens alles mit vertretbarem aufwand gehen. Erst ab ein paar Millionen wirds irgendwann wirklich langsamer. Darf ich fragen um was für einen Graph es sich handelt -- je nachdem gibt es nämlich ziemlich viele verschiedene Möglichkeiten zur Beschleunigung.

junta

decimad schrieb:

Naja, wenn der Graph konstant ist, und das eine Server-App ist und soviele Zugriffe stattfinden, dass der Energieverbrauch oder die Auslastung eine Rolle spielen, dann würde es vielleicht Sinn ergeben, eine Art Cache über den Suchalgorithmus zu ziehen.

Ja, wenn ich mal mehr als einen Besucher hab... Da der Graph aber nur von einem Cronjob genutzt wird, ist super Performance nicht unbedingt notwendig.

Jester schrieb:

Darf ich fragen um was für einen Graph es sich handelt -- je nachdem gibt es nämlich ziemlich viele verschiedene Möglichkeiten zur Beschleunigung.

Kenn mich da nicht aus, bin eh froh, dass mir der Dijkstra eingefallen ist

Ich würde sagen es müsste ein auf einen einfachen Graph reduzierter Multigraph sein

Jester

Klar, man kann immer auf einfache Graphen reduzieren. Ich möchte wissen wo der Graph herkommt und was er für strukturelle Eigenschaften hat. Für Straßennetze und Graphen mit vergleichbaren Eigenschaften gibt es zum beispiel viele Verbesserungen.