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