Chinese Postman Problem
AKA: Route Inspection
Agorithm used for: Finding the shortest route which travels along all the edges of a graph
Valency: Number of edges connected to a vertex
Traversable: A route can be found that travels along all the edges of a graph without repetition
of vertices (All valencies are even)
Semi- traversable: A route can be found that travels along all the edge of a graph by repeating
the shortest route between a pair of vertices with odd valency (Has two odd valencies)
Start and finish at A: If graph has odd valencies, repeat shortest path between pairs.
Start at A, finish at B: Start and finish at vertices with odd valencies.
Algorithm used for: Finding the shortest path between two vertices
Method: From the starting vertex labelled 1, choose the edge wth least weight connected to it.
Label it 2, continue this process including edges connected to all the vertices labelled, until you
reach the finishing vertex.
Shortest path: Start from the finishing vertex, find the path by checking each vertex. Minus the
edge weight from the finished weight to equal the starting weight.
Weight of the path: This will be the total distance at the finishing vertex.
Path between two other vertices: Use the shortest path and divert to the other vertex.
Algorithm used for: Finding the minimum spanning tree of a graph
Method: From a starting vertex, choose the shortest edge connected. Like Dijkstra's, include
all connected edges to all the vertices used when choosing the shortest.
Distance matrix: Use Prim's on a distance matrix, labelling columns 1,2, 3 as you go and
crossing off the rows used.
Algorithm used for: Finding a minimum spanning tree of a graph.
Method: Order the arcs in ascending order. Use this list and either select or reject arcs to use.
(Reject arcs that form cycles)