MySQL: Dijkstra's "kürzester Pfad"

[omata]

Zitat:

Zitat von rollstuhlfahrer (Beitrag 1099243)

Zitat:

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:

Zitat von Memnarch (Beitrag 1099237)

@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. :gruebel:

[FredlFesl]

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