all-pair-shortest-path

Hallo NG!

Ich möchte auf eine Community-Seite die Verbindungen zweier Benutzer
über die Freundeslisten anderer Benutzer anzeigen.

Angenommen ich betrachte das Profil von Benutzer D, ich selbst bin
Benutzer A. Die verbindung könnte dann so aussehen:


A -> B -> C -> D

A (ich) kenne B
B kennt C
C kennt D (Ziel)


Ich weiß durch Google bereits, dass das Problem als
"all-pair-shortest-path" bezeichnet wird und es existieren dafür bereits
diverse Lösungsansätze. Da diese aber in der Regel in mir fremden
Programmiersprachen geschrieben und mit Zugrundelegung komplizierter
Mathematik gespickt sind, komme ich da ohne Hilfe nicht weiter.

Quellen zur Problemlösunghabe ich auch schon einige Zusammengetragen:

http://de.wikipedia.org/wiki/A*
http://de.wikipedia.org/wiki/Algorithmus_von_Dijkstra
http://de.wikipedia.org/wiki/Algorithmus_von_Floyd_und_Warsh all


Ist das vielleicht alles komplizierter beschrieben als es in
Wirklichkeit ist und gibt es dafür schon fertige Lösungen? Kann mir
vielleicht einfach jemand auf die Sprünge helfen damit?


Danke für Hilfe!
Habbo

Re: all-pair-shortest-path

Jan Habbo Brüning schrieb:

> Ist das vielleicht alles komplizierter beschrieben [...]?

Nein, das ist wirklich so kompliziert.

Grüße, Matthias

--
http://www.trullala.de
--
Der Trend geht ganz eindeutig zur Zweitsignatur.

Re: all-pair-shortest-path

Jan Habbo Brüning schrieb:

> http://de.wikipedia.org/wiki/Algorithmus_von_Dijkstra

> Ist das vielleicht alles komplizierter beschrieben als es in
> Wirklichkeit ist und gibt es dafür schon fertige Lösungen?

Kompliziert isses auf jeden fall. Fertige Php-Implementierungen kenn ich
keine. Aber ne gut verständliche Erklärung für Dijkstra gibts hier:

http://mandalex.manderby.com/d/dijkstra.php?id=93

Evtl. hilfts ja.

MfG, Ulf

Re: all-pair-shortest-path

Ulf Kadner schrieb:

> http://mandalex.manderby.com/d/dijkstra.php?id=93

Noch nen Paar:
http://dsor.upb.de/vawi/11_kuerzeste_wege/
http://www.uni-stuttgart.de/iv-kib/generic/download/lehre/ei nfuehrung/ws00_01/vorlesung/mb_dijkstra.pdf

MfG, Ulf

Re: all-pair-shortest-path

Vielen Dank erstmal für die weiteren Links.

Sehe ich das denn richtig, dass die Lösung dieses Problemes auf jeden
Fall viele Datenbankabfragen erfordern wird? Es ist ja nicht ganz
unproblematisch, wenn beim Aufruf des Benutzerprofiles zusätzlich zu den
übrigen Abfragen alleine für die Darstellung der Verbindung zu dem
Benutzer ein dutzend Queries abgeschossen werden ...


Gruß,
Habbo

Re: all-pair-shortest-path

Jan Habbo Brüning wrote:
[snip]

Hättest Du nicht Off-Topic gepostet und ein wenig gegoogled, hättest
Du gesehen, dass ich vor einem Monat ähnliche Probleme hatte.

Da ich kein Mathefreak bin, habe ich mich ein paar Tage in die
Materie eingelesen und hatte innerhalb von zwei Wochen eine
komplett fertige Implementierung von Dijkstra und Floyd-Warshall.

Sobald ich das Zeugs fertig habe, werde ich es als OpenSource
für die breite Masse zur Verfügung stellen.

Wenn Du noch Fragen hast, schick' mir eine kurze Mail.

Re: all-pair-shortest-path

Matthias P. Wuerfl wrote:
> Nein, das ist wirklich so kompliziert.

Ist es eigentlich nicht. Ich finde, die Schreibweise ist kompliziert,
aber das hat die Mathematik so ansich.

Von der Logik her sind die Algorithmen sehr gut nachvollziehbar
und wenn man sie in "Klartext" übersetzt, kann man gut damit
arbeiten.

Re: all-pair-shortest-path

Ulf Kadner wrote:
> http://www.uni-stuttgart.de/iv-kib/generic/download/lehre/ei nfuehrung/ws00_01/vorlesung/mb_dijkstra.pdf

Super, den kannte ich noch nicht! Danke.

Re: all-pair-shortest-path

Jan Habbo Brüning wrote:
> Sehe ich das denn richtig, dass die Lösung dieses Problemes auf jeden
> Fall viele Datenbankabfragen erfordern wird? Es ist ja nicht ganz
> unproblematisch, wenn beim Aufruf des Benutzerprofiles zusätzlich zu
> den übrigen Abfragen alleine für die Darstellung der Verbindung zu dem
> Benutzer ein dutzend Queries abgeschossen werden ...

Klar, jede Kante und jeder Knoten wird angefragt.

Ich habe 6.500 Knoten mit ca. 13.000 Kanten. Die Rechenzeit von einem
Ausgangsknoten zu allen 6.500 Knoten dauert genau 13 Sekunden in
PHP5 (Windows XP, ca. 3 GHz) - Dijkstra-Implementierung natürlich.
Floyd-Warshall wird sicher länger dauern.

Re: all-pair-shortest-path

Tobias Wendorff schrieb:
> Jan Habbo Brüning wrote:
>
> Klar, jede Kante und jeder Knoten wird angefragt.
>
> Ich habe 6.500 Knoten mit ca. 13.000 Kanten. Die Rechenzeit von einem
> Ausgangsknoten zu allen 6.500 Knoten dauert genau 13 Sekunden in
> PHP5 (Windows XP, ca. 3 GHz) - Dijkstra-Implementierung natürlich.
> Floyd-Warshall wird sicher länger dauern.

Die Algorithmen sind in der O(n^3) Region angesiedelt (der komplexe A*
hat O(n log n + m), aber nur bei sehr guter Implementierung), also
ziemlich aufwändig. Hierbei noch ständig auf der DB rumzurödeln wäre
wohl Selbstmord. Das ist 1. eine interessante Optimierungsaufgabe
hinsichtlich der Minimierung nötiger DB-Zugriffe und 2. ein Kandidat für
Datenreduktion und komplette In-Memory-Bearbeitung.

OLLi

--
"We gotta move fast."
"Ya, he might come back and hug us in the act."
[firefly 11]

Re: all-pair-shortest-path

Oliver Grätz wrote:
> Die Algorithmen sind in der O(n^3) Region angesiedelt (der komplexe A*
> hat O(n log n + m), aber nur bei sehr guter Implementierung), also
> ziemlich aufwändig.

Nach über einem Monat Analyse und Texte-Lesen habe ich herausgefunden,
dass sich der A* nur seeehr bedingt für die Lösung im Verkehr eignet.
Manchmal sind Umwege die schnellere Variante.

> Hierbei noch ständig auf der DB rumzurödeln wäre wohl Selbstmord.
> Das ist 1. eine interessante Optimierungsaufgabe hinsichtlich der
> Minimierung nötiger DB-Zugriffe und 2. ein Kandidat für
> Datenreduktion und komplette In-Memory-Bearbeitung.

Das sind Dinge, mit denen ich mich als Raumplaner leider nur sehr
wenig beschäftige :-(