Input:
- G=(V,E) Graph, V is the set of Nodes, E is the set of edges, whereas v in V is one single node and (x,y) in E is an edge between nodes x and y (in V).
- w(x,y) in Q+ the edge weights (ie: a value calculated from the distance of x and y and the max speed), Q+ is the set of positive rational numbers.
- s in V: the start node
- z in V: destination node
variables:
- d(v) for v in V is the distance of v from s (ie the sum of the w(x,y) for every edge you have to go from s to v)
- p(v) for v in V is the predecessor of v in the current shortest path (ie where you come from)
- Q: a priority queue of the nodes, priority function is the distance d(v), enqueuing a node causes it to be sorted into the queue so the node with the smallest d(v) is the first and the one with the biggest d(v) is the last element, dequeuing will give you the v with the lowest d(v), and if d(v) of a node changes, the queue will be re-sorted
- S: a stack
Code: Select all
Set d(s) to 0, Set p(s) to NULL
for all (v in V, v!=s) set d(v)=infinity (or a really big value never appearing in the game) and set p(v) to NULL
enqueue s in Q
while Q is not empty
dequeue x from Q (is the node with the lowest d)
for all (y where (x,y) in E)
if d(x)+w(x,y)<d(y) then
set p(y) to x
set d(y) to d(x)+w(x,y)
if y not in Q then
enqueue y
else
re-sort Q
end if
end if
end for
end while
set y to z
while y not NULL
push y to S
set y to p(y)
end while
return S
The edge weights can be given dynamically: every piece of track has a maximum speed depending on bridge type and curve radius. Plus, every train has a max speed. So, if a train has calculated a route with the above algorithm, it could temporarily set the max speed of all track pieces with a faster max speed than the train's to the max speed of the train. You would then achieve the following:
You have two tracks from city A to city B. You let a mail train haul mail from A to B, the mail train has a max speed of 120 km/h. And the same time, a high speed passenger train departs from A heading for B. Let's say, the slow train departs first and takes track 1 which is a bit shorter than track 2. In Locomotion, the fast passenger train would also choose the shorter track 1 although it is actually faster on track 2 due to its faster speed 'cause it doesn't have to wait for the slow train. With this algorithm above the slow train would set the max speed of all tracks to 120km/h and thus increase the edge weights on track 1 so the edge weights on track 2 will be smaller and the high speed train will take the slightly longer track 2.
To optimize it a bit (Dijkstra can get very very long paths while calculating, ie if you want to calculate the shortest track from Halle to Leipzig (it is approx. 30 km) Dijkstra could temporarily get a path going via Paris and Rome and shorten it with every new run), you could first do a modified depth-first-search beginning from node s and with depth 1 and increasing the depth until the "Aufspannender Teilgraph" (don't know this in English) contains the destination node. Then you only have to do a Dijkstra in this part of the graph which would be WAY faster. You could store this graph in every train so you don't have to recalculate it every time. You only need to recalculate it if you change your track layout or the route of the train/bus/etc.
It was just an idea I had.
)