0

# Finding shortest path on colored graph with color restrictions

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!

2 odpowiedzi

0

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

0

oh i see thanks!!