1. Model the road map, in order to find the best route from one place to another. Consider one-way streets, turn restrictions (intersections where you are not allowed to turn left, for instance) and turn costs (turning left is difficult in some intersections, so it should be penalized in the route cost).
2. Model the metro network, in order to find the best route from one metro station to another. Changing the metro (unboarding a metro going on one line and boarding another metro, on another line, in the same station) is to be penalized, say, as much as traveling 3 stations (because you need to wait for the next metro). The simple approach, where each station is a vertex and you put an edge between two stations iff they are consecutive on a line, cannot take into account the cost of changing lines.
3. Plane travel. We know the plane schedule, so, for each plane, we know the departure airport and time, and the arrival airport and time, as well as the travel fare. We want a sequence of flights from a given starting airport to a given destination airport. Waiting time in the intermediate airports must be added to the travel fares in order to get the actual total cost. Hint: represent each airport as a sequence of vertices, one for each departure or arrival time at that airport.
4. Consider the wolf-goat-cabbage problem. (A man has wolf, a goat and a cabbage and wants to cross a river with them using a boat that has room only for one of the three things. So, at each move, the man crosses the river with either an empty boat or with one of the three things. The rule is that he cannot let the goat with the cabbage or the wolf with the goat, unattended. The goal is to get with all three things on the other side in as few moves as possible.) The problem is twofold: how to associate a graph to the problem, and how to find an ad-hoc representation for it. First, the idea is to represent possible states as vertices and moves as edges. Second, the graph doesn't need to be represented as such in the memory: it is enough to have an implementation for the read-only functions a graph should expose.
Sample implementation: graph.py
Radu-Lucian LUPŞA