A-level Mathematics/MEI/D1/Networks

Networks are weighted graphs, their edges have associated weights with them. Networks are useful for modelling geographical problems (though they have many other uses).

Networks have a walk called the minimum spanning tree which is the shortest walk that connects every node in the network via edges. There are two algorithms for producing the minimal spanning tree: Kruskal's algorithm and Prim's algorithm, by the end of this page you should be able to use both algorithms in graphical form and Prim's algorithm in tabular form.

Finally you should also be able to use Dijkstra's algorithm to find the shortest route between two points.

Algorithms

Minimal spanning tree

Kruskal's algorithm

Pick the shortest edge of the network.
Pick the next shortest edge of the network that doesn't link nodes between which a path has already been established.
Repeat 2, until n-1 edges have been selected (where n is the number of nodes in the network).

Here's an example on Wikipedia: Kruskal's algorithm example.

Prim's algorithm

Graphical approach

Pick an arbitrary node.
Connect that node to its nearest node by an edge.
Now connect the nearest node that isn't already connected to the walk you're forming.
Repeat 3 until all nodes have been connected.

Example: Graphical run of Prim's algorithm.

Tabular approach

Networks can be represented in tabular form where distances are recorded between nodes.

Select an arbitrary node X.
Delete row X.
Look for smallest value in column X, read which node it belongs to, this is your new node Y.
Delete row Y.
Look for smallest value in column X and Y, then go to 3, repeat until network is connected.

Example: Tabular run of Prim's algorithm.

Shortest path

Dijkstra's algorithm

Permanent labels (P-labels) are depicted by a value contained in a box.

Temporary labels (T-labels) are depicted by a value with no box.

Step 1
1. Label start node S with a P-label of 0.
2. For all nodes reachable from S, assign a T-label equal to their direct distances from S.
3. Select the node with the smallest T-label value, make this a P-label, this label marks the shortest distance from S to that node
Step 2
1. Put a T-label on each node that can be reached directly from the node that has just been marked with a P-label. The T-label should be equal to the sum of the P-label and the direct distance from it. If there is an existing T-label at a node, it should be replaced if the new sum is smaller.
2. Select the minimum T-label and make it permanent.
3. If this labels the destination node continue, else repeat step 2.
Step 3
1. Trace back from the current node (the destination node) to the start node including any edge MN where (P-label of M) - (P-lalbel of N) = length of arc MN.

Example:

Find the shortest route between S and T using Dijkstra's algorithm.

Image	Description
	Here's the initial graph.
	Start by labelling the start node with a P-label of zero.
	Mark the directly connected nodes with T-labels of their distances from the start node.
	Make the lowest T-label a P-label, then mark it's directly connected nodes with T-labels of their own. Note: the T-label of Q has been cropped, it's 7
	Make the lowest T-label a P-label, mark it's directly connected connected nodes with T-labels of their own, here X's T-label has been relabelled as 4 as a shorted route has been found.
	Make the lowest T-label a P-label, mark it's directly connected connected nodes with T-labels of their own Note: the T-label of V is cropped out, it's 6
	Make the lowest T-label a P-label, mark it's directly connected connected nodes with T-labels of their own
	Make the lowest T-label a P-label, mark it's directly connected connected nodes with T-labels of their own
	Make the lowest T-label a P-label, mark it's directly connected connected nodes with T-labels of their own
	Make the lowest T-label a P-label, mark it's directly connected connected nodes with T-labels of their own
	Make the lowest T-label a P-label, mark it's directly connected connected nodes with T-labels of their own
	Finally trace back from the current node (the destination node) to the start node including any edge MN where (P-label of M) - (P-lalbel of N) = length of arc MN. Route, SUVWT is a shortest path, SPQRT also is a shortest path (but this wasn't chosen for the demonstration).