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

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

จากรูปข้างบน ในที่นี้ $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$

@@ แถว 11: / แถว 11: @@
 =Shortest Paths=
-มี G = (v,E)  โดยที่  n = |v|
+มี <math>G = (v,E)</math>  โดยที่  <math>n = |v|</math>
-มี <math>l</math> : E -> R  โดยที่ m = |E|
+มี <math>l</math> : <math>E -> R </math>  โดยที่ <math>m = |E|</math>
-ให้ <math>d(u)</math>  สำหรับ u ใดๆ แทนระยะทางที่สั้นที่สุดจาก s ไป u
+ให้ <math>d(u)</math>  สำหรับ <math>u</math> ใดๆ แทนระยะทางที่สั้นที่สุดจาก <math>s</math> ไป <math>u</math>
-'''Lemma:''' ถ้าให้ <math>d_t (s,v)</math> เป็นระยะทางจาก s ไป v บน T แล้ว  T จะเป็น shortest path tree ก็ต่อเมื่อ(if and only if) สำหรับทุกๆ เส้นเชื่อม  (u,v) <math>\in</math> E
+'''Lemma:''' ถ้าให้ <math>d_T (s,v)</math> เป็นระยะทางจาก <math>s</math> ไป <math>v</math> บน <math>T</math> แล้ว  <math>T</math> จะเป็น shortest path tree ก็ต่อเมื่อ(if and only if) สำหรับทุกๆ เส้นเชื่อม  <math>(u,v) \in  E </math>
 <math>d_T (s,u)  + l(u,v) \geq d_T (s,v) </math>
 [[ไฟล์:lecture7_figure1.png]]
+พิจารณาตัวอย่าง
+[[ไฟล์:lecture7_figure2.png]]
+จากรูปข้างบน ในที่นี้ <math>d_T(s,v)</math> ไม่ใช่ shortest path แล้ว ถ้าเราอยากทราบ shortest path เราก็บอก parent ของ <math>v</math> ให้วิ่งไปหา shortest path ทางอื่น อย่าวิ่งผ่านมาที่ <math>v</math> (นี่คือการ update shortest path)
+'''Framework''' ของการหา shortest path
+* ทุกๆ โหนดเก็บ parent , โหนด <math>u</math> เก็บ <math>p(u)</math> ที่เป็น parent ใน candidate shortest path tree
+    (เริ่มต้น)  <math>p(s) = nil  </math>
+                 <math> \forall{u} \in V,  p(u) = nil</math>
+* ทุกๆ โหนด <math>u</math> เก็บ <math>D(u)</math> ซึ่งแทนระยะทางที่สั้นที่สุด''"เท่าที่ทราบ"'' จาก <math>s</math> ไป <math>u</math>
+    (เริ่มต้น)  <math>D(s) = 0 </math>
+                 <math> \forall{u} \in V - \{s\} ,  D(u) = \infty </math>

ผลต่างระหว่างรุ่นของ "204512-53/lecture7"

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

Shortest Paths

รายการเลือกการนำทาง

เครื่องมือส่วนตัว

เนมสเปซ

สิ่งที่แตกต่าง

ดู

เพิ่มเติม

ค้นหา

การนำทาง

เครื่องมือ