Finding shortest path on colored graph with color restrictions

Question

Hello!!

I have a weighted directed graph with colors assigned to the nodes. I need to find the shortest path in the graph that contains at most one of the nodes of the specified color.

For example: say we have a graph with 5 different colors {red, black, green, white, yellow} and we were told we need to find the shortest path that contains at most one black node.

What is the best way to approach this problem?

I was thinking about using Dijkstra’s algorithm but I don’t know how to modify it to suit my problem.

Any help is appreciated!! Thankss!

Answer 1

bluesea i dont think this will work because the first black node is added it might have a way longer path than another one with a different black node

Answer 2

oh i see thanks!!