# finding shortest valid path in a colored-edge graphs

Posted
by
user1067083
on Stack Overflow
See other posts from Stack Overflow
or by user1067083

Published on 2011-11-26T16:33:22Z
Indexed on
2011/11/26
17:51 UTC

Read the original article
Hit count: 307

Given a directed graph G, with edges colored either green or purple, and a vertex S in G, I must find an algorithm that finds the shortest path from s to each vertex in **G so the path includes at most two purple edges** (and green as much as needed).

I thought of BFS on G after removing all the purple edges, and for every vertex that the shortest path is still infinity, do something to try to find it, but I'm kinda stuck, and it takes alot of the running time as well...

Any other suggestions?

Thanks in advance

© Stack Overflow or respective owner