AQA D1 Algorithms

FINDS THE SHORTEST PATH BETWEEN ANY TWO VERTICES

1. Label the start vertex with the value 0 (box it)

2. Label all of the vertices directly connected to the start vertex with their working value

Working value= Value at previous vertex + Weight of arc

3. If the new value is lower than one that is already there, replace it

4. Compare all vertice values and box the smallest

5. Repeat until all of the vertices are boxed

6. Trace a route backwards (from the end vetex to the start) to find the shortest path

Route Inspection Problem

Finding the shortest route through a graph that crosses every edge at least once

Eulerian Graph

A trail can be found which travels every edge once only, starting and finishing at the same vertex. All vertices must be even. (Eulerian Cycle)

Semi-eulerian

A trail can be found which travels every edge once only, starting and finishing at different vertices. Exactly two vertices must be odd. (Eulerian Trail)

Non-eulerian

It is not possible to travel every edge once only. More than two vertices are odd. 

Traversable

A path can be found that travels across each edge once only.

Makes a semi/non-eulerian graph, eulerian by making all vertices even.

1. Identify odd ordered vertices

2. Construct pairs

3. Form pairing combinations by finding the shortest route between the vertices

4. Select the pairing of least total weight (if there are more than two odd ordered vertices)

5. Draw in new edges

6. Add this weight to the original network total

7. Find a new route starting and ending at the same vertex

NO. OF POSSIBLE PAIRINGS= (n-1) x (n-2) x (n-3)...x 1

IF YOU CAN START AND FINISH AT DIFFERENT VERTICES THEN 2 VERTICES CAN BE ODD

Hamiltonian Cycle

A cycle through a graph that visits every vertex exactly once and returns to the start vertex.If a graph is complete, a hamiltonian cycle will always be possible- fill in weight of uncomplete edges if necessary.

Number of hamiltonian cycles= [(n-1)!] / 2

Lower Bound ≤ BEST TSP SOLUTION ≤ Upper Bound

Upper bound for TSP= Nearest Neighbour Algorithm

FINDS AN UPPER BOUND FOR TSP PROBLEM

1. Choose a starting vertex

2. Choose the nearest unused vertex/ lowest weight arc (from current vertex)

3. Repeat step 2 until you've visited every vertex

4. Return to the start vertex

CHANGING THE START VERTEX MAY CHANGE THE UPPER BOUND

BEST UPPER BOUND= LOWEST VALUE

1. Find/ select start vertex in 'from' column and circle

2. Find and circle lowest number (in row of selected vertex)

KEEP A TRACK OF THE ROUTE AS YOU GO

3. Cross out column of new letter and circle letter in 'from' column

4. Repeat until all vertices have been visited

5. Return back to the start vertex

On a graph

1. Find/ select start vertex and choose the two lowest weight edges joined to the vertex

2. Delete the start vertex (and all edges joined to it)

3. Find a minimum spanning tree for the rest of the network (Primm's or Kruskal's)

On a matrix

1. Select lowest weight edges from start vertex

1. Delete start vertex (cross out row and column)

2. Use Primm's on a matrix to find a minimum spanning tree for the rest of the graph 

LOWER BOUND= Lowest weight arcs from start vertex + MST