The shortest path was finalised before the rebate

# Self-authored for the EML case corpus (no external origin). A route planner
# finds the cheapest way from A to B by always settling the cheapest unsettled
# point next, and it implements that algorithm exactly. What the algorithm
# assumes about every road, and which road breaks it, is computed below.
#
# The planner is careful. It reads the real cost of every road; it settles
# points strictly in order of cheapest-so-far; once settled a point is never
# revisited, exactly as the algorithm specifies; and the intent is exactly 'the
# cheapest route'.
#
# One road carries a rebate - travelling it pays you back - and the algorithm's
# never-revisit rule assumes no road can lower a cost already settled, so B is
# settled at 5 while the road through C reaches it at 2.

5 => road_a_to_b
10 => road_a_to_c
8 => rebate_on_the_road_c_to_b

road_a_to_b => cost_to_b_when_settled
road_a_to_c - rebate_on_the_road_c_to_b => cost_to_b_via_c
cost_to_b_when_settled - cost_to_b_via_c => overpayment_per_trip
int(overpayment_per_trip * 10000 / cost_to_b_when_settled) => route_overpriced_per_myriad

"road A to B                     : " + str(road_a_to_b) ^0
"road A to C                     : " + str(road_a_to_c) ^0
"road C to B                     : a rebate of " + str(rebate_on_the_road_c_to_b) + " - it pays you" ^0
"" ^0
"settle A at 0; reach B at " + str(road_a_to_b) + ", C at " + str(road_a_to_c) ^0
"settle B next (cheapest)        : " + str(cost_to_b_when_settled) + ", final, never revisited" ^0
"settle C                        : " + str(road_a_to_c) + "; C to B would give " + str(cost_to_b_via_c) + ", but B is final" ^0
"planner's answer for B          : " + str(cost_to_b_when_settled) ^0
"cheapest route to B             : " + str(cost_to_b_via_c) + ", via C" ^0
"overpayment per trip            : " + str(overpayment_per_trip) + ", " + str(route_overpriced_per_myriad) + " per ten thousand" ^0
"" ^0

# ---- what the planner verified ----

"the cheapest-first planner" ^0
"  reads : the real cost of every road" ^0
"  order : strictly cheapest-so-far first" ^0
"  settled points : never revisited, per the algorithm" ^0
"  intent : the cheapest route" ^0
"  steps outside the algorithm : 0" ^0
"  verdict : B SETTLED AT 5" ^0
"" ^0
"  implementing the settle-cheapest-first algorithm exactly" ^0
"  is the part done right here, and it is why the answer is" ^0
"  provably cheapest for every network the algorithm was" ^0
"  written for" ^0
"" ^0

# ---- what the algorithm assumes about roads ----

"the never-revisit rule" ^0
"  why a settled point can be final : any route found later" ^0
"    goes through a point at least as costly, and roads only" ^0
"    add cost" ^0
"  what the rebate road does : subtracts cost" ^0
"  so a route through the costlier C : ends up cheaper than" ^0
"    the direct road, " + str(cost_to_b_via_c) + " against " + str(cost_to_b_when_settled) ^0
"  by the time the planner sees it : B is final and the" ^0
"    cheaper route is discarded" ^0
"" ^0

# ---- what the traveller got ----

"the route" ^0
"  charged : " + str(cost_to_b_when_settled) ^0
"  cheapest available : " + str(cost_to_b_via_c) ^0
"  is the algorithm implemented wrong : no; exactly" ^0
"  is the network one the algorithm was written for : no;" ^0
"    it has a road that pays, and the proof needs none" ^0
"" ^0

# ---- null control ----

# The same network solved with a method that allows a settled point to be
# improved (relax every road repeatedly), which is correct with rebates.
5 => nc_cost_to_b_never_revisit
2 => nc_cost_to_b_relax_repeatedly
3 => nc_overpayment_the_right_method_removes

