What do you use Djjkstra’s algorithm for
To find the shortest distance between two points
What are minimal spanning trees
They are trees of minimum weight required to connect all vertices of a network
What is krusksals algorithm used for
Finding minimal spanning trees on a network
What is prims algorithm used for
Finding the minimal spanning tree on a network and also on an adjacency matrix
What is Kruskal’s algorithm
find all of the shortest edges that are present in a network and do so so that all nodes are connected and no cycles are created
How is prims algorithm done on a network
Find the shortest edge connected to a point, then find the shortest edge connected to either of those two points without creating a cycle and repeat
How is prims algorithm done on an adjacency matrix
Cross through the entries in the starting row, and mark the column 1.
Choose a minimum entry that is uncircled in a mark column
Repeat first step
Until there are no longer any weights to choose
What is the order of prims and kruskal’s algorithm
O(N^3)
What is the order of djjkstras algorithm
O(n^2)
How do you find the upper bound for a least weight cycle
Using the neareast neighbour method
How do you find the lower bound for a least weight cycle
You remove a given vertex and all arcs that are directly connected to that vertex.
Find the minimum spanning tree for the reduced network
Add the weight of this minimum connector to the two least weight arcs that had been deleted
What is used for the least weight route using every arc
The route inspection algorithm
If the graph is eulerian in a least weight arc problem what can be done
There is a closed path that uses every arc once so that’s the solution
What is the route inspection algorithm
Start with a list of the odd degree vertices
For each pair of odd nodes, find the connecting path of least weight
Group the odd nodes so that the sum of weights of the connecting paths is minimised
Add this sum to the total weight of the graph
