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