A social network and metro system representation - Shortest path problem :
Finding the shortest path. Checking the six degrees of separation (for a social network). Finding the shortest path from a station to another that crosses all underground lines (for a metro system).