VCE Algorithmics requires detailed knowledge of five key graph algorithms:
| Algorithm | Problem Solved | Graph Type |
|---|---|---|
| Prim’s | Minimum Spanning Tree (MST) | Undirected, weighted |
| Dijkstra’s | Single-source shortest path | Directed/undirected, non-negative weights |
| Bellman-Ford | Single-source shortest path | Directed, allows negative weights |
| Floyd-Warshall | All-pairs shortest path + transitive closure | Directed, weighted |
| PageRank | Vertex importance estimation | Directed (web graph) |
An algorithm specification formally describes:
1. Input: What the algorithm accepts (graph type, constraints)
2. Output: What the algorithm produces
3. Preconditions: What must be true for the algorithm to work correctly
An algorithm is correct if it produces the right output for every valid input. Correctness arguments include:
- Loop invariants (e.g., “at the start of each iteration, all processed vertices have their final shortest distance”)
- Greedy proofs (e.g., prove that the greedy choice never worsens the solution)
- Induction on the number of processed vertices
Limitations describe conditions under which an algorithm fails or becomes inappropriate:
- Dijkstra’s fails with negative-weight edges
- Prim’s requires a connected graph
- Floyd-Warshall has cubic time complexity
KEY TAKEAWAY: For each graph algorithm, know: (1) what problem it solves, (2) what input constraints it requires, (3) why it is correct, and (4) when to use it vs. alternatives.
| Requirement | Algorithm |
|---|---|
| Cheapest network connecting all nodes | Prim’s |
| Shortest path from one source, no negative edges | Dijkstra’s |
| Shortest path, may have negative edges | Bellman-Ford |
| Shortest paths between ALL pairs | Floyd-Warshall |
| Which web pages are most “important”? | PageRank |
| Can I reach every node from every other node? | Floyd-Warshall (transitive closure) |
EXAM TIP: VCAA exams require you to not only apply these algorithms but also justify your choice and describe limitations. Know each algorithm’s preconditions — they are frequently the basis of questions.
