Entwicklung einer Fahrplanauskunft

[Namenloser]

Zitat von BUG:

Zitat von NamenLozer:

Das, was jfheins gesagt hat, und vielleicht hilft es, wenn du dir bewusst machst, dass Zeit auch eine Dimension ist. Das heißt, eigentlich suchst du eine Route durch eine dreidimensionale (wenn deine Karte zweidimensional ist, wovon ich ausgehe) Punktwolke (die sich als Graph darstellen lässt).

Das Ganze kann man vereinfachen. Die Position der Haltestellen ist eigentlich egal, nur die Zeit (und evtl. der Preis) zwischen den Stationen ist interessant.

Ja, das ist schon richtig, am Ende hat man natürlich einfach einen Graphen mit Kantengewichten. Ich persönlich finde es bloß anschaulicher, wenn man sich vorstellt, dass man kürzeste Wege auf einer zweidimensionalen Karte berechnet und die Kosten zwischen zwei Knoten der geometrischen Distanz entsprechen. In der Praxis muss natürlich der geometrisch kürzeste Weg nicht der schnellste sein, da man z.B. auf der Autobahn schneller fahren kann als auf irgendeiner Landstraße, aber ich finde, wenn man das Prinzip erst mal verstanden hat, kann man es sehr leicht verallgemeinern...

Edit:

Zitat von BUG:

Auch wenn die oben definierte Graphen theoretisch unendlich sind (angenommen die Zeit endet nicht), kann man praktisch annehmen, das niemand mehr als drei Tage auf einer Strecke fährt und damit die Anzahl der Knoten auf gut handhabbare Größen begrenzen

Das ist eigentlich gar nicht nötig, es reicht ja, wenn die Knoten „virtuell“ vorhanden sind. Dijkstra guckt sich ja immer nur die unmittelbar adjazenten Knoten an. Man kann diese also generieren, während man den Algorithmus ausführt...

Man muss nur aufpassen, dass es zwischen dem Start- und dem Ziel-Knoten auch wirklich eine Verbindung gibt... sonst würde man in eine Endlosschleife laufen.