decision 1 algorithms

Primms algorthim to find a minimum spanning tree

• from start vertexchoose the lowest weight edge
• check new edge doesnt create a cycle
• add new edge
• add lowest edge from any connected vertex
• repeat previous3 steps until all nodes are connected

Primms algorithm from a matrix to find a minimum spanning tree

• label start vertex column 1 and cross out the corresponding row
• ring the lowest value in a labelled column
• label column of ringed number and delete its row
• repeat previous 2 steps until all columns are labelled

kruskals algorithm to find a minimum spanning tree

• choose unused edge with lowest value
• check new edge doesnt create a cycle
• add new edge
• repeat until all edges are connected

Dijkstra's algorithm to find the shortest path

• label start vertex as 0
• box this number
• label each vertex that is connected to the newly boxed vertex with the boxed value plus the value of the edge if there is no label or if this is lower than the current label
• box the lowest un boxed label
• repeat previous 3 steps until the end vertex has a boxed label

If there are multiple start points and a single end point start at the end and work backwards and choose the lowest value from the values of each of the start points.

The chinese postman problem finds the shortest distance you can travel if you are to use every edge at least once and return to his start point

• First you have to establish if the graph is Eulerian
• to make a non eularian graph eularian pair odd nodes in the shortest distance and addextra arcs to the original graph
• the optimum distance is the sum of all the original nodes plus all the addedones

the travelling sales person problem is to find the shortest tour

a tour visits every vertex and returns to the start vertex and will always have the same number of edges as there are nodes. For the following algorithms to be correct the graph must be complete if this is not the case the graph must be made complete first.

Nearest neighbour algorithm -calculating upper bounds

• from your start vertex go to nearest unvisited vertex
• from current vertex got to nearest unvisited vertex
• repeat previous step until all vertexes have been visited
• return to start vertex

remember the lowest upper bound is the best upper bound

calculating lower bounds

• delete a vertex and all connected edges
• find a minimum spanning tree for the remaining graph
• add the two shortest edges from the deleted vertex

remember the lower bound may not be possible and the highest lower bound is the best

improving a matching to make a maximum matching

• find avertex on the left-hand side that is not in the inital matching and connect it to a node on the right
• if this node is not in the inital matching then add it to the matching and repeat previous step
• add the new edge to the matching and remove the the edge linked to this vertex in the intial matching
• return to the begining and continue until no further improvement can be made