Weighted Graphs, Networks, and the Shortest Path Problem (VCE SSCE General Mathematics): Revision Notes

Weighted Graphs, Networks, and the Shortest Path Problem

Introduction to weighted graphs and networks

In many real-world situations, we need to represent more than just connections between locations or points. We often need to show additional information such as distances, times, or costs. This is where weighted graphs become useful.

A weighted graph is a graph that has a number associated with each edge. These numbers are called weights. The weights can represent any kind of numerical information we want to attach to the connections in our graph.

For example, consider a graph showing how six towns are connected by roads. Initially, the graph might just show which towns have direct road connections. However, we can make this graph much more informative by adding weights to each edge.

In this weighted graph, each edge has a number representing the distance between towns in kilometres. For instance, the edge connecting Town A and Town B shows $7$, meaning these towns are $7$ km apart. Similarly, Town E and Town F are connected by an edge with weight $7$, indicating a $7$ km distance.

What is a network?

While all networks are weighted graphs, not all weighted graphs are networks. The key distinction is what the weights represent.

A network is a weighted graph in which the weights represent physical quantities. These physical quantities include:

• Distance (measured in kilometres, metres, etc.)
• Time (measured in minutes, hours, etc.)
• Cost (measured in dollars, pounds, etc.)

Interpreting a network

Being able to read and extract information from network diagrams is an essential skill. Let's explore how to work with networks through a practical example.

Consider a network representing walking tracks in a forest. The vertices represent key locations like gates, a bridge, a waterfall, and other points of interest. The edges show the direct paths connecting these locations, with weights indicating walking times in minutes.

In this forest network:

• $W$ represents a waterfall
• $B$ represents a suspension bridge
• $T$ represents a very old tree
• $F$ represents a fern gully
• $G1$ and $G2$ represent entrance/exit gates

The numbers on the edges tell us how many minutes it takes to walk between directly connected locations.

Reading direct connections

To find the time to walk directly between two connected locations, simply identify the edge linking them and read the weight. For example:

• Walking directly from the bridge ($B$) to the fern gully ($F$) takes $12$ minutes (reading the weight on edge $B$-$F$)
• Walking from the waterfall ($W$) to the old tree ($T$) takes $10$ minutes

Calculating path lengths

When traveling between locations that aren't directly connected, or when following a specific route through multiple points, we need to add up the weights of all edges along the path.

This systematic approach of identifying the path and summing the individual edge weights works for any sequence of connected vertices in a network.

Practice problem

Consider this network showing towns and the distances between them in kilometres:

Using the same principles:

• To find the distance from Stratmoore directly to Osburn, locate the edge connecting these vertices and read the weight
• To find the distance from Stratmoore to Kenton via Melville then Osburn, identify each edge in the path (Stratmoore-Melville, Melville-Osburn, Osburn-Kenton) and add their weights

The shortest path problem

One of the most important questions we can ask about a network is: "What is the shortest route between two vertices?" This challenge is known as the shortest path problem.

In this network, finding the shortest distance between some towns is straightforward. For example, Town A and Town B are directly connected, so the shortest distance is simply the weight of that edge: $7$ km.

However, when towns aren't directly connected, such as Town F and Town C, we must travel through other towns. This means we need to compare different possible routes to find the shortest one.

While sophisticated mathematical techniques exist for solving the shortest path problem systematically, for smaller networks we can use a practical method called finding the shortest path by inspection. This means identifying all reasonable routes and comparing their total lengths.

Method: Finding the shortest path by inspection

The inspection method involves these key steps:

Step 1: Identify all likely shortest routes

List all reasonable paths between the starting and ending vertices. To save time, eliminate paths that:

• Pass through any vertex more than once
• Use any edge more than once
• Take an obvious detour when a direct route exists

Step 2: Calculate the length of each route

For each identified path, add up the weights of all edges along that path.

Step 3: Compare and identify the shortest

Compare all calculated lengths and identify the minimum value. This is your shortest path. Note that sometimes multiple paths may have the same minimum length, meaning there can be more than one shortest path in a network.

Worked example: Finding the shortest route

Exam tips

Practice problem

Find the shortest route between the waterfall ($W$) and the fern gully ($F$) in this forest network. Remember to:

• List all reasonable paths
• Calculate the total time for each path
• Compare results to find the minimum

Remember!