รุ่นแก้ไขเมื่อ 07:36, 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) $\in$ E

$d_{T}(s,u)+l(u,v)\geq d_{T}(s,v)$

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