Network Algorithms Flashcards
What are the six steps to Prims algorithm (graphically) ?
What are some common errors in doing prims algorithm graphically?
- not starting from specific node given in the question
- forming a cycle by accident
- not looking at all the connected vertices
- not showing working out of each edge
- not stating the total weight
What are the steps to Prims algorithm (tabular)?
What are some common errors when doing Prims Algorithm (tabular)
- not deleting a row
- not looking down on all the avaible rows
- not recording edges and weights
- not showing working out
- not stating the total weight of MST
What is a greedy algorithm?
it maximises the immediate rewards without considering future choices/consequences
Why are the steps for carrying out Kruskal’s algorithm?
What are the common errors in kruskals algorithm?
- not listing the order of arcs
- accidentally forming cycles (constnatly look at the graph)
Why can kruskals algorithm not be used in tabular form?
no way of knowing when cycle will be made
∴ cannot be used by computers
what is a common mistake in dijkstras?
not starting the order of becoming permenant from 1
this is dijkstras not critical path
What are the steps for Dijkstra’s algorithm?
How would you find the shortest route and length from this completed
what is the complexity of kruksals, primms and dijksras?
O (n^^2)
* Dijkstra’s is as a function of number of vertices
* Primms/ Kruksals is a function of the number of edges
What is the shortest distance from A-E and A-F
