3

I know Dijkstra's algorithm is a popular solution for the "shortest path" problem, however it seems to be backfiring when implementing time tables.

Say I have this graph with the following weights (time to get from one point to another):

A-----C     A->C: 10
\--B--/     A->B: 5
            B->C: 5

If you throw it into Dijkstra, it'll return route A->C. That's fine until you refer to a timetable that says route A->C only exists within a certain time frame. You could easily remove the A->C edge if the requested time frame falls outside the range when that edge is used. But obviously the data set I'm working with has a bunch of other ways to get from A->C with other, higher, costs. Not to mention what if you want to get from Z->Y which requires going from A->C in the middle. It doesn't seem like an ideal solution.

Is there a better way, other than Dijkstra, to create a shortest path while also keeping a timetable in mind? Or should the algorithm be modified to consider two weights when finding the optimal path?

If it matters, I'm using python.

[edit]

The time table is a basic table that says a train (in my case) leaves from point A at (say) 12:00 and leaves from station B at 12:05 then leaves from C at 12:10. When it doesn't stop at B, its column is empty and A will have 08:00 and C will have 08:10 

A       B        C
800            8:10
12:00  12:05  12:10
SarTheFirst
  • 350
  • 1
  • 11
  • 1
    What is the timetable in your case? Is it the weight of the path? because if that's the case then Dijkstra should work properly. – MooingRawr Feb 28 '18 at 14:34
  • 2
    It sounds like you should re-evaluate your graph and remove no-longer-existing edges at every step, during your shortest route calculation. – Shark Feb 28 '18 at 14:36
  • @MooingRawr The time table is a basic table that says a train (in my case) leaves from point A at (say) 12:00 and leaves from station B at 12:05 then leaves from C at 12:10. When it doesn't stop at B, its column is empty and A will have 08:00 and C will have 08:10 – SarTheFirst Feb 28 '18 at 14:37
  • 1
    So like Shark says, if you have a dynamic path changing system, you need to either a/ remove the path that is invalid (either on a time base system or a step base system), or b/ set the path's weight SUPER costly when it's out of time zone or c/ modify Dijkstra's algorithm to not just check the weight of the path, but the availability of the path based on the time. Without code (MCVE'd) we can't really help you much. Personally I would go with step C, since you don't need to modify the map, but it will cost you an extra calculation... – MooingRawr Feb 28 '18 at 14:43
  • 1
    At each step, update the distance to be the sum of travel time + wait time, where wait time is determined by (cumulative time traveled up to that point) mod (time between departures)? Would also have to take into account some offset if departures don't all start exactly at 12:00 – caw5cv Feb 28 '18 at 14:52
  • Perhaps it could help to think of missing edges as edges with infinite weight in a weighted graph. – mehdix Feb 28 '18 at 15:12
  • A different way to look at what @MooingRawr and Shark wrote: think of time-dependent cost. Cost does not have to be fixed: it can vary dependent on the time-table. You can set infinite cost when an edge is not available. – c0der Mar 02 '18 at 07:32

1 Answers1

0

One way could be creating a set of trees that denotes all simple paths between to given nodes and just selecting the shortest one among those that are not contain a deprecated edge. You can find all paths by adapting Dijkstra's algorithm or another algorithm like DFS or BFS. Also finding all paths between two nodes is considered to be a hard problem but based on your need and the type of graphs that you're dealing with you can create what you want. You can also read this post regarding this matter. -> Find all paths between two graph nodes. i.e you can have a limited set of paths (if using Dijkstra top N shortest).

Now for Optimizing this step so that find out if an edge is deprecated or not I suggest to have a dictionary of all edge ids or names as keys and their deprecation timestamp as value then filter the dictionary by comparing the values with now().timestamp() and after each find just remove the items from dictionary. Also note that before you start filtering you should check if the edge exist in dictionary or not (in order to prevent the lagorithm to run the filtering multiple times for duplicate edges).

The code should be like following:

def filter_edge(u_id):
    if edge in deprecation:
        time_stamp = deprecation[u_id]
        if time_stamp > datetime.now().timestamp():
            return True
    return False

And the path validation is something like following:

def validate_path(path):
    return not any(filter_edge(edge.id) for edge in path)
Mazdak
  • 105,000
  • 18
  • 159
  • 188