112Mathematics · University mathematics · Graph theory

Shortest Path: 15 Edges

fx-50FH II · CMPLX · 547 bytes

Find one minimum-cost route through an undirected network of up to ten nodes and 15 edges; display its nodes in order, then its total cost.

  • 547 bytes
  • CMPLX mode
01

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
2 → 3 → 4 → 6; Total cost 4+2+3=9 min
Standard solution (without a calculator)
  1. Apply Dijkstra from S. Below, u is the newly settled node and each d(v) is an updated tentative distance; ∞ means unreachable so far.
  2. u=2, d(2)=0; d(1)=7, d(3)=4
  3. u=3, d(3)=4; d(4)=6, d(5)=12
  4. u=4, d(4)=6; d(6)=9
  5. u=1, d(1)=7; ∅
  6. u=6, d(6)=9; d(5)=11
  7. Backtrack the predecessors and add the route's edge costs: 2 → 3 → 4 → 6; Total cost 4+2+3=9 min
Do it on the calculator

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
7 → 8 → 9 → 1 → 2; Total cost 0+3+1+2=6
Standard solution (without a calculator)
  1. Apply Dijkstra from S. Below, u is the newly settled node and each d(v) is an updated tentative distance; ∞ means unreachable so far.
  2. u=7, d(7)=0; d(1)=9, d(8)=0
  3. u=8, d(8)=0; d(2)=10, d(9)=3
  4. u=9, d(9)=3; d(1)=4, d(2)=7
  5. u=1, d(1)=4; d(2)=6
  6. u=2, d(2)=6; ∅
  7. Backtrack the predecessors and add the route's edge costs: 7 → 8 → 9 → 1 → 2; Total cost 0+3+1+2=6
Do it on the calculator

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 15 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

Answer
1 → 2 → 9 → 10; Total cost 5+1+4=10
Standard solution (without a calculator)
  1. Apply Dijkstra from S. Below, u is the newly settled node and each d(v) is an updated tentative distance; ∞ means unreachable so far.
  2. u=1, d(1)=0; d(2)=5, d(6)=9
  3. u=2, d(2)=5; d(3)=12, d(7)=14, d(9)=6
  4. u=9, d(9)=6; d(4)=15, d(8)=11, d(10)=10
  5. u=6, d(6)=9; d(5)=12
  6. u=10, d(10)=10; ∅
  7. Backtrack the predecessors and add the route's edge costs: 1 → 2 → 9 → 10; Total cost 5+1+4=10
Do it on the calculator
02

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 15 non-loop edges can be stored. Parallel edges each occupy a slot; all costs must use one common unit.
  • This 15-edge version has no complete node-range or integer-cost validator. Enter only supported data. Negative or missing costs and capacity overflow cause Math ERROR. Below capacity, a missing endpoint with a nonnegative cost, or a self-loop, is ignored. Once full, only the two blank prompts finish input.
  • The program uses 547 of the shared 680 bytes, leaving 133 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.

Sign in to unlock the full programme

Checking access…

The programme code and appendix unlock together.

Checking access…

Sign in to unlock the full programme

Checking access…

The programme code and appendix unlock together.