尽管存在所有边属性，但使用整数默认权重的时间增量加权边的最短路径失败

Question

当我想通过 networkx 中的 timedelta 加权图计算最短路径时，如下所示

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')

函数抛出异常：

---------------------------------------------------------------------------
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'

问题似乎出在 weight attributes in thesingle_source_dijkstra(...) 上，它将不存在的属性设置为 1（然后无法将其添加到 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.

以及后面的注释中：

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

但是根据nx.get_edge_attributes(G, 'timedelta')一切似乎都是正确的：

{(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())

已解决问题，但我仍然不明白为什么？

为什么 timedelta 是非数字的？出了什么问题？

Answer 1

Networkx 在启动时将路径长度初始化为 0（即从源到自身的距离）。然后计算一条路径的长度，依次加上每条边的权重。

在你的情况下，在第一个边缘它不能将 0 添加到 datetime.timedelta(seconds=1)。因此，关于不添加 int 和 datetime.timedelta 的错误。如果将重量转换为数值，则它运行正常。

尽管存在所有边属性，但使用整数默认权重的时间增量加权边的最短路径失败

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

python

networkx

shortest-path