Decision 3 - Algorithms on Graphs Flashcards
What is Kruskal’s algorithm?
Kruskal’s algorithm can be used to find a minimum spanning tree:
1) Sort all the arcs (edges) into ascending order of weight.
2) Select the arc of the 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 doesn’t form a cycle, add it to the tree.
•If there is a choice of equal arcs, consider each in turn.
4) Repeat step 3 until all vertices are connected.
What is Prim’s algorithm.
Prim’s algorithm can be used to find a minimum spanning tree:
1) Choose any vertex to start the tree.
2) Select an arc of least weight that joins a vertex already in the tree to a vertex not yet in the tree.
•If there is a choice of arcs of equal weight, choose any of them.
3) Repeat step 2 until all the vertices are connected.
What is the difference between Kruskal’s and Prim’s algorithm?
Prim’s algorithm considers vertices, whereas Kruskal’s algorithm considers edges.
How would you apply Prim’s algorithm to a distance matrix?
The distance matrix form of Prim’s algorithm is:
1) Choose any vertex to start the tree.
2) Delete the row in the matrix for the chosen vertex.
3) Number the column in the matrix for the chosen vertex.
4) Put a ring round the lowest undeleted entry in the numbered columns.
•If there is an equal choice, choose randomly.
5) The ringed entry becomes the next arc to be added to the tree.
6) Repeat steps 2-5 until all rows have been deleted.
What is Dijkstra’s algorithm?
Dijkstra’s algorithm can be used to find the shortest path from S to T through a network:
1) Label the start vertex, S, with the final label, 0.
2) Record a working value at every working value at every vertex, Y, that is directly connected to the vertex that has just received it’s final label, X.
•Working value at Y= final label at X+weight of arc XY.
•If there is already a working value at Y it is only replaced if the new value is smaller.
•Once a vertex has received a final label, it is not revisited and its working values are no longer considered.
3) Look at the working values at all vertices without final labels. Select the smallest working value. This now becomes the final label at that vertex. (If two vertices have the same smallest working value, either may be given its final label first).
4) Repeat steps 2 and 3 until the destination vertex T receives its final label.
5) To find the shortest path, trace back from T to S. Given that B already lies on the route, include arc AB whenever: final label of B-final label of A=weight of arc AB.
You can also use Dijkstra’s algorithm to find the shortest route between the start vertex and any other vertex with a final label, this also works for networks with directed arcs, they must be treated like one way roads.
Describe Floyd’s algorithm.
Floyd’s algorithm can be used to find the shortest path between every pair of vertices in a network:
1) Complete an initial distance table for the network. If there is no direct route from one vertex to another, label the distance with the infinity symbol.
2) Complete an initial route table by making every entry in the first column the same as the label at the top of the first column, making every entry in the second column the same as the label at the top of the second column and so on.
3) In the first iteration, copy the first row and the first column values of the distance table into a new table. Lightly shade these values.
4) Consider each unshaded position in turn. Compare the value in this position in the previous table with the sum of the corresponding shaded values.
If X+Y≥Z then copy Z into the new table.
If X+Y
