AQA D1 Algorithms

HideShow resource information

Dijkstra's Algorithm

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

1 of 7

Route Inspection Theory

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.

2 of 7

Chinese Postman

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

3 of 7

Travelling Salesperson Theory

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

4 of 7

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

5 of 7

Nearest Neighbour Algorithm on a Matrix

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

6 of 7

Lower Bound Algorithm

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

7 of 7

Comments

No comments have yet been made

Similar Mathematics resources:

See all Mathematics resources »See all Networks, algorithms and problem solving resources »