UCT CSC2001 / 2023
Inside a shortest-path search
Generated weighted graphs and instrumented Dijkstra to count vertex and edge processing.
UCT / COURSE CONTEXT / 2023
CSC2001F · Computer Science 2001
Data structures, graph algorithms and relational database design; practical Java programming.
2026 PORTFOLIO RECREATIONS
Shortest paths, step by step
Initialise A at distance 0.
| Node | Distance | Predecessor | State |
|---|---|---|---|
| A | 0 | — | Unsettled |
| B | ∞ | — | Unsettled |
| C | ∞ | — | Unsettled |
| D | ∞ | — | Unsettled |
| E | ∞ | — | Unsettled |
Path to E: unreachable so far · Tentative / not settled
New granular browser trace of a directed, non-negative example graph. Final distances are checked against all five source-executed Java traces. Cyan: tentative path; magenta: inspected edge; green: settled. Only a settled destination has a final distance.
ENGINEERING PERSPECTIVE
Inside the work
Investigate how a shortest-path algorithm processes a weighted graph. Instrumentation makes the relationship between reachability, edge work and priority-queue behaviour visible instead of treating a complexity formula as a benchmark.
- Java / priority queue
- Run the supplied binary-heap Dijkstra implementation with added processing counters.
- GraphExperiment / CSV
- Generate graph inputs and record vertex/edge-processing counts.
Initialise distances
Give the source distance zero and all other vertices an initially unknown/infinite distance.
- Relaxation
- An outgoing edge improves a neighbour when the current distance plus its weight is smaller.
- Nonnegative weights
- The demonstrated shortest-path logic depends on this Dijkstra precondition.
- Operation counts vs time
- Edge counts alone do not measure heap work, elapsed time or efficiency relative to asymptotic bounds.
What the demonstration establishes
The interactive trace comes from a new instrumented five-vertex example. It shows distance updates and final paths, not a historical GUI or a universal performance claim.
Evidence behind this page
Named report, GraphExperiment source, attributed graph framework and retained count results.
How it works
Generate edge records, construct a directed graph and run binary-heap priority-queue Dijkstra from the first source vertex. Increment counters when processing vertices and outgoing edges, then append CSV-formatted experiment rows.
Results & recovery
- The six source classes compile; the original experiment completed all 25 input-size combinations.
- An additional instrumented copy produced the interactive trace below on a new five-vertex example, with final distances A=0, B=3, C=1, D=4, E=7.
Technical limitations
The report misinterprets operation-count ratios as efficiency relative to asymptotic bounds. The generator permits parallel endpoints with different weights and is unseeded. Reachability affects processed counts. The demonstration is new documentation, not a historical GUI.
What I would improve now
Seed generation, control connectivity and parallel edges, repeat each workload and distinguish operation counts from heap-dependent time complexity.