The Travelling Salesperson Algorithm

Find a cycle that goes through each vertex using the Nearest Neighbour Algorithm.

Find the lower bound by using the Lower Bound Algorithm.

The weight of the optimum route is: Lower bound ≤ Weight of optimum route ≤ Upper bound

Upper Bound Algorithm (Nearest Neighbour Algorithm)

Choose a starting vertex unless assigned one.

Choose the nearest unused vertex.

Continue until all vertices are visited and return to starting vertex.

Start at A

Total weight = 24

Start at B

Total weight = 20

Start at C

Total weight = 23

Start at D

Total weight = 20

Start at E

Total weight = 23

Lowest upper bound = 20

Lower Bound Algorithm

Choose a vertex unless assigned one.

Find the two lowest weight edges joined to that vertex and note them.

Delete that vertex and all the edges joined to it.

Find the minimum spanning tree for the rest of the network.

Add the minimum spanning trees value to the noted edges to get the total weight.

Delete A

Delete B

Delete C

Delete D

Delete E

Highest lower bound = 18

18 ≤ Weight of Optimum Route ≤ 20

© 2011 Grant Dwyer

Dijkstra's Algorithm

Give the start vertex the permanent label ‘0’.

Find all vertices directly connected to the vertex you have just given a permanent label to.

Give each of these the temporary label.

Temporary label = Permanent label of previous vertex + Weight of arc joining them

If temporary label is already occupied, replace it only if the new value is lower.

The temporary label without a permanent label which has the lowest value is the next permanent label.

Repeat until end vertex has a permanent label.

Find route from start vertex to end vertex.

Order of becoming permanent	Permanent label
Temporary Labels

ABCG is the shortest path.

©2011 Grant Dwyer