Algorithms on Graphs Flashcards Preview

A Level Further Maths Decision 1 > Algorithms on Graphs > Flashcards

Flashcards in Algorithms on Graphs Deck (18)
Loading flashcards...
1

Minimum spanning tree

A spanning tree such that the total length of its arcs is as small as possible. Can tell you smallest/cheapest/fastest way of linking all nodes

2

What does Kruskal's algorithm do?

Find the minimum spanning tree

3

Kruskal's algorithm

1. Sort the arcs into ascending order of weight
2. Select the arc of least weight to start the tree
3. Consider the next arc of least weight
- if it would form a cycle with the arcs already selected, reject it
- if it does not form a cycle, add it to the tree
4. Repeat step 3 until all vertices are connected

4

Kruskal's algorithm working

Write down edge, tick/cross if used, draw if necessary

5

Kruskal's algorithm advantages and disadvantages

+ easy to follow
- weaker for many edges, difficult to check cycles

6

What does Prim’s algorithm do

Find the minimum spanning tree

7

Prim’s algorithm process

1. Choose any vertex to start the tree
2. Select an arc of least weight that joins a vertex in the tree to a vertex not in the tree and draw and note it down - can choose any if equal
3. Repeat step 2 until all vertices are connected

8

What does Prim’s algorithm do if there are multiple

Gives you a different spanning tree depending on the starting node

9

What else can Prim’s algorithm be used on?

An undirected distance matrix

10

Prim’s algorithm on a distance matrix

1. Choose any vertex to the start the tree
2. Number the column 1 and cross that row
3. Circle the smallest uncrossed value in a numbered column
4. Take the node corresponding to that entry, label it’s column with the next number and delete the row
Repeat until all rows are crossed

11

What does Dijkstra's algorithm do?

Find the shortest path from one node to all the others in a network

12

Dijkstra's Algorithm Table

Vertex | Order of labelling | Final label
Working values

13

Dijkstra's Algorithm Process

Label the start vertex with order 1 and final label 0
Assign a working value to all that can be reached from that vertex of final value of that + distance between, replacing the current value if it is lower
Give the vertex with lowest working label its final label and repeat until the destination vertex has its final label

14

How to find the shortest path from Dijkstra's algorithm?

Trace back from the end vertex, taking paths where the final label of the vertex you are going to is equal to the final label of the current node minus the distance between

15

Floyd’s algorithm setup

1. Complete an initial distance table for the network, with from on the left and to on top. If they aren’t connected by one arc, put an infinity symbol there
2. Complete an initial route table by making every position the same as the label of its column

16

First iteration of Floyd’s algorithm

1. Lightly shade row and column A of the initial distance table in and fill in another distance and route table with row and column A the same
2. For each unshaded position in the new table, replace with the sum of the shaded values it shared a row/column with if it is lower than the present value
3. If you replace them, put the letter of the row and column that are shaded into the route table and box each in square brackets

17

Further iterations of Floyd’s algorithm

Repeat, shading row and column B and so on
Unbox any values that were boxed on the last iteration

18

Finding a route from Floyd’s algorithm

Write down the start and end vertex with a gap in between
Using the final route table use the row of the start and column of the end to see if any nodes are used in between
Repeat this for any routes until all have been checked to be fastest direct