Chapter 3: Algorithms on Graphs

Question 1

What is a minimum spanning tree?

Answer 1

A spanning tree such that the total length of its arcs is as small as possible

Question 2

What algorithms can you use to find a minimum spanning tree?

Answer 2

1) Kruskal’s Algorithm

2) Prim’s Algorithm

Question 3

How do you apply Kruskal’s algorithm?

Answer 3

KRUSKAL’S ALGORITHM CONSIDERS EDGES

1) Sort all edges into ascending order of weight. Choose the arc of least weight to be your first arc
2) Consider the next arc of least weight: if it can be joined without forming a cycle, add it to your tree
3) Repeat this until all vertices are connected

Question 4

How do you apply Prim’s algorithm?

Answer 4

PRIM’S ALGORITHM FOCUSES ON VERTICES AND CAN BE FASTER, ESPECIALLY IS EDGE:VERTEX RATIO IS HIGH

1) Choose any vertex to start the tree
2) Select the arc of least weight that isn’t already connected to a vertex in your tree but comes from a vertex already in the tree
3) Continue until all vertices are connected to your tree

Question 5

How to apply Prim’s algorithm to a distance matrix?

Answer 5

1) Choose any vertex to start the tree and delete the row that your chosen vertex is in and number the column that the vertex is in
2) Look at the numbered column and circle the edge with the lowest weight - this arc is now added to your tree
3) Delete the row that the ringed vertex is in and number the column that the vertex is in
4) Now look at both numbered columns and choose the lowest weighted arc
5) Repeat this until all rows have been deleted

Question 6

How to apply Prim’s algorithm to a distance matrix?

Answer 6

1) Choose any vertex to start the tree and delete the row that your chosen vertex is in and number the column that the vertex is in
2) Look at the numbered column and circle the edge with the lowest weight - this arc is now added to your tree
3) Delete the row that the ringed vertex is in and number the column that the vertex is in
4) Now look at both numbered columns and choose the lowest weighted arc
5) Repeat this until all rows have been deleted

Question 7

What can Dijkstra’s algorithm be used for

Answer 7

Dijkstra’s algorithm can be used to find the shortest path between two vertices

Question 8

What does the box for each vertex in Dijkstra’s algorithm represent?

Answer 8

Each vertex with have a box with two rows and in the first row there are 3 columns.

Column one has the vertex letter
Column two has the order of the vertices in the path, so the starting vertex will have 1 in this box
Column three has the total weight of the path so far, so the starting verte will have 0 in this box

Row two is where you record the working value for total weight of the path and the smallest value in this box is chosen to be put in the third column

Question 9

How do we apply Dijkstra’s algorithm?

Answer 9

1) Label the start vertex with label 0
2) Record a working value at every vertex. Working value = final label at vertex before + weight of arc. Choose the next vertex that has lowest final label to be part of your path
3) Only replace the working value if the new value is smaller. The smallest value is chosen to be the final label of the vertex - once a vertex has a final label, it isn’t revisited. Choose the next vertex that has lowest final label to be part of your path
4) Repeat this for all vertices until we have reached the destination vertex
5) To find the shortest path, trace back from the final vertex to the starting vertex to make sure it fits. The opposite of this is the shortest path from start vertex to final vertex