Putting It Together: Graph Theory

At the start of this module, you were thinking about finding the fastest route from one client to another.  Thankfully, now you know how to use graph theory to figure it out.  Take another look at the diagram.  Now you know it is a graph in which each vertex represents a client and each edge represents a path between clients.  The numbers, or weights, indicate the length of time (minutes) required to travel from one vertex to another.

Graph diagram connects locations A through E. A connects to B by 8 units, B to C by 8 units, C to D by 10 units, D to E by 8 units, E to F by 7 units, F to G by 5 units, G to H by 5 units, and H to I by 5 units. In addition, B connects to D by 14 units, B to F by 20 units, F to I by 15 units, and G to I by 12 units.

One vertex, A, is degree 1. Some vertices are degree 2, such as C and E, and H.  Others are degree 3, such as D and G. Still others are degree 4, such as B, F, and I.  What does that mean for you?  It means that there are multiple paths leading from each client and several different routes you can take traveling from one to the other.

You were faced with the problem of having to get from Client G to Client C using the fastest route.  Start by marking the ending vertex with a time of 0.  Then find all vertices leading to the current vertex.  Calculate their distances to the end.

Graph diagram connects locations A through E. A connects to B by 8 units, B to C by 8 units, C to D by 10 units, D to E by 8 units, E to F by 7 units, F to G by 5 units, G to H by 5 units, and H to I by 5 units. In addition, B connects to D by 14 units, B to F by 20 units, F to I by 15 units, and G to I by 12 units. A red 0 is placed near C, 10 by D, and 7 by B.

Mark C as visited, and mark the vertex with the smallest recorded time as current.  So B will be designated current.  Again find all vertices leading to the current vertex.  For each vertex leading to B, and not to a visited vertex, find the time from the end.

Graph diagram connects locations A through E. A connects to B by 8 units, B to C by 8 units, C to D by 10 units, D to E by 8 units, E to F by 7 units, F to G by 5 units, G to H by 5 units, and H to I by 5 units. In addition, B connects to D by 14 units, B to F by 20 units, F to I by 15 units, and G to I by 12 units. A red 0 is placed near C, 10 by D, 7 by B, 27 by F, 15 by A, and 17 by I.

Mark B as visited, and mark the vertex with the smallest recorded time as current.  So D will be designated current.  Add CD to DE, 10 + 8 = 18.

Graph diagram connects locations A through E. A connects to B by 8 units, B to C by 8 units, C to D by 10 units, D to E by 8 units, E to F by 7 units, F to G by 5 units, G to H by 5 units, and H to I by 5 units. In addition, B connects to D by 14 units, B to F by 20 units, F to I by 15 units, and G to I by 12 units. A red 0 is placed near C, 10 by D, 7 by B, 27 by F, 15 by A, 17 by I, and 18 by E.

Compare the time at E with that at I.  The time at I is lower so mark E as visited, and mark I as current.  So C to G through I has a total of 32 minutes.  But the time at H is only 22 minutes.  Since it is lower, keep going. Mark I as visited and H as current.  The total time from C to G through H is 27 minutes.  This is the fastest route.

Graph diagram connects locations A through E. A connects to B by 8 units, B to C by 8 units, C to D by 10 units, D to E by 8 units, E to F by 7 units, F to G by 5 units, G to H by 5 units, and H to I by 5 units. In addition, B connects to D by 14 units, B to F by 20 units, F to I by 15 units, and G to I by 12 units. A red 0 is placed near C, 10 by D, 7 by B, 25 by F, 15 by A, 17 by I, 18 by E, 27 by G, and 22 by H.

 

So it will take you 27 minutes to get back to Client C to pick up your sample.  It may have looked as if a different route, perhaps D, would have been faster but it turns out not to be the case.  Using the graph confirmed the best route.

Now you have to get all the way to your next client at H.  You can tell by the work you have already done that the fast route back to H is from C to B to I to H.  And how long will that take?  It will take a speedy 22 minutes.  Drawing a graph may seem complex, but in the end it really helps you make definite calculations rather than estimating.  And that can mean the difference between closing the deal or missing the client altogether.