用边缘代价函数计算网络中的最短路径

Question

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

例如，在s和v1之间，如果s的电池负载高于18，则边缘成本为18；如果电池负载小于18，则边缘成本为18(接近无限)。

是否可以定义网络中最短路径算法使用的边缘代价函数？

​

​

或者，您认为最好的解决方案是创建一个新的MultiDiGraph，根据起始点的初始费用重新计算所有可能的边缘成本？

编辑1:简化了这个问题，我们可以考虑负重(相当于电池的充电)等于零。第二次，我将了解如何使用约翰逊算法。它似乎是在networkx (paths.weighted.johnson.html)中实现的。

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

Answer 1

1. 假设初始电池水平无限大。
2. 搜索得到的计算成本，以找出最负的。
3. 将最负成本(X)的绝对值添加到每个环节的成本中。
4. 运行Dijsktra的算法，找到从源到距离的最低成本。
5. 从路径成本减去X(P)
6. 如果初始电池电平大于(P)，则可到达目的地。

例如

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是Dijsktra的boost：：的C++包装器)

所以，现在我们有了一个新的以前隐藏的限制，电池容量最大为20。所以我提出了另一个假设，这应该是对任何可能出现的进一步限制的证明。它是基于算法的思想

1. 重新设计问题，使充电站处于节点，充电站之间的链路具有恒定的正成本。(在我看来，这是一个更自然的真实世界模型)
2. 使用Dijsktra，仅考虑链路成本，从连接到当前节点的每个节点(最初是起始节点)找到到达目的地的最便宜的路径。
3. 对于连接到当前的每个节点，从当前连接到目标的成本之和为1减去节点提供的任何充电。
4. 从3中计算的每一个节点中，选择最便宜的。跟踪用于到达此节点的路径，并使其成为当前路径。
5. 从步骤2重复，直到到达目标节点。

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