Student Name: Sristi Fulsunge Student ID: 130490344 Course: CS 460 – Algorithms | Spring 2026
-
Why a single shortest-path run from S is not enough: A single shortest-path run from S is not enough as dijkstras gives us the shortest path one from node to all other nodes. It does not tell us from which relic to pick first, second, etc. It does not give us the order of the relics.
-
What decision remains after all inter-location costs are known: Once we run dijsktras on all nodes to figure out the shortest path from any relic to any relic, we still need to know which path allows us to use the cheapest travel fuel. The order still remains unknown after all inter-location costs are known.
-
Why this requires a search over orders (one sentence): This still requires a search over orders as we need to figure out which is the shortest path we can choose among all the paths possible.
| Source Node Type | Why it is a source |
|---|---|
| S | The problem requires us to find the shorted path from the entrance S to all nodes |
| {R1, R2, ..., Rk} | We are required to find the shiortest path from all relics to each and every relic in order |
| Property | Your answer |
|---|---|
| Data structure name | Dictionary |
| What the keys represent | Source Node(S) or Relics(R1, R2, ..., Rk) |
| What the values represent | Another dictionary with it's key-value pair representing the destination source with distance |
| Lookup time complexity | O(1) |
| Why O(1) lookup is possible | The dictionary here represents a hash map that allows constant time lookup |
- Number of Dijkstra runs: K+1
- Cost per run: O(mlogn)
- Total complexity: O((K+1)mlog(n))
- Justification (one line): We run dijkstras on the source node S and for each k relics.
-
For nodes already finalized (in S): The shortest distances from source to these nodes have been finalised.
-
For nodes not yet finalized (not in S): The current distance stored is the shortest path known so far, but a more optimal path might occur later.
-
Initialization : why the invariant holds before iteration 1: At the initial step the distance from the source to all different points is infinite (or a very large number), as no path is found yet. The distance stored for source is 0. The loop starts correctly.
-
Maintenance : why finalizing the min-dist node is always correct: While running the loop, either the minimum distance has already been found, or the shortest path has not been found yet. The nodes having the smallest distance is finalised as no further shortest path exists in later runs.
-
Termination : what the invariant guarantees when the algorithm ends: All nodes have their correct shortest distance from the source. The loop ends correctly.
The route planner gives us the correct shortest distance, that can be used later to find the order of the relics to find the most efficient path.
- The failure mode: Greedy always picks the shortest distance locally, but this could lead to a higher total cost. However, there could be a better, more optimal path in later steps.
- Counter-example setup: Taking another graph as an example S-->A (cost = 1), S --> B(cost 2), A-->B (cost 100), A-->T(cost 1), B-->A(cost 1), B-->T(Cost 1). Greedy always picks the locally most optimal path. Greedy picks S-->A-->B-->T and gives us a total cost of 102, while we could pick S-->B-->A-->T giving us a total cost of 4.
- What greedy picks: The shortest path known locally, i.e. from S to B
- What optimal picks: Could pick S to C that could lead to a cheaper overall cost.
- Why greedy loses: Choosing the closest relic first could lead to future expensive paths, while a slightly more expensive path at the first step could lead to a more cheaper path.
- The algorithm must explore all possible different combinations/orders to evaluate the minimum cost path that explores all relics from a given starting positon to end position.
| Component | Variable name in code | Data type | Description |
|---|---|---|---|
| Current location | current_loc | charectar | The node where the Torchbearer is at |
| Relics already collected | relics_collected | Set | The relics that have already been visited |
| Fuel cost so far | cost_so_far | int | The total fuel cost accumalted so far |
| Property | Your answer |
|---|---|
| Data structure chosen | Set |
| Operation: check if relic already collected | Time complexity: O(1) |
| Operation: mark a relic as collected | Time complexity: O(1) |
| Operation: unmark a relic (backtrack) | Time complexity: O(1) |
| Why this structure fits | A set allows us to easy add, remove and checks relics during backtracking. Sets in python are implemented using hashmaps, which is why the time complexity is O(1) |
- Worst-case number of orders considered: k!
- Why: It evalautes every single possible order of combinations for k relics.
- What is tracked: The best total fuel accumalated so far for a complete route starting from S, through all relics, to T.
- When it is used: It is used during the recurssive step when the current path cost is compared to the best route already found.
- What it allows the algorithm to skip: It allows the algorithm to skip when any path computed is more expensive than the best complete route.
- What information is available at the current state: The algorithm knows the current location , relics visited and unvisited so far and the total fuel cost.
- What the lower bound accounts for: The lower bound accounts for the minimum extra fuel still needed to visit all the relics and still reach the end.
- Why it never overestimates: We take the cheapest path possible, so our estimate is always lower or equal to the actual cost.
- This way we are evaluating all the paths possible that include all relic, and discard those whose current cost plus remaining cost is more than the minimum fuel evalauted so far.
- lecture notes