06เส้นทางสั้นที่สุด ไม่ใช่เส้นทางที่ดีที่สุด

import heapq

# ลิงก์ (u, v, ETX) — ค่ามาจากการวัดแบบบทที่ 4
LINKS = [("A","C",2.10), ("C","F",2.10),                    # เส้นตรง 2 hop ผ่านย่านที่คนใช้เยอะ
         ("A","D",1.14), ("D","B",1.20), ("B","F",1.10)]    # เส้นอ้อม 3 hop ลิงก์ดีทุกเส้น

def dijkstra(links, src):
    g = {}
    for u, v, w in links:
        g.setdefault(u, []).append((v, w))
        g.setdefault(v, []).append((u, w))
    dist = {src: 0.0}; prev = {}; pq = [(0.0, src)]
    while pq:
        d, u = heapq.heappop(pq)
        if d > dist.get(u, float("inf")): continue
        for v, w in g.get(u, []):
            nd = d + w
            if nd < dist.get(v, float("inf")):
                dist[v] = nd; prev[v] = u; heapq.heappush(pq, (nd, v))
    return dist, prev

def path(prev, dst):
    out = [dst]
    while dst in prev:
        dst = prev[dst]; out.append(dst)
    return " -> ".join(reversed(out))

dist, prev = dijkstra(LINKS, "A")
best = path(prev, "F"); hops = best.count("->")
short, chosen = (2.10+2.10)*100, dist["F"]*100

print(f"  ถ้านับ hop  : A -> C -> F        2 hop   ETX รวม {2.10+2.10:.2f}")
print(f"  ถ้านับ ETX  : {best}   {hops} hop   ETX รวม {dist['F']:.2f}")
print(f"  ส่ง 100 ชิ้น: เส้น 2 hop = {short:.0f} ครั้ง · เส้น {hops} hop = {chosen:.0f} ครั้ง"
      f"  ประหยัดกว่า {(1-chosen/short)*100:.0f}%")

  ถ้านับ hop  : A -> C -> F        2 hop   ETX รวม 4.20
  ถ้านับ ETX  : A -> D -> B -> F   3 hop   ETX รวม 3.44
  ส่ง 100 ชิ้น: เส้น 2 hop = 420 ครั้ง · เส้น 3 hop = 344 ครั้ง  ประหยัดกว่า 18%