Shortest path for timedelta-weighted edges failed by using integer default weight despite all edge a-CodePudding

When I want to compute the shortest path through a timedelta-weighted graph in networkx like the following

import networkx as nx
from datetime import timedelta
 
G = nx.DiGraph()

G.add_edge(1, 2, timedelta=timedelta(seconds=1))
G.add_edge(2, 3, timedelta=timedelta(seconds=1))
G.add_edge(1, 3, timedelta=timedelta(seconds=3))

nx.single_source_dijkstra(G, 1, weight='timedelta')

the function throws an exception:

---------------------------------------------------------------------------
TypeError                                 Traceback (most recent call last)
/Users/michaeldorner/Research/Code/Information Diffusion in Code Review/notebooks/hops.ipynb Cell 4' in <module>
      4 G.add_edge(2, 3, timedelta=timedelta(seconds=1))
      5 G.add_edge(1, 3, timedelta=timedelta(seconds=3))
----> 7 nx.single_source_dijkstra(G, 1, weight='timedelta')

File /Library/Frameworks/Python.framework/Versions/3.10/lib/python3.10/site-packages/networkx/algorithms/shortest_paths/weighted.py:469, in single_source_dijkstra(G, source, target, cutoff, weight)
    373 def single_source_dijkstra(G, source, target=None, cutoff=None, weight="weight"):
    374     """Find shortest weighted paths and lengths from a source node.
    375 
    376     Compute the shortest path length between source and all other
   (...)
    467     single_source_bellman_ford
    468     """
--> 469     return multi_source_dijkstra(
    470         G, {source}, cutoff=cutoff, target=target, weight=weight
    471     )

File /Library/Frameworks/Python.framework/Versions/3.10/lib/python3.10/site-packages/networkx/algorithms/shortest_paths/weighted.py:730, in multi_source_dijkstra(G, sources, target, cutoff, weight)
    728 weight = _weight_function(G, weight)
    729 paths = {source: [source] for source in sources}  # dictionary of paths
--> 730 dist = _dijkstra_multisource(
    731     G, sources, weight, paths=paths, cutoff=cutoff, target=target
    732 )
    733 if target is None:
    734     return (dist, paths)

File /Library/Frameworks/Python.framework/Versions/3.10/lib/python3.10/site-packages/networkx/algorithms/shortest_paths/weighted.py:833, in _dijkstra_multisource(G, sources, weight, pred, paths, cutoff, target)
    831 if cost is None:
    832     continue
--> 833 vu_dist = dist[v]   cost
    834 if cutoff is not None:
    835     if vu_dist > cutoff:

TypeError: unsupported operand type(s) for  : 'int' and 'datetime.timedelta'

The problem seems to be with the weight attributes in thesingle_source_dijkstra(...) which sets non-existing attributes to 1 (which can then not be added to timedelta)

weight string or function If this is a string, then edge weights will be accessed via the edge attribute with this key (that is, the weight of the edge joining u to v will be G.edges[u, v][weight]). If no such edge attribute exists, the weight of the edge is assumed to be one.

and later in the notes:

Edge weight attributes must be numerical. Distances are calculated as sums of weighted edges traversed.

But according to nx.get_edge_attributes(G, 'timedelta') everything seems to be correct:

{(1, 2): datetime.timedelta(seconds=1),
 (1, 3): datetime.timedelta(seconds=3),
 (2, 3): datetime.timedelta(seconds=1)}

nx.single_source_dijkstra(G, 1, weight=lambda u, v, data: data['timedelta'].total_seconds())

fix the issue but I still don't get why?

Why would timedelta be non-numerical? What went wrong?

CodePudding user response：

Networkx initializes the path length to 0 when it starts (that’s the distance from the source to itself). Then to calculate the length of a path, it successively adds the weight of each edge.

In your case at the very first edge it cannot add 0 to datetime.timedelta(seconds=1). Hence the error about not adding an int and datetime.timedelta. If you convert the weight into a numerical value then it runs fine.