Given a graph, G, with vertices, V, and edges, E, and V1 is one of the vertices in the graph, find the path in G such that it is the shortest path between V1 and a vertex and the path is greater than the shortest path between V1 and any other vertex in the graph.
For example, take this graph
In this graph, given V1 = node 4; the path that should result is 4 -> 1 -> 3 -> 5. The reason is that, the path 4-1-3-5 is the shortest path between 5 and 4 and it is the path that is longer than shortest paths between node 4 and any every other vertices.
Solution: We need to do a Breadth-First Search.
1) Take V1 as the root node. Then take all its children in a queue.
2) Do this till there is no more nodes in the queue:
2.a) If the children has been processed before, ignore it.
2.b) Otherwise, if the depth is the highest yet found, note down the path and depth for next iteration.
3) When all nodes are processed, return the highest yet depth and path.
1) Take V1 as the root node. Then take all its children in a queue.
2) Do this till there is no more nodes in the queue:
2.a) If the children has been processed before, ignore it.
2.b) Otherwise, if the depth is the highest yet found, note down the path and depth for next iteration.
3) When all nodes are processed, return the highest yet depth and path.
No comments:
Post a Comment