Decision - Algorithms on Graphs Flashcards
What is a MST?
Minimum spanning tree
A MST is a spanning tree such that the total lengths of all its arcs is as small as possible
What are the 4 algorithms you need to know?
Kruskal’s
Prim’s
Dijkstra’s
Floyd’s
What is a tree?
A tree is a connected graph with no cycles
What is a spanning tree?
A spanning tree of a graph, G, is a subgraph which includes all the vertices of G and is also a tree
What is a MST sometimes called?
A minimum connector
State Kruskal’s algorithm?
What can Kruskal’s algorithm be used for?
Finding the MST
What is counter intuitive when using Kruskal’s algorithm?
It may grow as 2 unconnected graphs but it will always finish as 1 connected spanning tree
What can Prim’s algorithm be used for?
Finding the MST
State Prim’s algorithm?
What is the main difference between Kruskal’s algorithm and Prim’s algorithm?
The difference between Prim’s and Kruskal’s algorithm is that Prim’s algorithm considers vertices whereas Krukal’s algorithm considers edges
What 2 versions of Prim’s algorithm do you need to know?
A normal graph version and a distance matrix version
State the distance matrix form of Prim’s algorithm?
When using the distance matrix form Prim’s algorithm what workings out do you need to show?
The final annotated table
Plus
A list of arcs in the correct order
What is a practical application of Dijkstra’s algorithm?
Finding the cheapest or fastest way to transport goods
What can Dijkstra’s algorithm be used to find?
(In terms of graph theory)
Dijkstra’s algorithm can be used to find the shortest path through S and T through a network
How do you pronounce Dijkstra?
Dike-Stra
State Dijkstra’s algorithm?
What are the required workings out when using Dijkstra’s algorithm?
you only need 1 completed diagram with the answer stated at the end
The order of the working list needs to be correct
What are working labels often called?
Temporary labels
What are final labels often called?
Permeant labels
What is the correct notation to use when using Dijkstra’s algorithm?
What is the correct notation to use when using Dijkstra’s algorithm?
What is the correct notation to use when using Dijkstra’s algorithm?
What is the 1st key observation about Dijkstra’s algorithm?
You can use Dijkstra’s algorithm to work out the shortest route between the start vertex and any other vertex with a final label
What is 1 major implication of the 1st observation about Dijkstra’s algorithm?
If you have a completed diagram Dijkstra’s algorithm can work out the shortest route between the start variable and any other
What is 1 generalisation you can apply to Dijkstra’s algorithm?
What is this the equivalent of in the real world?
It can be used with directed graphs (just don’t go the wrong way down an arrow)
1 way roads
What can Floyd’s algorithm be used to do?
Find the shortest path between any 2 vertices in a network
State Floyd’s algorithm?
Once you have a completed route table how do you find the shortest route?
To find the quickest route between C and D you need to: look at row C and column D the letter that is in that stop is the vertex that you need to go to get from C to D. But you then need to check the quickest route from that new vertex (B) to D by doing the same process of looking at row C and column B and so on until that value is D
(You need to write the numbers from the right to the left.
Once you have a completed distance table how do you find the weight of the shortest route?
The corresponding entry in the final distance table will tell you the distance between the 2 routes
What is a distance table?
It is essentially a distance table but with infinity signs where there would normally be dashes (except down the leading diagonal
What will the initial route table look like?
How can highlighting be done in exams?
Circling the row and column that needs to be highlighted
What is step 1 of Floyd’s algorithm?
1) Complete an initial distance table for the network
If there is no direct route from one vertex to another use a infinity sign
What is step 2 of Floyd’s algorithm?
2) Complete an initial route table by making every element in the 1st column the same
as the label at the top of the column and then doing the same thing for each
subsequent column
What is step 3 of Floyd’s algorithm?
3) In the first iteration, copy the first row and first column values of the distance table
into a new table as well as all the dashes – highlight these columns and rows
What is step 4 of Floyd’s algorithm?
What is step 5 of Floyd’s algorithm?
5) For the second iteration copy the second row and column from the last iteration into a new distance table whilst highlighting these values
What is step 6 of Floyd’s algorithm?
6) Repeat step 4 with the new unshaded positions but this time any change will result in a detour through B so you should write B in the new route table when necessary
What is step 7 of Floyd’s algorithm?
7) If there are n vertices then the algorithm will require n iterations
What is step 1 of Dijkstra’s algorithm?
What is step 2 of Dijkstra’s algorithm?
What is step 3 of Dijkstra’s algorithm?
What is step 5 of Dijkstra’s algorithm?
