D1 - Algorithms

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)