Shortest Path: 20 Edges
fx-50FH II · CMPLX · 637 bytes
Find one minimum-cost route through an undirected network of up to ten nodes and 20 edges; display its nodes in order, then its total cost.
- 637 bytes
- CMPLX mode
Worked examples
Example 1
Original university operations-research exercise: a museum robot moves through numbered galleries. Listed connections are two-way and their costs are minutes. Find a minimum-time route from 2 to 6 and its total time.
All listed links are undirected; unlisted links do not exist. Edge list (a–b: cost): 2–1: 7; 2–3: 4; 1–4: 5; 3–4: 2; 3–5: 8; 4–6: 3; 5–6: 2; 1–5: 12
Answer
Standard solution (without a calculator)
- Apply Dijkstra from S. Below, u is the newly settled node and each d(v) is an updated tentative distance; ∞ means unreachable so far.
- u=2, d(2)=0; d(1)=7, d(3)=4
- u=3, d(3)=4; d(4)=6, d(5)=12
- u=4, d(4)=6; d(6)=9
- u=1, d(1)=7; ∅
- u=6, d(6)=9; d(5)=11
- Backtrack the predecessors and add the route's edge costs: 2 → 3 → 4 → 6; Total cost 4+2+3=9 min
Example 2
Original university operations-research exercise: an exhibition shuttle network uses integer fare units. The 7–8 connection is free, with cost exactly 0. Find a minimum-fare route from 7 to 2 and its total fare.
All listed links are undirected; unlisted links do not exist. Edge list (a–b: cost): 7–8: 0; 8–9: 3; 9–2: 4; 7–1: 9; 1–2: 2; 8–2: 10; 9–1: 1
Answer
Standard solution (without a calculator)
- Apply Dijkstra from S. Below, u is the newly settled node and each d(v) is an updated tentative distance; ∞ means unreachable so far.
- u=7, d(7)=0; d(1)=9, d(8)=0
- u=8, d(8)=0; d(2)=10, d(9)=3
- u=9, d(9)=3; d(1)=4, d(2)=7
- u=1, d(1)=4; d(2)=6
- u=2, d(2)=6; ∅
- Backtrack the predecessors and add the route's edge costs: 7 → 8 → 9 → 1 → 2; Total cost 0+3+1+2=6
Example 3
Original university operations-research exercise: a training communication network links ten virtual terminals. Every two-way link has a fixed integer transmission cost. Enter all 20 links in the listed order and find a minimum-cost route from 1 to 10, including the last links.
All listed links are undirected; unlisted links do not exist. Edge list (a–b: cost): 1–2: 5; 2–3: 7; 3–4: 4; 4–5: 6; 5–6: 3; 6–7: 8; 7–8: 2; 8–9: 5; 9–10: 4; 1–6: 9; 2–7: 9; 3–8: 9; 4–9: 9; 5–10: 9; 2–9: 1; 1–4: 1; 4–7: 1; 7–10: 1; 1–8: 9; 3–10: 8
Answer
Standard solution (without a calculator)
- Apply Dijkstra from S. Below, u is the newly settled node and each d(v) is an updated tentative distance; ∞ means unreachable so far.
- u=1, d(1)=0; d(2)=5, d(4)=1, d(6)=9, d(8)=9
- u=4, d(4)=1; d(3)=5, d(5)=7, d(7)=2, d(9)=10
- u=7, d(7)=2; d(8)=4, d(10)=3
- u=10, d(10)=3; d(9)=7
- Backtrack the predecessors and add the route's edge costs: 1 → 4 → 7 → 10; Total cost 1+1+1=3
When to use it
University mathematics · operations research. Use a fixed network with nonnegative additive costs. This is a graph algorithm exercise; no physical direction or travel conditions are inferred.
Enter the network
- At the first Y?, enter S+Ti: S is the starting node and T the destination. Then alternate Y? = a+bi for an undirected edge and M? = its cost. Use ENG for i. Do not enter a node count or edge count.
- Finish at the next Y? with EXE alone, then at M? with EXE alone. These are two different prompts. Enter a known zero cost as 0EXE.
Read the route and cost
- Each Disp screen is one route node, starting at S. Press EXE after every node, including T, to reach the final cost. −1 means no route. When S=T, the output is S then 0. Leave the final screen with AC; EXE runs the program again.
Conditions and limits
- Use integer node labels 1–10 and integer edge costs 0–100. At most 20 non-loop edges can be stored. Parallel edges each occupy a slot; all costs must use one common unit.
- This 20-edge version checks integer endpoints, costs and ranges. A single missing field, invalid value or extra edge causes Math ERROR. A valid self-loop is ignored below capacity; once full, only the two blank prompts finish input.
- The program uses 637 of the shared 680 bytes, leaving 43 bytes for other slots. It clears A, B, C, D, X, Y, M and Ans at every run; back up values first.
- Create and run as CMPLX, with a+bi and Norm 1. The examples use Deg and P1. Normal completion restores Norm 1; the input i encodes two integer labels, not an imaginary cost.
- Directed links, negative weights and more than ten nodes are unsupported. Equal-cost routes may exist: only one is returned, with no promise of the fewest edges. Use the exact source; the compact encoding has a narrow finite-precision margin.
Checking access…