Graph Shortest Paths w/Dynamic Weights (Repeated Dijkstra? Distance Vector Routing Algorithm?) in R / Python / Matlab

Question

I have a graph of a road network with avg. traffic speed measures that change throughout the day. Nodes are locations on a road, and edges connect different locations on the same road or intersections between 2 roads. I need an algorithm that solves the shortest travel time path between any two nodes given a start time.

Clearly, the graph has dynamic weights, as the travel time for an edge i is a function of the speed of traffic at this edge, which depends on how long your path takes to reach edge i.

I have implemented Dijkstra's algorithm with edge weights = (edge_distance / edge_speed_at_start_time) but this ignores that edge speed changes over time.

My questions are:

1. Is there a heuristic way to use repeated calls to Dijkstra's algorithm to approximate the true solution?

2. I believe the 'Distance Vector Routing Algorithm' is the proper way to solve such a problem. Is there a way to use the Igraph library or another library in R, Python, or Matlab to implement this algorithm?

EDIT I am currently using Igraph in R. The graph is an igraph object. The igraph object was created using the igraph command graph.data.frame(Edges), where Edges looks like this (but with many more rows):

I also have a matrix of the speed (in MPH) of every edge for each time, which looks like this (except with many more rows and columns):

Since I want to find shortest travel time paths, then the weights for a given edge are edge_distance / edge_speed. But edge_speed changes depending on time (i.e. how long you've already driven on this path). The graph has 7048 nodes and 7572 edges (so it's pretty sparse).

Answer 1

There exists an exact algorithm that solves this problem! It is called time-dependent Dijkstra (TDD) and runs about as fast as Dijkstra itself.

Unfortunately, as far as I know, neither igraph nor NetworkX have implemented this algorithm so you will have to do some coding yourself.

Luckily, you can implement it yourself! You need to adapt Dijkstra in single place. In normal Dijkstra you assign the weight as follows: With dist your current distance matrix, u the node you are considering and v its neighbor.

alt = dist[u] + travel_time(u, v)

In time-dependent Dijkstra we get the following:

current_time = start_time + dist[u]
cost = weight(u, v, current_time)
alt = dist[u] + cost

TDD Dijkstra was described by Stuart E. Dreyfus. An appraisal of some shortest-path algorithms. Operations Research, 17(3):395–412, 1969

Currently, much faster heuristics are already in use. They can be found with the search term: 'Time dependent routing'.

Answer 2

What about igraph package in R? You can try get.shortest.paths or get.all.shortest.paths function.

library(igraph)
?get.all.shortest.paths
get.shortest.paths()
get.all.shortest.paths()# if weights are NULL then it will use Dijkstra.

Answer 3

def dijkstra(G, src): distances = {node: float('inf') for node in G.nodes()} distances[src] = 0

pq = [(0, src)]
while pq:
    current_distance, current_node = heapq.heappop(pq)

    if current_distance > distances[current_node]:
        continue

    for neighbor in G.neighbors(current_node):
        weight = G.edges[current_node, neighbor]['weight']
        distance = current_distance + weight
        if distance < distances[neighbor]:
            distances[neighbor] = distance
            heapq.heappush(pq, (distance, neighbor))

return distances