MySQL: Dijkstra's "kürzester Pfad"

[omata]

Die Idee war eigentlich eine andere...

Wenn ich ein sehr großes Netz in einer Datenbank gespeichert habe und dann eine Berechnung auf den Daten ausführen möchte, dann müsste ich erst alle Daten in eine eigene Datenstruktur aus der DB laden, oder ich mache während der Algoirithmus läuft viele einzelene SQL-Abfragen. Das heißt, der Datenverkehr zwischen Client-Anwendung und Datenbank ist sehr hoch. Deshalb diese Idee, dort bleiben die Daten in der DB und es findet auch kein großer Datenverkehr statt.

Vielleicht ist mein Aufruf-Beispiel auch unverständlich:
-> Ist das Netz erstellt, ist nur die Resolve-Zeile nötig.

Naja, vielleicht ist das auch alles bödsinn.
Vergesst einfach diesen Beitrag, sorry fürs posten und Speicher verbrauchen.

[patti]

Zitat von omata:

Naja, vielleicht ist das auch alles bödsinn.
Vergesst einfach diesen Beitrag, sorry fürs posten und Speicher verbrauchen.

Ganz im Gegenteil! Ich finde die Umsetzung sehr interessant und wer weiß - vielleicht kann man sowas ja mal brauchen

[FredlFesl]

Das ist der 'Single-Pair-Shortest-Path' Algorithmus, richtig?
Lustig wäre auch der 'All-Pair-Shortest-Path' Algorithmus, der nur unwesentlich komplexer ist, wenn ich mich recht erinnere...

Ist trotzdem schon lustic, was man mit SQL (=Mengenlehre) so alles anstellen kann.

[Memnarch]

@Omata: Ich wollte deine Arbeit in keinster Weise schmälern. Brauchte nur nen Denkanstoss

@FredlFesel: Was ist all-pair-shortest-path? Die beiden begriffe single und all pair waren mir noch nicht begegnet o.O


MFG
Memnarch

[FredlFesl]

Zitat von Memnarch:

@FredlFesel: Was ist all-pair-shortest-path? Die beiden begriffe single und all pair waren mir noch nicht begegnet o.O

Single-Pair Shortest Path= Finde kürzesten Weg für ein Paar (Anfangspunkt, Endpunkt)
All-Pair Shortest Path = Finde die kürzesten Weg zwischen allen Punkte im Graph.

Man kann sich das Wissen, das man bei der Suche nach einem kürzesten Weg für das Finden anderer kürzester Wege zu Nutze machen.

[himitsu]

Der Kürzeste Weg zwischen allen Punkten ist doch eigentlich nur der, wo der kleineste Wert angegeben wurde?
(wenn's keine negativen Entfernungen gibt)

a>b wäre also die Lösung und dafür braucht man doch keine großen Berehnungen.
Drum versteh ich jetzt nicht so ganz, weswegen man für All-Pair Shortest Path den "aufwändigen" Single-Pair Shortest Path erweitern sollte,
wo doch ein einfaches "gib mir Row, mit kleinstem Wert"-Select ausreichen würde.

[FredlFesl]

Nun sind ja nicht alle Punkte im Graphen miteinander verbunden...

[s.h.a.r.k]

Zitat von patti:

Zitat von omata:

Naja, vielleicht ist das auch alles bödsinn.
Vergesst einfach diesen Beitrag, sorry fürs posten und Speicher verbrauchen.

Ganz im Gegenteil! Ich finde die Umsetzung sehr interessant und wer weiß - vielleicht kann man sowas ja mal brauchen

Also mir ist in dem Zusammenhang gleich das Thema Mobile Devices eingefallen. Selbst in SmartPhones stecken keine Hochleistungsrechner und von dem her finde ich den Ansatz echt klasse, da so halt der Server rechnen muss und nicht der Client. Kommt natürlich immer auf das Einsatzgebiet an, aber sowas kann sich durchaus lohnen.

[rollstuhlfahrer]

Wenn ich im PhpMyAdmin das ausführe (SQL Block 1, SQL Block 2 und dann SQL Block 3 hintereinander), dann bekomme ich im letzten Block einen Fehler:

Zitat von MySQL Fehler:

#2014 - Commands out of sync; you can't run this command now
CALL procResolve('a', 'i')

Wenn ich dann die letzte Anweisung (bei der er meckert) nochmal ausführe, dann klappts. Liegt das jetzt an mir oder am Server?

Bernhard

[omata]

Zitat von rollstuhlfahrer:

Zitat von MySQL Fehler:

#2014 - Commands out of sync; you can't run this command now

Dir MySQL-Dokumentation sagt dazu folgendes: klick

Das hier ist auch ganz interessant: klick