Weighted graphs
A weighted graph adds a bit of extra information to the edges. This can be a numerical value that indicates something. Let's say, for example, that the following graph indicates different ways to get from point A to point D. You can either go straight from A to D, or choose to pass through B and C. Associated with each edge is the amount of time in minutes the journey to the next node will take:
Perhaps the journey AD would require you to ride a bike (or walk). B and C might represent bus stops. At B you would have to change to a different bus. Finally, CD may be a short walk to reach D.
In this example, AD and ABCD represent two different paths. A path is simply a sequence of edges that you pass through between two nodes. Following these paths, you see that the total journey AD takes 40 minutes, whereas the journey ABCD takes 25 minutes. If your only concern is time, you would be better off traveling along ABCD, even with the added inconvenience of changing buses.
The fact...
