let's say that a map of a bus system is provide by as graph G. and each edge of this graph is colored to distinguish which of bus lines that edge is associated with. Come up an algorithm which returns the smallest number of times that one need to change lines in order to get from the start vertex to the end one. You can assume all the edges in any given line are connected. More specifically, One can get from any stop on one line to any other stop on that line without changing line.

Solution provided as:

enter image description here

So confused with the statement "Note that the number of steps on this path of trans-locating between stop and lines has the length of 2k." Can someone please me visualized it ? Understand that we can use BFS to find the shortest path in unweighted graph. K is the number of different lines, but why is 2k is the number of steps on this path? Try to construct the graph, don't think it is corrected. Any hint?

enter image description here

  • 1
    $\begingroup$ The problem seems incomplete to me. Please put the full original source and not as an image if possible. You should also credit the source. $\endgroup$ – Vince Jan 28 at 8:59

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.