Ordinary Level Applied Maths

Algorithms, Optimisation & Project Scheduling

8 Steps · all open

Start at Step 1
  1. Step 1OpenTrees & Spanning TreesA tree is connected and has no cycles, and a spanning tree connects every vertex of the original graph.
  2. Step 2OpenMinimum Spanning TreesA minimum spanning tree connects every vertex without a cycle while minimising the total edge weight.
  3. Step 3Full accessKruskal's AlgorithmKruskal's algorithm builds a minimum spanning tree by considering edges in increasing weight order and accepting only those that do not form a cycle.
  4. Step 4Full accessPrim's AlgorithmPrim's algorithm grows one tree by repeatedly choosing the cheapest edge joining a vertex already in the tree to a new vertex.
  5. Step 5Full accessDijkstra's Shortest-Path AlgorithmDijkstra's algorithm finds shortest paths from a starting vertex by making the smallest temporary distance permanent and updating neighbouring distances.
  6. Step 6Full accessBellman's Principle & Dynamic ProgrammingBellman's principle finds the best route by combining each next-edge cost with the best remaining cost from its destination.
  7. Step 7Full accessChoosing, Comparing & Justifying AlgorithmsChoose an algorithm by deciding whether the aim is a cheapest connected network or a shortest route.
  8. Step 8Full accessProject Scheduling — Critical Path, Early/Late Times & FloatA project network uses activity dependencies to find early and late times, float and the critical path that determines the shortest completion time.