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
[edit | edit source]Minimal spanning tree
[edit | edit source]Kruskal's algorithm
[edit | edit source]- 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
[edit | edit source]Graphical approach
[edit | edit source]- 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
[edit | edit source]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
[edit | edit source]Dijkstra's algorithm
[edit | edit source]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
- Label start node S with a P-label of 0.
- For all nodes reachable from S, assign a T-label equal to their direct distances from S.
- 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
- 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.
- Select the minimum T-label and make it permanent.
- If this labels the destination node continue, else repeat step 2.
- Step 3
- 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.