Pathfinding - Kontakte über mehrere Ecken

[Martin Berg]

Hallo,

in unserer Community kann jedes Mitglied persönliche Kontakte besitzen.

Gerne würden wir ein Feature einbauen, mit dessen Hilfe sich jedes Mitglied darstellen lassen kann, über welche seiner persönlichen Kontakte er ihm bisher ihm unbekannte doch kennt.

Nicht so einfach der Satz, deswegen versuche ich es mal ein wenig konkreter an einem Beispiel zu erläutern:

Mitglied A kennt Mitglied B
Mitglied B kennt Mitglied C
Mitglied C kennt Mitglied D

So nun kennt A demnach auch D, nur nicht direkt sondern
A->B->C->D

D ist für A also ein Kontakt dritten Grades.

Auf http://www.openbc.com ist so ein Feature sehr schön zu sehen.

Wie kann ich sowas realisieren? Ich denke mal die Stichworte sind "Pathfinding" und evtl. "Dijkstra". Leider bin ich hier noch nicht so weit gekommen und hoffe hier im Forum Hilfe zu finden.

Eckdaten:
- PHP
- Tabelle mitglieder unteranderem mit Feld "mitglieds_id"
- Tabelle kontakte mit dem Feld "mitglieds_id", "kontakt_mitglieds_id"

Ich freue mich auf Antworten.

Viele Grüße aus Düsseldorf
Martin Berg

[Daniel W.]

funktion zum Kontakte auslesen, die sich selber aufruft, würd ich sagen<br><br>entwurf:<br><i>
funk Kontakt(str)<br>
{while (Kontakte da){<br>
Kontakt linken oder was auch immer;<br>
funk Kontakt(gefundener Kontakt);<br>
}}</i><br>Das hat dann kein ende...(angenommen jeder kennt wen)<br>erster aufruf: <i>funk Kontakt(user selber);</i><br><br>so würd ichs machen, hab aber auch noch nie von "Pathfinding" und "Dijkstra" gehört..

[Martin Berg]

Dies ist natürlich die "einfache" Lösung, die aber mit Sicherheit viel zu rechenlastig ist.

Kennt sich niemand mit "Dikstra" oder "AStern" aus? Das sind/sollen sein Algorithmen, mit denen ich angeblich dieses Problem lösen kann.

Viele Grüße
Marti