In the modern world, planning efficient routes is essential for business and industry, with applications as varied as product distribution, laying new fiber optic lines for broadband internet, and suggesting new friends within social network websites like Facebook.

This field of mathematics started nearly 300 years ago as a look into a mathematical puzzle (we’ll look at it in a bit). The field has exploded in importance in the last century, both because of the growing complexity of business in a global economy and because of the computational power that computers have provided us.

Example 14.1

Naturally, she wants to minimize the amount of walking she has to do. Is it possible for her to walk down every street in this development without having to do any backtracking? While you might be able to answer that question just by looking at the picture for a while, it would be ideal to be able to answer the question for any picture regardless of its complexity.

To do that, we first need to simplify the picture into a form that is easier to work with. We can do that by drawing a simple line for each street. Where streets intersect, we will place a dot.

Definition 14.2: Graphs, Vertices, and Edges

A graph consists of a set of dots, called vertices, and a set of edges connecting pairs of vertices.

While we drew our original graph to correspond with the picture we had, there is nothing particularly important about the layout when we analyze a graph. Both of the graphs below are equivalent to the one drawn above since they show the same edge connections between the same vertices as the original graph.

Example 14.3

Back in the 18th century in the Prussian city of Königsberg, a river ran through the city and seven bridges crossed the forks of the river. The river and the bridges are highlighted in the picture to the right

As a weekend amusement, townsfolk would see if they could find a route that would take them across every bridge once and return them to where they started.

Leonard Euler (pronounced OY-lur), one of the most prolific mathematicians ever, looked at this problem in 1735, laying the foundation for graph theory as a field in mathematics. To analyze this problem, Euler introduced edges representing the bridges:

Since the size of each land mass it is not relevant to the question of bridge crossings, each can be shrunk down to a vertex representing the location:

Notice that in this graph there are two edges connecting the north bank and island, corresponding to the two bridges in the original drawing. Depending upon the interpretation of edges and vertices appropriate to a scenario, it is entirely possible and reasonable to have more than one edge connecting two vertices.

While we haven’t answered the actual question yet of whether or not there is a route which crosses every bridge once and returns to the starting location, the graph provides the foundation for exploring this question.

Definition 14.4: Vertex

Definition 14.5: Edges

Definition 14.6: Loop

A loop is a special type of edge that connects a vertex to itself. Loops are not used much in street network graphs.

Definition 14.7: Degree of a vertex

The degree of a vertex is the number of edges meeting at that vertex. It is possible for a vertex to have a degree of zero or larger.

Definition 14.8: Path

A path is a sequence of vertices using the edges. Usually we are interested in a path between two vertices. For example, a path from vertex A to vertex M is shown below. It is one of many possible paths in this graph.

Definition 14.9: Circuit (a.k.a. cycle)

A circuit (a.k.a. cycle) is a path that begins and ends at the same vertex. A circuit (a.k.a. cycle) starting and ending at vertex A is shown below.

Definition 14.10: Connected

A graph is connected if there is a path from any vertex to any other vertex. Every graph drawn so far has been connected. The graph below is disconnected; there is no way to get from the vertices on the left to the vertices on the right.

Definition 14.11: Weights

Learning Checkpoint 14.3.1

The graph below shows 5 cities. The weights on the edges represent the airfare for a one-way flight between the cities.

a.

How many vertices and edges does the graph have?

b.

Is the graph connected?

c.

What is the degree of the vertex representing LA?

d.

If you fly from Seattle to Dallas to Atlanta, is that a path or a circuit?

e.

If you fly from LA to Chicago to Dallas to LA, is that a path or a circuit?

Learning Outcomes

• What is the problem statement?

• How to use Dijkstra’s algorithm

• Software solutions

Resources

Example 14.12

Suppose you need to travel from Yakima, WA (vertex Y) to Tacoma, WA (vertex T). Looking at a map, it looks like driving through Auburn (A) then Mount Rainier (MR) might be shortest, but it’s not totally clear since that road is probably slower than taking the major highway through North Bend (NB). A graph with travel times in minutes is shown below. An alternate route through Eatonville (E) and Packwood (P) is also shown.

