MySQL: Dijkstra's "kürzester Pfad"

[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

[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...