Add additional cost to path depending on label of edge

I have a graph with some edges. Each edge has a weight/cost and also a label/type, which could be red and green.

I know that if I run Dijkstra’s algorithm it will find the shortest/cheapest path from the weights of all edges. However, my issue is that depending on which type of edge it chooses, additional cost should be added. In principle, the additional cost should only be added each time a new type is used.

So for example if the path I find from Dijkstra’s is:

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

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

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

The additional cost added should then be added according to this 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>

So the additional cost should only be added if there is a change between types within the path.

I have no idea if this is even possible to do in any way ?

Answer

You can apply Dijkstra’s algorithm to a modified version of the graph which will account for the additional costs:

• Duplicate every node in the graph, so that every node v in the old graph corresponds to a green node v_g and a red node v_r in the new graph;
• The new node v_g will get every green edge from v;
• The new node v_r will get every red edge from v;
• In addition, add one edge linking v_g to v_r, with weight <add additional cost to [i] edge> from your code.

Another way to think of this construction is to imagine that you have two copies of the original graph: the red graph and the green graph; both graphs have all the nodes, but each graph only has the edges of the right colour; and there is one extra black edge connecting each node from the red graph to the corresponding node from the green graph.

Start of the path: The node where the path begins plays a special role in the Dijkstra algorithm. Since the start node has now been divided into two nodes start_r and start_g, how do you know which node to start Dijkstra from? You could run the algorithm twice, once from start_g and once from start_r, and keep the smallest solution; but there is a better solution. Since the shortest path will have no cycle, you can set the weight on the edge between start_r and start_g at 0 instead of the weight used for the other nodes; the shortest path will not use this edge, except possibly once as the very first edge of the path.

Note that the end node doesn’t play any special role in the Dijkstra algorithm (Dijkstra actually computes the shortest distances from the start node to every other node); so you don’t need to worry about the end node.

Now you can run regular Dijkstra algorithm on the new graph.