MySQL: Dijkstra's "kürzester Pfad"

[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

[alcaeus]

Hinweis: es gibt mit FlockDB von Twitter eine auf MySQL basierende Graph-Datenbank, welche genau fuer solche Dinge geschrieben wurde. Ich bin nur letztens zufaellig drueber gestossen und dachte mir ich erwaehns mal

Den Algorithmus finde ich trotzdem.....interessant

Greetz
alcaeus