One important use of graphs and graph theory can be illustrated by the following scenario:

   You are an exporter who needs to ship several boxes of your product to a major city in Europe.  There are various routes that the shipment could take.  The possible routes are laid out in the directed graph below.

   The graph above is called a network, and it must hold certain properties.  The vertex s, referred to as the "source" of the network, represents the city in which your company is located.  Notice that the indegree of the source must always be 0.  The vertex t, referred to as the "sink" of the network, represents the city to which you are shipping your product.  Notice that the outdegree of the sink must always be 0.  The other vertices (a, b, c, d) represent several "middlemen."  The number assigned to each edge, called the capacity of the edge, represents the maximum rate at which your product can be shipped over that particular edge (the capacity must be a non-negative number.)  You naturally wish to be able to send the boxes of your product at the highest possible rate through the graph, but without exceeding the capacity of each edge.

   Now, in order to show the rate at which you send your product, each edge must also be labeled with a non-negative number called the flow.  A flow must also hold certain properties.  The flow on an edge must not exceed the capacity of the edge.  This is referred to as the "capacity constraint."  The total flow into any vertex must equal the total flow out of the vertex. This is referred to as "flow conservation."  And due to flow conservation, it follows that the total flow out of the source must equal the total flow into the sink.  Look closely at the network below and you will see that these properties hold true (the flow is shown inside of parentheses.)

   In order to find the maximum flow through the graph you would set the flow on each edge to 0 and recursively attempt to improve on each flow until you can no longer send your product at a greater rate.  The actual algorithms used to find the maximum flow through a network are beyond the scope of this tutorial.

Back to Dijkstra's Algorithm

On to NP-Complete Problems