A few simple graph problems, and their interestingly cute solutions!

Recently, I was solving a few graph problems from here, and I found the questions to be simple yet challenging! By this, I just mean that the questions didn't ask for any advanced knowledge from my side, and yet it was a challenge to come up with simple solutions for them.

There were many questions, for which I too came up with my answers, but they were complex. On the other hand, the given solutions were quite simple, and they had an aesthetic beauty that only an algorithmist can understand. Hence, the cuteness.

I am just providing the questions here in brief, and the underlying thought process that led to those cute solutions. For a detailed study, which you must do, go here.

1. Design an algorithm that finds all bridges in undirected, connected graph G in O(V · E) time.
   
   Actually this is the third part of one question. They beautifully and thoroughly made the students think over the solution. The key idea is to think of the BFS tree of the graph.
   
   First, they asked to prove that all the bridges will be present in the BFS tree of the graph. Then, to examine the running time of checking whether a given edge is a bridge or not. And finally they stated the problem that I mentioned.
   
   What an amazing way to teach students how to solve problems!
   
   
2. To find an efficient algorithm to find the number of paths in directed acyclic graph G from s to t.
   
   Topological sorting, and storing the number of paths to all the vertices, using the previous counts to build the next ones!
   
   
3. Suppose you are given a city map with unit distance between each pair of directly connected locations. Design an O(V + E)-time algorithm that finds the number of shortest paths between the source vertex s and the target vertex t.
   
   Always remember, BFS finds the shortest path to all the vertices in an unweighted graph. And then again, we can store the number of shortest paths to all the vertices, using the previous counts to build the next ones.
   
   But remember, we are finding the number of shortest paths in an unweighted graph!
   
   
4. Consider a connected weighted directed graph G = (V, E, w). Define the fatness of a path P to be the maximum weight of any edge in P. Give an efficient algorithm that, given such a graph and two vertices u, v ∈ V , finds the minimum possible fatness of a path from u to v in G.
   
   Amazing question, and what a cute solution! A good reminder to self regarding what value does d[u] store for all the vertices. A simple change in RELAX method of Dijkstra's algorithm. Seriously, this never crossed my mind before I read the solution.
   
    
5. Given four vertices u, v, s, and t in a directed weighted graph G = (V, E) with non-negative edge weights, present an algorithm to find out if there exists a vertex vc ∈ V which is part of some shortest path from u to v and also a part of some shortest path from s to t. The algorithm should run in O(E + V log V ) time.
   This is my favourite of all. The solution just requires understanding the basic definition
   d[u,v] = d[u,vc] + d[vc,v]. And there you have it.
   

I found all these questions to be quite mind-stretching, and yet looking out for only the elements of understanding in me!