D1 Algortihms

To find a minimum spanning tree for a network with n edges

Step 1: Choose the unused edge with the lowest value

Step 2: Add this edge to your tree

Step 3: If there are n-1 edges in your tree stop. If not go to step one.

To find a minimum spanning tree for a network with n edges

Step 1: From a start vertex draw the lowest valued edge to start the tree

Step 2: From any vertex on the tree add the edge with the lowest value

Step 3: If there are n-1 edges you have finished, if not go to step 2 

Step 1: Label the start vertex as 0

Step 2: Box this number

Step 3: Label each vertex that is connected to the start vertex with its distance

Step 4: Box the smallest number

Step 5: From this vertex consider the distance to each connected vertex

Step 6: If a distance is less than a distance already at this vertex, cross out this distance      and write in the new distance. If there was no distance at the vertec write down the    new distance.

Step 7: Repeat from step 4 until the destination vertex is boxed.

An algorithm for finding the optimal Chinese Postman route

Step 1: List all odd verticies

Step 2: List all possible pairings of odd verticies

Step 3: For each pairing find the edges that connect the verticies with minimum weight

Step 4: Find the pairings such that the sum of the weights is minimised

Step 5: On the original graph add the edges that have been found in step 4

Step 6: The length of the optimal Chinese Postman route is the sum of all the edges added     to the total found in step 4

Step 7: A route corresponding to this minimal weight can then be easily found

Step 1: Delete a vertex and all its edges connected to the vertex

Step 2: Find a minimum spanning tree for the remaining network

Step 3: Add the two shortest edges from the deleted network