Step 2 (#2): For each vertex leading to P (and not leading to a visited vertex) we find the distance from the end. Since E is 96 minutes from P, and we’ve already calculated P is 76 minutes from Y, we can compute that E is $96+76=172$ minutes from Y.

Step 2 (#6): The only non-visited vertex leading to E is T. Calculating the distance from T to Y through E, we compute $172+57=229$ minutes. Since this is longer than the existing marked time, we do not replace it.

Step 3 (#6): We mark E as visited. Since all vertices have been visited, we are done.

From this, we know that the shortest path from Yakima to Tacoma will take 160 minutes. Tracking which sequence of edges yielded 160 minutes, we see the shortest path is Y-NB-A-T.

Example 14.13: Dijkstra’s algorithm example

We will initialize our algorithm at node ’a’.

We can now summarize our calculations that followed Dijkstra’s algorithm.

and has length

Example 14.14

A shipping company needs to route a package from Washington, D.C. to San Diego, CA. To minimize costs, the package will first be sent to their processing center in Baltimore, MD then sent as part of mass shipments between their various processing centers, ending up in their processing center in Bakersfield, CA. From there it will be delivered in a small truck to San Diego.

The travel times, in hours, between their processing centers are shown in the table below. Three hours has been added to each travel time for processing. Find the shortest path from Baltimore to Bakersfield.

While we could draw a graph, we can also work directly from the table.

Step 1: The ending vertex, Bakersfield, is marked as current.

Step 2: All cities connected to Bakersfield, in this case Denver and Dallas, have their distances calculated; we’ll mark those distances in the column headers.

Step 3 & 4: Mark Bakersfield as visited. Here, we are doing it by shading the corresponding row and column of the table. We mark Denver as current, shown in bold, since it is the vertex with the shortest distance.

Step 2 (#2): For cities connected to Denver, calculate distance to the end. For example, Chicago is 18 hours from Denver, and Denver is 19 hours from the end, the distance for Chicago to the end is $18+19=37$ (Chicago to Denver to Bakersfield). Atlanta is 24 hours from Denver, so the distance to the end is $24+19=43$ (Atlanta to Denver to Bakersfield).

Step 3 & 4 (#2): We mark Denver as visited and mark Dallas as current.

Step 2 (#3): For cities connected to Dallas, calculate the distance to the end. For Chicago, the distance from Chicago to Dallas is 18 and from Dallas to the end is 25, so the distance from Chicago to the end through Dallas would be $18+25=43$. Since this is longer than the currently marked distance for Chicago, we do not replace it. For Atlanta, we calculate $15+25=40$. Since this is shorter than the currently marked distance for Atlanta, we replace the existing distance.

Step 3 & 4 (#3): We mark Dallas as visited, and mark Chicago as current.

Step 2 (#4): Baltimore and Atlanta are the only non-visited cities connected to Chicago. For Baltimore, we calculate 15+37 = 52 and mark that distance. For Atlanta, we calculate $14+37=51$. Since this is longer than the existing distance of 40 for Atlanta, we do not replace that distance.

Step 3 & 4 (#4): Mark Chicago as visited and Atlanta as current.

Step 2 (#5): The distance from Atlanta to Baltimore is 14. Adding that to the distance already calculated for Atlanta gives a total distance of $14+40=54$ hours from Baltimore to Bakersfield through Atlanta. Since this is larger than the currently calculated distance, we do not replace the distance for Baltimore.

Step 3 & 4 (#5): We mark Atlanta as visited. All cities have been visited and we are done.

The shortest route from Baltimore to Bakersfield will take 52 hours, and will route through Chicago and Denver.

Learning Outcomes

• Find the smallest set of edges that connects a graph

Resources

Definition 14.15: Spanning Tree

A spanning tree is a connected graph using all vertices in which there are no circuits. In other words, there is a path from any vertex to any other vertex, but no circuits.

Some examples of spanning trees are shown below. Notice there are no circuits in the trees, and it is fine to have vertices with degree higher than two.

Usually we have a starting graph to work from, like in the phone example above. In this case, we form our spanning tree by finding a subgraph – a new graph formed using all the vertices but only some of the edges from the original graph. No edges will be created where they didn’t already exist.

Question: How many edges are in a spanning tree of a connected graph?

Definition 14.16: Minimum Cost Spanning Tree (MCST)

The minimum cost spanning tree is the spanning tree with the smallest total edge weight.

Applications of the Minimum Cost Spanning Tree (MCST):

1.

Network Design: When laying fiber optic cables, water pipes, or electrical wires to connect a set of cities or buildings, we want to ensure full connectivity at the lowest installation cost. An MCST gives the cheapest way to connect all locations without creating loops.

2.

Transportation Infrastructure: A transportation planner may need to connect a set of towns with roads while minimizing total construction cost. The MCST provides a plan to connect all towns with no redundant roads.

3.

Clustering in Machine Learning: In hierarchical clustering, data points can be viewed as nodes in a graph, with edges weighted by pairwise distances. The MCST captures the structure of the data, and removing the largest edges can reveal natural clusters.

4.

Reliable Communication Networks: For basic connectivity in communication systems (e.g., computer networks or telecommunications), an MCST ensures all devices are connected with minimal total wiring cost, providing a base network.

5.

Subroutines in Approximation Algorithms: The MCST is used as a key subroutine in approximation algorithms for NP-hard problems, such as the Traveling Salesperson Problem (TSP). For instance, the 2-approximation for metric TSP begins by constructing a minimum spanning tree to guide tour construction.

Kruskal’s algorithm is a surprisingly simple algorithm. It builds a spanning tree one edge at a time by choosing the cheapest next edge to add. But! It skips the edge if this edge would create a cycle.

Here is an algorithm description:

Algorithm: Kruskal’s Algorithm (Descriptive Version)

  Input: A connected, undirected graph $G=(V,E)$ with edge weights $w(e)$.

  Initialization: Mark all edges as unused. Set $T\leftarrow \varnothing$.

repeat

  Select the cheapest unused edge in the graph.

if adding the edge would create a cycle then

  Skip this edge.

else

  Add the edge to $T$.

end if

until $T$ contains $\left|V\right|-1$ edges (i.e., a spanning tree has been formed).

  Output: The set $T$, forming a minimum spanning tree of $G$.

In pseudocode, the algorithm looks like this:

Algorithm: Kruskal’s Algorithm

  Input: A connected, undirected graph $G=(V,E)$ with weights $w(e)$ on each edge $e\in E$.

  Initialization:

• Set $T\leftarrow \varnothing$.

• Sort all edges $E$ in non-decreasing order by weight.

for each edge $e\in E$ in sorted order do

if adding $e$ to $T$ does not form a cycle then

  Add $e$ to $T$.

end if

if $T$ contains $\left|V\right|-1$ edges then

  break

end if

end for

  Output: The set $T$, which forms a minimum spanning tree.

Example 14.17

Using our phone line graph from above, begin adding edges:

At this point we stop – every vertex is now connected, so we have formed a spanning tree with cost $24 thousand a year.

Example 14.18

The power company needs to lay updated distribution lines connecting the ten Oregon cities below to the power grid. How can they minimize the amount of new line to lay?

Using Kruskal’s algorithm, we add edges from cheapest to most expensive, rejecting any that close a circuit. We stop when the graph is connected.

Continuing,

Exercise 14.19: Min Cost Spanning Tree

Find a minimum cost spanning tree on the graph below using Kruskal’s algorithm.

Exercise 14.20: Networkx

Use the code below to load the prior exercise’s graph into Python. Then solve this problem using the Networkx package.

Algorithm: Prim’s Algorithm (Descriptive Version)

  Input: A connected, undirected graph $G=(V,E)$ with edge weights $w(e)$.

  Initialization: Start with any vertex $v\in V$. Let $T\leftarrow \{v\}$ and $E_T\leftarrow \varnothing$.

repeat

  Find the cheapest edge with one endpoint in $T$ and one endpoint not in $T$.

  Add that edge to $E_T$ and its other endpoint to $T$.

until $T$ includes all vertices.

  Output: The set $E_T$, forming a minimum spanning tree of $G$.

In pseudocode, the algorithm looks like this:

Algorithm: Prim’s Algorithm

  Input: A connected, undirected graph $G=(V,E)$ with weights $w(e)$ on each edge.

  Initialization:

• Pick an arbitrary starting vertex $v_0$.

• Let $T\leftarrow \{v_0\}$, $E_T\leftarrow \varnothing$.

while $\left|T\right|<\left|V\right|$ do

  Among all edges $(u,v)\in E$ with $u\in T$ and $v\notin T$, find the one with minimum weight.

  Add $v$ to $T$, and $(u,v)$ to $E_T$.

end while

  Output: The set $E_T$, which forms a minimum spanning tree.

Example 14.21

Using our phone line graph from above, begin with vertex A and grow the tree:

The same minimum cost spanning tree is produced, and we stop once all vertices have been added to the tree.

Exercise 14.22: Prim’s Algorithm

Exercise 14.23: Shortest Path Problem

Find the shortest path between vertices A and G in the graph below.

Skills

Solution

Dijkstra’s algorithm was introduced by Edsger W. Dijkstra in his 1959 paper “A note on two problems in connexion with graphs,” Numerische Mathematik 1, 269–271. The algorithm finds the shortest path between two nodes; a common variant finds the shortest paths from a single source node to every other node in the network.

Resources

Several graph libraries are available in Python, each with distinct strengths depending on your needs. NetworkX is widely used for its ease of use and flexibility, especially for small to medium-sized graphs. For high-performance analysis on large graphs, graph-tool and NetworKit offer optimized implementations of common graph algorithms. igraph strikes a balance between speed and usability, while libraries like PyTorch Geometric and DGL are specifically designed for machine learning on graphs. The table below compares key features across several popular graph libraries.