รุ่นแก้ไขเมื่อ 07:08, 29 สิงหาคม 2553

จดบันทึกคำบรรยายโดย:

5314550032 นาย กิตติกานต์ ดวงประภา

5314550041 นาย เกียรติชุมพล สุทธิศิริกุล

5314550059 นาย ฉนานนท์ ตันสกุล

Shortest Paths

มี G = (v,E) โดยที่ n = |v|

มี l : E -> R โดยที่ m = |E|

ให้ d(u) สำหรับ u ใดๆ แทนระยะทางที่สั้นที่สุดจาก s ไป u

Lemma: ให้ d_t(s,v) เป็นระยะทางจาก s ไป v บน T , T จะเป็น shortest path tree ก็ต่อเมื่อ(if and only if) สำหรับทุกๆ เส้นเชื่อม (u,v) ∈ E

d_T(s,u) + l(u,v) ≥ d_T(s,v)

@@ แถว 6: / แถว 6: @@
 5314550059  นาย ฉนานนท์  ตันสกุล
+=Shortest Paths=
+มี G = (v,E)  โดยที่  n = |v|
+มี l : E -> R  โดยที่ m = |E|
+ให้ d(u) สำหรับ u ใดๆ แทนระยะทางที่สั้นที่สุดจาก s ไป u
+'''Lemma:''' ให้ d_t(s,v) เป็นระยะทางจาก s ไป v บน T ,  T จะเป็น shortest path tree ก็ต่อเมื่อ(if and only if) สำหรับทุกๆ เส้นเชื่อม  (u,v) &isin; E
+d_T(s,u) + l(u,v) &ge; d_T(s,v)