Algorithms on networks Flashcards
What does Kruskal’s algorithm do?
It finds the minimum spanning tree
What is a minimum spanning tree?
A spanning tree such that the total length of its edges is as small as possible
Explain Kruskal’s algorithm
Sort all of the edges into ascending order of weight. For each edge, if it would not form a cycle with the already selected edges, add it to the tree. Otherwise, reject it. Repeat this until all vertices are connected
What does Prim’s algorithm do?
It finds the minimum spanning tree
Explain Prim’s algorithm
Choose any vertex to start the tree. Then select the edge of least weight that joins a vertex that is already in the tree to a vertex that is not yet in the tree (if there are multiple to choose from, pick randomly). Repeat this until all vertices are connected
Explain how Prim’s algorithm can be used with matrices
Choose any vertex to start the tree. Delete the vertex’s row, and number its column. Then, until all rows have been deleted, circle the lowest undeleted entry in any of the numbered columns, delete its row and numbers its column. Once this has been completed, the circled entries will be the edges of the minimum spanning tree
What does Dijkstra’s algorithm do?
Finds the shortest route between two vertices
Explain Dijkstra’s algorithm
Label the start vertex’s final value as 0. Then, until the end vertex receives its final value: for every vertex Y that is joined to the vertex X that has just received its final value, if X’s final value + length of XY < Y’s current working value, update Y’s current working value. Once all vertices joined to X have been considered, the vertex with the lowest working value has its final value set to its working value. When the end vertex receives its final value, a backtrace is performed; starting at the end vertex, and letting B equal the last chosen vertex, include edge AB whenever B’s final value - length of AB = A’s final value. The edges produced by this form the shortest path
