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

Related posts about algorithm

Related posts about homework