使用边代价函数计算networkx中的最短路径

Question

我想使用networkx计算节能路线。为此，我考虑将电池约束建模为边缘成本函数。在下面的示例中，我想根据我车辆的蓄电池负载计算s和t之间的最短路线（b）。我的网络约束将决定边缘成本函数

例如，在s和v1之间，如果s处的电池负载高于18，则边缘成本将为18；如果s处的电池负载低于18，则边缘成本将为18（接近无穷大）

是否可以定义networkx中最短路径算法将使用的边代价函数

或者你认为最好的解决方案是创建一个新的多有向图，其中所有不同的可能边缘成本都会根据起点的初始费用重新计算

编辑1: 为了简化问题，我们可以考虑负权重（对应于电池的充电）等于零。在第二次中，我将看到如何使用Johnson's algorithm。它似乎是在networkx（https://networkx.org/documentation/stable/reference/algorithms/generated/networkx.algorithms.shortest_paths.weighted.johnson.html）中实现的

编辑2: 最大电池负载为20，这解释了为什么电池负载在s和v_3之间没有增加，以及为什么不可能通过s->；v3->；v2

Answer 1

1. 假设初始电池电量无限大
2. 搜索得到的计算成本中最负的成本
3. 将最负成本（X）的绝对值添加到每个链接的成本中
4. 运行Dijsktra的算法，找到从源头到远处的最低成本
5. 从路径成本中减去X（P-X）
6. 若初始电池电量大于（P-X），则可到达目的地

比如说

C:\Users\James\code\PathFinder\bin>gui
l s v1 38
l s v3 0
l v1 v2 0
l v3 v2 38
l v2 t 23
s s
e t

s -> v3 -> v2 -> t ->

（PathFinder是DojsTr::DjjStA：图的执行）的C++包装

因此，现在我们有一个新的先前隐藏的约束，即电池容量最大为20。因此，我提出了另一种方法，它应该是针对可能出现的任何进一步限制的证据。它基于A* algorithm的思想

1. 重新设计问题，使充电站位于节点，充电站之间的链路具有恒定的正成本。（在我看来，这是一个更自然的真实世界模型）

2. 使用Dijsktra，仅考虑链路成本，从连接到当前完成节点（最初为起始节点）的每个节点查找到目的地的最便宜路径

3. 对于连接到当前节点的每个节点，将当前节点的链路成本、1中计算的到目的地的成本减去节点提供的任何充电

4. 从3中计算成本的每个节点中，选择最便宜的节点。跟踪用于到达此节点的路径并使其成为当前路径

5. 从步骤2重复，直到到达目标节点

这是一个非常专业的问题，我不会将其添加到PathFinder选项中。如果它代表了一个严重的现实问题，而不仅仅是家庭作业或学术练习，那么在PathFindergithub存储库上打开一个问题，我们可以讨论为此开发一次性应用程序的细节