Question

Problem 1: 

Shortest Path-ish 

Suppose that you want to get from vertex s to vertex t in an unweighted graph G = (V, E), but you would like to stop by vertex u if it is possible to do so without increasing the length of your path by more than a factor of a. Describe an efficient algorithm that would determine an optimal s-t path given your preference for stopping at u along the way if doing so is not prohibitively costly. (It should either return the shortest path from s to t or the shortest path from s tot containing u, depending on the situation.) If it helps, imagine that there are burgers at u. 

Problem 2: Discipline in Groups of Children 

Your job is to arrange n rambunctious children in a straight line, facing front. You are given a list of m statements of the form "i hates j". If i hates j, then you do not want to put i somewhere behind j because then i is capable of throwing something at j. Give an algorithm that orders the line (or says it's not possible) in Om + n) time. Justify that you algorithm runs in the required time.

Answer 1

Ans to the question no 1:

We have an unweighted graph G = (V, E). Our task is to reach from s to t via u. I think the optimal solution could be: Since we have to pass by vertex u, the best way is to find the shortest path between (s and u) and (u and t) using BFS. Now we have the shortest path from s to t via u. And find the shortest path between s and t using BFS. Now you can choose the best path to return. This algorithm will work in O(V+E) time.

Ans to question no 2:

According to the question, there are two cases in which we have to care if the graph is acyclic then, in that case, we will reach to the parent before the child. And there could be a directed graph like i hates j and j hates i , so in this case ordering of nodes is not possible. So the efficient way to solve the problem is to use topological sorting using DFS, which can handle all the situations. Since the time complexity of DFS is O(V+E), topological sort uses the same approach so the time complexity of the algorithm will be O(m+n).