204512-53/lecture7

จาก Theory Wiki
ไปยังการนำทาง ไปยังการค้นหา

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

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