effektiver Algorithmus? (Kürzester Weg auf Graph)
- Ersteller Moritz K
- Erstellt am
Alain Aubert
Legendäres Mitglied
Ist mir noch was in den Sinn gekommen wg. Dijkstra weil Gewichtung und so. Man könnte die Anzahl der Kontakte eines Knotes als eine Wahrscheinlichkeitsfunktion auffassen und das als Gewichtung verwenden. Allerdings ist nicht ganz sauber und ich glaube nicht, dass es sehr gut performt für Mitglieder >> durchschnittliche Kontakte (die Regel!
.
A Propos Java. Vgl. Touchgraph. Und es gibt sehr viele Implementationen von Bäumen.
Floyd ist wie Dijkstra für gewichtete Bäume.
Letzt Frage wurde oben schon erklärt. Hier bei Ayom habe ich folgendes: (die Buddy Funktion, die sehr schwach genutzt wird)
member (table)
-id
contacts (table)
-id
-member id
-contact id
D.h. es ist ein gerichteter Graph, weil ich Dich ins Kontaktbuch aufnehmen kann, ohne dass Du mich im Kontaktbuch hast, ohne dass Du zustimmen musst. In diesem Falle stellt sich bei der Suche des kürzesten Weges die Frage ob man Wege auch gegen ihre Richtugn ablaufen kann.
Wenn man nur bestätigte Kontakte hat, liegt ein ungerichter Graph vor. Dann kann man sich überlegen, ob man aus Performancegründen redundanten Content in der DB ablegt, nötig ist es allerdings nicht (wenn der Algo den Datentyp versteht).
.A Propos Java. Vgl. Touchgraph. Und es gibt sehr viele Implementationen von Bäumen.
Floyd ist wie Dijkstra für gewichtete Bäume.
Letzt Frage wurde oben schon erklärt. Hier bei Ayom habe ich folgendes: (die Buddy Funktion, die sehr schwach genutzt wird)
member (table)
-id
contacts (table)
-id
-member id
-contact id
D.h. es ist ein gerichteter Graph, weil ich Dich ins Kontaktbuch aufnehmen kann, ohne dass Du mich im Kontaktbuch hast, ohne dass Du zustimmen musst. In diesem Falle stellt sich bei der Suche des kürzesten Weges die Frage ob man Wege auch gegen ihre Richtugn ablaufen kann.
Wenn man nur bestätigte Kontakte hat, liegt ein ungerichter Graph vor. Dann kann man sich überlegen, ob man aus Performancegründen redundanten Content in der DB ablegt, nötig ist es allerdings nicht (wenn der Algo den Datentyp versteht).