Re: Bus/train timetable search algorithm
- From: John Slimick <slimick@xxxxxxxxxxxxxxxxxxxx>
- Date: Fri, 7 Nov 2008 21:18:08 +0000 (UTC)
If you add dummy edges at the intermediate stages with weights of the
expected layovers, Dijkstra's algorithm should work.
For example, one could route from New Orleans to Minneapolis
vi Chicago as (with guessed-at times):
New Orleans --- 12 hrs --- Chi1 -- 4 hrs -- Chi2 -- 4 hrs -- Minn
Chi1 and Ch2 are two nodes representing Union Station arrival and
departure respectively.
john slimick
slimick@xxxxxxxx
======================================================================
On 2008-11-06, adamwatson@xxxxxxxxxxxxx <adamwatson@xxxxxxxxxxxxx> wrote:
Does anyone know of public transport routing algorithms that use a.
timetable and include changing between services?
A breadth first search is easy to implement for small datasets and a
limited number of interchanges, but rapidly becomes unmanageable.
Something like Dijkstra's algorithm isn't obviously applicable because
the quickest route does not necessarily comprise of the quickest
intermediate stages.
I'm left with a depth first exhaustive search, but I feel there must
be a better way.
- References:
- Bus/train timetable search algorithm
- From: adamwatson
- Bus/train timetable search algorithm
- Prev by Date: Re: huffman coding
- Next by Date: Re: LL(1) Parser - methods for accessing token stream
- Previous by thread: Bus/train timetable search algorithm
- Next by thread: Re: Bus/train timetable search algorithm
- Index(es):
Relevant Pages
|
Loading
