ผลต่างระหว่างรุ่นของ "204512-53/lecture7"
ไปยังการนำทาง
ไปยังการค้นหา
Kiatchumpol (คุย | มีส่วนร่วม) |
Kiatchumpol (คุย | มีส่วนร่วม) |
||
| แถว 17: | แถว 17: | ||
ให้ <math>d(u)</math> สำหรับ u ใดๆ แทนระยะทางที่สั้นที่สุดจาก s ไป u | ให้ <math>d(u)</math> สำหรับ u ใดๆ แทนระยะทางที่สั้นที่สุดจาก s ไป u | ||
| − | '''Lemma:''' | + | '''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> | <math>d_T (s,u) + l(u,v) \geq d_T (s,v) </math> | ||
รุ่นแก้ไขเมื่อ 07:37, 29 สิงหาคม 2553
จดบันทึกคำบรรยายโดย:
5314550032 นาย กิตติกานต์ ดวงประภา
5314550041 นาย เกียรติชุมพล สุทธิศิริกุล
5314550059 นาย ฉนานนท์ ตันสกุล
Shortest Paths
มี G = (v,E) โดยที่ n = |v|
มี : E -> R โดยที่ m = |E|
ให้ สำหรับ u ใดๆ แทนระยะทางที่สั้นที่สุดจาก s ไป u
Lemma: ถ้าให้ เป็นระยะทางจาก s ไป v บน T แล้ว T จะเป็น shortest path tree ก็ต่อเมื่อ(if and only if) สำหรับทุกๆ เส้นเชื่อม (u,v) E
