时间戳

首页 > 解决方案 > 根据边缘标签向路径添加额外成本

python - 根据边缘标签向路径添加额外成本

问题描述

我有一个带有一些边的图。每条边都有一个权重/成本，还有一个标签/类型，可以是red和green。

我知道如果我运行 Dijkstra 的算法，它会从所有边的权重中找到最短/最便宜的路径。但是，我的问题是，根据它选择的边缘类型，应该增加额外的成本。原则上，只应在每次使用新类型时增加额外成本。

例如，如果我从 Dijkstra 找到的路径是：

node1  --->  node2  --->  node3  --->  node4  ----->  node5  ----->  node6

|---- edge1  --|-- edge2 ---|--- edge3 --|--- edge4 ----|--- edge5 ----|

   type = red    type = red   type = red   type = green   type = green

然后应根据此设置/逻辑添加添加的额外成本：

for i, edge in enumerate(path.edges):
    if edge[i].type == edge[i+1].type:
        <do not add any additional cost>
    elif edge[i].type != edge[i+1].type:
        <add additional cost to [i] edge>

因此，仅当路径中的类型之间发生更改时，才应添加额外的成本。

我不知道这是否有可能以任何方式做到？

标签： pythonnetworkxgraph-theory

解决方案

您可以将 Dijkstra 的算法应用于图形的修改版本，这将考虑额外的成本：

  • 复制图中的每个节点v，使旧图中的每个节点对应新图中的一个绿色节点v_g和一个红色节点v_r；
  • 新节点v_g将从v;
  • 新节点v_r将从v;
  • 此外，添加一条连接v_g到的边v_r，使用代码中的权重<add additional cost to [i] edge>。

构建新图

考虑这种结构的另一种方法是假设您有两个原始图的副本：红色图和绿色图；两个图都有所有节点，但每个图只有正确颜色的边；并且有一个额外的黑色边将红色图中的每个节点连接到绿色图中的相应节点。

路径的起点：路径开始的节点在 Dijkstra 算法中起着特殊的作用。既然启动节点现在已经分为两个节点start_r和start_g，那么你怎么知道从哪个节点启动 Dijkstra 呢？您可以运行算法两次，一次从 开始start_g，一次从 开始start_r，并保持最小的解；但有一个更好的解决方案。由于最短路径将没有环，因此您可以将0start_r和之间的边的权重设置start_g为 0，而不是其他节点使用的权重；最短路径不会使用这条边，除非可能有一次作为路径的第一条边。

请注意，结束节点在 Dijkstra 算法中没有任何特殊作用（Dijkstra 实际上计算从开始节点到每个其他节点的最短距离）；所以你不必担心端节点。

现在您可以在新图上运行常规 Dijkstra 算法。

推荐阅读