204512-53/lecture7

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

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)$

พิจารณาตัวอย่าง

จากรูปข้างบน ในที่นี้ $d_{T}(s,v)$ ไม่ใช่ shortest path แล้ว ถ้าเราอยากทราบ shortest path เราก็บอก parent ของ $v$ ให้วิ่งไปหา shortest path ทางอื่น อย่าวิ่งผ่านมาที่ $v$ (นี่คือการ update shortest path)

Framework ของการหา shortest path

• ทุกๆ โหนดเก็บ parent , โหนด $u$ เก็บ $p(u)$ ที่เป็น parent ใน candidate shortest path tree

   (เริ่มต้น)  $p(s)=nil$
                $\forall {u}\in V,p(u)=nil$

• ทุกๆ โหนด $u$ เก็บ $D(u)$ ซึ่งแทนระยะทางที่สั้นที่สุด"เท่าที่ทราบ" จาก $s$ ไป $u$

   (เริ่มต้น)  $D(s)=0$
                $\forall {u}\in V-\{s\},D(u)=\infty$

LABELING STEP:

    เลือกเส้นเชื่อม $(u,v)\in E$ ที่  
                $D(u)+l(u,v)<D(v)$
    จากนั้น   
                $D(v)<-D(u)+l(u,v)$
                $p(v)<-u$

Ford's algorithm -> ทำ labeling step ไปเรื่อยๆ

ตัวอย่าง

มี Graph

Step เริ่มต้น $D(s)=0$ และ $D(u)$ ของโหนดอื่นๆ มีค่าเป็น $\infty$