"null control - use a method that permits improving a settled point" ^0
"  cost to B, never-revisit : " + str(nc_cost_to_b_never_revisit) ^0
"  cost to B, relax repeatedly : " + str(nc_cost_to_b_relax_repeatedly) ^0
"  overpayment the right method removes : " + str(nc_overpayment_the_right_method_removes) ^0
"  no road changed; the planner stopped assuming every road" ^0
"  adds cost" ^0
"" ^0

# ---- the rule ----

"what an exact cheapest-first implementation guarantees" ^0
"  the answer is the cheapest route on any network where" ^0
"    every road adds cost : exactly, the algorithm's own" ^0
"    proof" ^0
"  the answer is the cheapest route on this network : not" ^0
"    addressed; one road is a rebate, the proof's premise" ^0
"    fails, and B is settled at " + str(cost_to_b_when_settled) + " with a " + str(cost_to_b_via_c) + " route through C" ^0
"    still unread" ^0
"" ^0

"an algorithm proven correct is correct on the inputs the proof assumed; a road" ^0
"that pays breaks the one premise the never-revisit rule rests on, and the" ^0
"implementation is exact all the way to a wrong answer" ^0
"" ^0

"It implements settle-cheapest-first exactly - provably right wherever roads" ^0
"only add cost. But the C-to-B road is a rebate of " + str(rebate_on_the_road_c_to_b) + ", so B is settled at " + str(cost_to_b_when_settled) ^0
"and never revisited while the route via C costs " + str(cost_to_b_via_c) + "; the traveller overpays " + str(overpayment_per_trip) + "," ^0
"" + str(route_overpriced_per_myriad) + " per ten thousand, until a method that can improve a settled point is used." ^0

road_a_to_b = 5
road_a_to_c = 10
rebate_on_the_road_c_to_b = 8
cost_to_b_when_settled = road_a_to_b
cost_to_b_via_c = road_a_to_c - rebate_on_the_road_c_to_b
overpayment_per_trip = cost_to_b_when_settled - cost_to_b_via_c
route_overpriced_per_myriad = int(overpayment_per_trip * 10000 / cost_to_b_when_settled)
print("road A to B                     : " + str(road_a_to_b))
print("road A to C                     : " + str(road_a_to_c))
print("road C to B                     : a rebate of " + str(rebate_on_the_road_c_to_b) + " - it pays you")
print("")
print("settle A at 0; reach B at " + str(road_a_to_b) + ", C at " + str(road_a_to_c))
print("settle B next (cheapest)        : " + str(cost_to_b_when_settled) + ", final, never revisited")
print("settle C                        : " + str(road_a_to_c) + "; C to B would give " + str(cost_to_b_via_c) + ", but B is final")
print("planner's answer for B          : " + str(cost_to_b_when_settled))
print("cheapest route to B             : " + str(cost_to_b_via_c) + ", via C")
print("overpayment per trip            : " + str(overpayment_per_trip) + ", " + str(route_overpriced_per_myriad) + " per ten thousand")
print("")
print("the cheapest-first planner")
print("  reads : the real cost of every road")
print("  order : strictly cheapest-so-far first")
print("  settled points : never revisited, per the algorithm")
print("  intent : the cheapest route")
print("  steps outside the algorithm : 0")
print("  verdict : B SETTLED AT 5")
print("")
print("  implementing the settle-cheapest-first algorithm exactly")
print("  is the part done right here, and it is why the answer is")
print("  provably cheapest for every network the algorithm was")
print("  written for")
print("")
print("the never-revisit rule")
print("  why a settled point can be final : any route found later")
print("    goes through a point at least as costly, and roads only")
print("    add cost")
print("  what the rebate road does : subtracts cost")
print("  so a route through the costlier C : ends up cheaper than")
print("    the direct road, " + str(cost_to_b_via_c) + " against " + str(cost_to_b_when_settled))
print("  by the time the planner sees it : B is final and the")
print("    cheaper route is discarded")
print("")
print("the route")
print("  charged : " + str(cost_to_b_when_settled))
print("  cheapest available : " + str(cost_to_b_via_c))
print("  is the algorithm implemented wrong : no; exactly")
print("  is the network one the algorithm was written for : no;")
print("    it has a road that pays, and the proof needs none")
print("")
nc_cost_to_b_never_revisit = 5
nc_cost_to_b_relax_repeatedly = 2
nc_overpayment_the_right_method_removes = 3
print("null control - use a method that permits improving a settled point")
print("  cost to B, never-revisit : " + str(nc_cost_to_b_never_revisit))
print("  cost to B, relax repeatedly : " + str(nc_cost_to_b_relax_repeatedly))
print("  overpayment the right method removes : " + str(nc_overpayment_the_right_method_removes))
print("  no road changed; the planner stopped assuming every road")
print("  adds cost")
print("")
print("what an exact cheapest-first implementation guarantees")
print("  the answer is the cheapest route on any network where")
print("    every road adds cost : exactly, the algorithm's own")
print("    proof")
print("  the answer is the cheapest route on this network : not")
print("    addressed; one road is a rebate, the proof's premise")
print("    fails, and B is settled at " + str(cost_to_b_when_settled) + " with a " + str(cost_to_b_via_c) + " route through C")
print("    still unread")
print("")
print("an algorithm proven correct is correct on the inputs the proof assumed; a road")
print("that pays breaks the one premise the never-revisit rule rests on, and the")
print("implementation is exact all the way to a wrong answer")
print("")
print("It implements settle-cheapest-first exactly - provably right wherever roads")
print("only add cost. But the C-to-B road is a rebate of " + str(rebate_on_the_road_c_to_b) + ", so B is settled at " + str(cost_to_b_when_settled))
print("and never revisited while the route via C costs " + str(cost_to_b_via_c) + "; the traveller overpays " + str(overpayment_per_trip) + ",")
print("" + str(route_overpriced_per_myriad) + " per ten thousand, until a method that can improve a settled point is used.")

