CODEWITHSUNDEEP
algorithmgraph-algorithm
Subhajit Kundu
Subhajit Kundu

Reputation: 403

Shortest journey time from source to destination

Consider a list of stations, say 10 stations, 'A' to 'J', connected by trains running between them.

In terms of graph, consider the stations (Vertices) and trains running between them (Edges) to form a connected graph but not complete, i.e. each station is reachable from any station either directly or via other stations by making hops. Most importantly, these hops includes waits between arrival and next departure. Quite understandably, the journey time between two connected stations is independent. However, the waiting time to next departure depends where you arrived from.

NOTE: I mention graph only to aid understanding. One could think beyond it.

Problem: Given any two stations and start time from the initial station, how to find shortest time to the destination, counting the waiting time between arrival and departure in cases of hops? And what DS will be used for the same? Assume that if two stations are connected by a train, then only-and-only one train is running between them.

Upvotes: 2

Views: 848

Answers (1)

libik
libik

Reputation: 23029

IMHO Dijkstra should be enough after all.

If you run Dijkstra from node "A", it finds shortest path to all other nodes.

Even when we have "hops", the worst case is that you get to some station earlier and then you have to wait to the same train as if you get there later with some other route.

The only difference is, that you count price as "time of waiting + time of travel" instead of only "time of travel"

This behaviour is caused by trains having real "arrival/departure".

If each route for every A2 node in every node combination A1 -> A2 -> A3 get random penalization for going from A1 to A3 through A2, then it would be unpredictable I think.

Upvotes: 0

Related Questions