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

Question

我有一个带有一些边的图。每条边都有一个 weight/cost 和一个 label/type，可以是 red 和 green.

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

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

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

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

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

所增加的额外费用则应按此添加setup/logic:

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>

因此，只有在路径中的类型之间发生变化时，才应添加额外成本。

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

Answer 1

您可以将 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，并保留最小的解决方案；但有更好的解决方案。由于最短路径没有环，所以可以将start_r和start_g之间的边权重设置为0，而不是其他节点的权重；最短路径不会使用这条边，除了可能有一次作为路径的第一条边。

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

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

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

Add additional cost to path depending on label of edge

python

graph-theory

networkx