Multi tool use

Constrained shortest distance in a graph

I came across this problem at a coding site and I have no idea on how to solve it. The editorial is not available nor was I able to find any related article online. So I am asking this here.

You have a graph G that contains N vertices and M edges. The vertices are numbered from 1 through N. Also each node is colored either Black or White. You want to calculate the shortest path from 1 to N such that the difference of black and white nodes is at most 1.

As obvious as it is, applying straight forward Dijkstra's Algorithm will not work. Any help is appreciated. Thank you!

N

M

1 Answer
1

We can consider a modified graph and run Dijkstra on this one:

For each node in the original graph, the modified graph will have multiple meta vertices (theoretically, infinitely many) that each correspond to a different black-white difference. You only need to create the nodes as you explore the graph with Dijkstra. Thus, you won't need infinitely many nodes.

The edges are then pretty simple (you can also create them while exploring). If you are currently at a node with black-white difference d and the original graph has an edge to a white node, then you create an edge to the respective node with black-white difference d-1. If the original graph has an edge to a black node, you create an edge in the modified graph to the respective node with black-white difference d+1. You don't necessarily need to treat them as different nodes. You can also store the Dijkstra variables in the node grouped by black-white difference.

d

d-1

d+1

Running Dijkstra in this way will give you the shortest paths to any node with any black-white difference. As soon as you reach the target node with an acceptable black-white difference, you are done.

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.