road A to B                     : 5
road A to C                     : 10
road C to B                     : a rebate of 8 - it pays you

settle A at 0; reach B at 5, C at 10
settle B next (cheapest)        : 5, final, never revisited
settle C                        : 10; C to B would give 2, but B is final
planner's answer for B          : 5
cheapest route to B             : 2, via C
overpayment per trip            : 3, 6000 per ten thousand

the cheapest-first planner
  reads : the real cost of every road
  order : strictly cheapest-so-far first
  settled points : never revisited, per the algorithm
  intent : the cheapest route
  steps outside the algorithm : 0
  verdict : B SETTLED AT 5

  implementing the settle-cheapest-first algorithm exactly
  is the part done right here, and it is why the answer is
  provably cheapest for every network the algorithm was
  written for

the never-revisit rule
  why a settled point can be final : any route found later
    goes through a point at least as costly, and roads only
    add cost
  what the rebate road does : subtracts cost
  so a route through the costlier C : ends up cheaper than
    the direct road, 2 against 5
  by the time the planner sees it : B is final and the
    cheaper route is discarded

the route
  charged : 5
  cheapest available : 2
  is the algorithm implemented wrong : no; exactly
  is the network one the algorithm was written for : no;
    it has a road that pays, and the proof needs none

null control - use a method that permits improving a settled point
  cost to B, never-revisit : 5
  cost to B, relax repeatedly : 2
  overpayment the right method removes : 3
  no road changed; the planner stopped assuming every road
  adds cost

what an exact cheapest-first implementation guarantees
  the answer is the cheapest route on any network where
    every road adds cost : exactly, the algorithm's own
    proof
  the answer is the cheapest route on this network : not
    addressed; one road is a rebate, the proof's premise
    fails, and B is settled at 5 with a 2 route through C
    still unread

an algorithm proven correct is correct on the inputs the proof assumed; a road
that pays breaks the one premise the never-revisit rule rests on, and the
implementation is exact all the way to a wrong answer

It implements settle-cheapest-first exactly - provably right wherever roads
only add cost. But the C-to-B road is a rebate of 8, so B is settled at 5
and never revisited while the route via C costs 2; the traveller overpays 3,
6000 per ten thousand, until a method that can improve a settled point is used.

Trace event types