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). thumb|left|Network 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 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. Image Descriptionx150px Here's the initial graph.x150px Start by labelling the start node with a P-label of zero.x150px Mark the directly connected nodes with T-labels of their distances from the start node.x150px 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 7x150px 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.x150px 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 6x150px Make the lowest T-label a P-label, mark it's directly connected connected nodes with T-labels of their ownx150px Make the lowest T-label a P-label, mark it's directly connected connected nodes with T-labels of their ownx150px Make the lowest T-label a P-label, mark it's directly connected connected nodes with T-labels of their ownx150px Make the lowest T-label a P-label, mark it's directly connected connected nodes with T-labels of their ownx150px Make the lowest T-label a P-label, mark it's directly connected connected nodes with T-labels of their ownx150px 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).