ผลต่างระหว่างรุ่นของ "204512/บรรยาย 6"

จาก Theory Wiki
ไปยังการนำทาง ไปยังการค้นหา
(แก้ข้อความอ่านไม่ออก(ใช้ wget + KHexedit + HTML Decode) ทั้งหมด)
 
(ไม่แสดง 1 รุ่นระหว่างกลางโดยผู้ใช้คนเดียวกัน)
แถว 1: แถว 1:
 
ertalia
 
ertalia
{{หัวคำบรรยาย|204512}}
+
{{หัวคำบรรยาย|204512}}
'''จดบันทึกคำบรรยายโดย:'''<br>
+
'''จดบันทึกคำบรรยายโดย:'''<br>
ณัฐ เรืองฤทธิ์ 50653773<br>
+
ณัฐ เรืองฤทธิ์ 50653773<br>
อมรเดช แจ่มสว่าง 50653963<br>
+
อมรเดช แจ่มสว่าง 50653963<br>
  
ในบทนี้จะพูดถึงปัญหาการหาเส้นทางที่สั้นที่สุด โดยจะเริ่มจากนิยามและพิสูจน์การมีอยู่ของเส้นทางที่สั้นที่สุดเมื่อไม่มีวงรอบที่เป็นลบ จากนั้นจะอธิบายถึง Single Source Shortest Path
+
ในบทนี้จะพูดถึงปัญหาการหาเส้นทางที่สั้นที่สุด โดยจะเริ่มจากนิยามและพิสูจน์การมีอยู่ของเส้นทางที่สั้นที่สุดเมื่อไม่มีวงรอบที่เป็นลบ จากนั้นจะอธิบายถึง Single Source Shortest Path
  
==นิยาม==
+
==นิยาม==
เราจะเริ่มต้นด้วยนิยามของเส้นทางสั้นที่สุด
+
เราจะเริ่มต้นด้วยนิยามของเส้นทางสั้นที่สุด
  
ให้ directed graph ''G = (V,E)'' และฟังก์ชัน <math>length:E \to R</math>  
+
ให้ directed graph ''G = (V,E)'' และฟังก์ชัน <math>length:E \to R</math>  
ที่ระบุความยาวบนเส้นเชื่อม กล่าวคือความยาวของเส้นเชื่อม ''(u,v)'' คือ ''length''(''u,v'')
+
ที่ระบุความยาวบนเส้นเชื่อม กล่าวคือความยาวของเส้นเชื่อม ''(u,v)'' คือ ''length''(''u,v'')
  
สำหรับเส้นทาง ''P'' ใด ๆ เราจะนิยามความยาว ''length''(''P'') เป็น
+
สำหรับเส้นทาง ''P'' ใด ๆ เราจะนิยามความยาว ''length''(''P'') เป็น
 
<center><math>length(P)= \sum_{e\in P} length(e)</math></center>
 
<center><math>length(P)= \sum_{e\in P} length(e)</math></center>
  
''เส้นทางที่สั้นที่สุด'' (shotest path) จาก ''s'' ไป ''t'' คือเส้นทาง ''P'' ที่เริ่มที่ ''s'' สิ้นสุดที่ ''t'' ที่มีความยาวน้อยที่สุด
+
''เส้นทางที่สั้นที่สุด'' (shotest path) จาก ''s'' ไป ''t'' คือเส้นทาง ''P'' ที่เริ่มที่ ''s'' สิ้นสุดที่ ''t'' ที่มีความยาวน้อยที่สุด
  
==วงรอบที่เป็นลบกับเส้นทางที่สั้นที่สุด==
+
==วงรอบที่เป็นลบกับเส้นทางที่สั้นที่สุด==
ปัญหาแรกที่เราสนใจก็คือ: '''เส้นทางที่สั้นที่สุดจะมีในทุก ๆ กราฟหรือไม่?'''
+
ปัญหาแรกที่เราสนใจก็คือ: '''เส้นทางที่สั้นที่สุดจะมีในทุก ๆ กราฟหรือไม่?'''
  
พิจารณากราฟต่อไปนี้<br>
+
พิจารณากราฟต่อไปนี้<br>
[[ภาพ:sp01.png]]<br>
+
[[ภาพ:sp01.png]]<br>
จากรูปจะเห็นได้ว่าถ้ามีการเลือกเส้นทางวนตรงกลางกราฟ จะสามารถวนซ้ำให้ค่าความยาวติดลบเท่าไหร่ก็ได้
+
จากรูปจะเห็นได้ว่าถ้ามีการเลือกเส้นทางวนตรงกลางกราฟ จะสามารถวนซ้ำให้ค่าความยาวติดลบเท่าไหร่ก็ได้
  
เส้นทางดังกล่าวคือ negative length cycle   
+
เส้นทางดังกล่าวคือ negative length cycle   
  
{{กล่องนิยาม|;นิยาม : เราจะเรียกวงรอบที่มีความยาวเป็นลบ ว่า '''negative length cycle''' หรือ '''negative cycle'''}}
+
{{กล่องนิยาม|;นิยาม : เราจะเรียกวงรอบที่มีความยาวเป็นลบ ว่า '''negative length cycle''' หรือ '''negative cycle'''}}
  
เราจะเรียก path ใด ๆ ว่าเป็น <u>simple path</u> ถ้าไม่มีโหนดใดๆ ประกฎใน path มากกว่า 1 ครั้ง และจะเรียก path ใด ๆ ว่าเป็น
+
เราจะเรียก path ใด ๆ ว่าเป็น <u>simple path</u> ถ้าไม่มีโหนดใดๆ ประกฎใน path มากกว่า 1 ครั้ง และจะเรียก path ใด ๆ ว่าเป็น
<u>''s''-''t'' path</u> ถ้า path นั้นเริ่มที่ ''s'' และสิ้นสุดที่ ''t''
+
<u>''s''-''t'' path</u> ถ้า path นั้นเริ่มที่ ''s'' และสิ้นสุดที่ ''t''
  
ทฤษฎีบทด้านล่างแสดงว่าถ้ากราฟจะมีเส้นทางที่สั้นที่สุด เมื่อและต่อเมื่อ กราฟไม่มีวงรอบที่เป็นลบ
+
ทฤษฎีบทด้านล่างแสดงว่าถ้ากราฟจะมีเส้นทางที่สั้นที่สุด เมื่อและต่อเมื่อ กราฟไม่มีวงรอบที่เป็นลบ
  
{{กล่องทฤษฎีบท|'''Theorem:''' ถ้าไม่มี negative cycle ''C'' ที่ไปถึงได้จาก ''s'' และบางใหนดใน ''C'' สามารถไปถึง ''t'' ได้,
+
{{กล่องทฤษฎีบท|'''Theorem:''' ถ้าไม่มี negative cycle ''C'' ที่ไปถึงได้จาก ''s'' และบางใหนดใน ''C'' สามารถไปถึง ''t'' ได้,
จะมี shortest path จาก ''s'' ไป ''t''}}
+
จะมี shortest path จาก ''s'' ไป ''t''}}
{{เริ่มบทพิสูจน์}}
+
{{เริ่มบทพิสูจน์}}
 
'''Proof:'''  
 
'''Proof:'''  
สังเกตว่าสำหรับ ''s-t'' path ''P'' ใดๆ จะมี simple ''s''-''t'' path ''P''' ที่มีความยาวไม่มากกว่า ''P'' ทั้งนี้เนื่องจากถ้าเส้นทางนั้นมี cycle เราสามารถตัด cycle นั้นออกได้โดยไม่ทำให้ความยาวของเส้นทางที่ได้ยาวขึ้น (ดูรูปด้านล่าง)
+
สังเกตว่าสำหรับ ''s-t'' path ''P'' ใดๆ จะมี simple ''s''-''t'' path ''P''' ที่มีความยาวไม่มากกว่า ''P'' ทั้งนี้เนื่องจากถ้าเส้นทางนั้นมี cycle เราสามารถตัด cycle นั้นออกได้โดยไม่ทำให้ความยาวของเส้นทางที่ได้ยาวขึ้น (ดูรูปด้านล่าง)
<center>[[ภาพ:sp02.png]]</center>
+
<center>[[ภาพ:sp02.png]]</center>
  
เนื่องจากจำนวน simple ''s-t'' path มีจำกัด (ไม่เกิน n! path) เมื่อ n = จำนวนโหนดในกราฟ ดังนั้นจะมี path ที่มีความยาวสั้นที่สุด
+
เนื่องจากจำนวน simple ''s-t'' path มีจำกัด (ไม่เกิน n! path) เมื่อ n = จำนวนโหนดในกราฟ ดังนั้นจะมี path ที่มีความยาวสั้นที่สุด
{{จบบทพิสูจน์}}
+
{{จบบทพิสูจน์}}
  
 
lirelrol
 
lirelrol
 
==Single Source Shortest Path==
 
==Single Source Shortest Path==
ในปัญหา single source shortest path เราจะได้รับ source ''s'' แล้วหา shortest path จาก ''s'' ไปยังทุกๆ โหนด
+
ในปัญหา single source shortest path เราจะได้รับ source ''s'' แล้วหา shortest path จาก ''s'' ไปยังทุกๆ โหนด
  
{{กล่องนิยาม|
+
{{กล่องนิยาม|
;นิยาม : ต้นไม้ ''T''  ที่มี ''s'' เป็น root เป็น '''shortest path tree''' ถ้าทุกๆ path ใน ''T'' เป็น shortest path}}
+
;นิยาม : ต้นไม้ ''T''  ที่มี ''s'' เป็น root เป็น '''shortest path tree''' ถ้าทุกๆ path ใน ''T'' เป็น shortest path}}
  
ให้ต้นไม้ ''T'', เราให้ ''dist<sub>T</sub>'' แทนความยาวของ path ใน ''T'' จาก ''s'' ไป ''u''  ทฤษฎีบทด้านล่างให้เงื่อนไขที่รับรองว่า ''T'' เป็น shortest path tree
+
ให้ต้นไม้ ''T'', เราให้ ''dist<sub>T</sub>'' แทนความยาวของ path ใน ''T'' จาก ''s'' ไป ''u''  ทฤษฎีบทด้านล่างให้เงื่อนไขที่รับรองว่า ''T'' เป็น shortest path tree
  
{{กล่องทฤษฎีบท|
+
{{กล่องทฤษฎีบท|
 
'''Theorem:'''
 
'''Theorem:'''
ถ้าสำหรับทุก ๆ เส้นเชื่อม (''u'',''v'') ในกราฟ
+
ถ้าสำหรับทุก ๆ เส้นเชื่อม (''u'',''v'') ในกราฟ
 
<center><math>dist_T(v)\le dist_T(u) + length(u,v)</math></center>
 
<center><math>dist_T(v)\le dist_T(u) + length(u,v)</math></center>
แล้ว T จะเป็น shortest path tree
+
แล้ว T จะเป็น shortest path tree
 
}}
 
}}
{{เริ่มบทพิสูจน์}}
+
{{เริ่มบทพิสูจน์}}
 
'''Proof'''<br>
 
'''Proof'''<br>
[[ภาพ:sp03.png|thumb|right|ถ้า ''T'' เป็น shortest path tree
+
[[ภาพ:sp03.png|thumb|right|ถ้า ''T'' เป็น shortest path tree
แล้ว length(u,v) <= 10]]
+
แล้ว length(u,v) <= 10]]
:พิจารณา s-t path ใดๆ<br>
+
:พิจารณา s-t path ใดๆ<br>
[[ภาพ:sp04.png]]<br>
+
[[ภาพ:sp04.png]]<br>
:P ยาว length(p)<br>
+
:P ยาว length(p)<br>
:path on tree ยาว dist <sub>T</sub>(t)<br>
+
:path on tree ยาว dist <sub>T</sub>(t)<br>
:P ต้องมีความยาวไม่น้อยกว่า path on tree ซึ่งเป็น shortest path  ทำให้ T จะเป็น shortest path tree<br><br>
+
:P ต้องมีความยาวไม่น้อยกว่า path on tree ซึ่งเป็น shortest path  ทำให้ T จะเป็น shortest path tree<br><br>
:Proof ด้วยวิธี induction บน P<br>
+
:Proof ด้วยวิธี induction บน P<br>
::ให้ <math>P = <v_0,v_1,...,v_k>\,</math><br>
+
::ให้ <math>P = <v_0,v_1,...,v_k>\,</math><br>
::ซึ่ง <math>v_0\,</math>=s , <math>v_k\,</math>=t<br>
+
::ซึ่ง <math>v_0\,</math>=s , <math>v_k\,</math>=t<br>
::ดังนั้น <math>length(P) = length(v_0,v_1)+length(v_1,v_2)+...+length(v_k-1,v_k)\,</math><br>
+
::ดังนั้น <math>length(P) = length(v_0,v_1)+length(v_1,v_2)+...+length(v_k-1,v_k)\,</math><br>
::จาก <math>dist_T(v)\le dist_T(u) + length(u,v)</math> <br>
+
::จาก <math>dist_T(v)\le dist_T(u) + length(u,v)</math> <br>
::เราทราบว่า<math>length(u,v) \ge dist_T(v) - dist_T(u)</math> <br>
+
::เราทราบว่า<math>length(u,v) \ge dist_T(v) - dist_T(u)</math> <br>
::นำมา map กับ P<br>
+
::นำมา map กับ P<br>
::จะได้ว่า <math>length(P) \ge (dist_T(v_1)-dist_T(v_0))+(dist_T(v_2)-dist_T(v1))+...+(dist_T(v_k)-dist_T(v_k-1))</math> <br>
+
::จะได้ว่า <math>length(P) \ge (dist_T(v_1)-dist_T(v_0))+(dist_T(v_2)-dist_T(v1))+...+(dist_T(v_k)-dist_T(v_k-1))</math> <br>
 
::<math>length(P) \ge dist_T(v_k)-dist_T(v_0)</math><br>
 
::<math>length(P) \ge dist_T(v_k)-dist_T(v_0)</math><br>
 
::<math>length(P) \ge dist_T(t)-0</math><br>
 
::<math>length(P) \ge dist_T(t)-0</math><br>
::P มีความยาวไมน้อยกว่า path on tree ถ้าเงื่อนไขนี้เป็นตริง T จะเป็น shortest path tree<br>
+
::P มีความยาวไมน้อยกว่า path on tree ถ้าเงื่อนไขนี้เป็นตริง T จะเป็น shortest path tree<br>
  
{{จบบทพิสูจน์}}
+
{{จบบทพิสูจน์}}
  
  
 
'''Algorithm'''
 
'''Algorithm'''
:เริ่มต้น
+
:เริ่มต้น
 
:*<math>distance(u)\leftarrow \infty </math> for all <math>u \in V</math><br>
 
:*<math>distance(u)\leftarrow \infty </math> for all <math>u \in V</math><br>
 
:*<math>distance(s)\leftarrow 0</math><br>
 
:*<math>distance(s)\leftarrow 0</math><br>
 
:*parent(u)= null  for all u<br>
 
:*parent(u)= null  for all u<br>
:จากนั้นจึงทำ labelling step<br>
+
:จากนั้นจึงทำ labelling step<br>
 
==== Labelling Step ====
 
==== Labelling Step ====
::เลือก edge(u,v) ที่ <math>distance(v)> distance(u) + length(u,v)\,</math> มา
+
::เลือก edge(u,v) ที่ <math>distance(v)> distance(u) + length(u,v)\,</math> มา
::แล้วปรับค่า <math>distance(v)\leftarrow distance(u) + length(u,v)</math>
+
::แล้วปรับค่า <math>distance(v)\leftarrow distance(u) + length(u,v)</math>
::และ <math>p(v)\leftarrow u</math><br>
+
::และ <math>p(v)\leftarrow u</math><br>
[[ภาพ:sp05.png]]
+
[[ภาพ:sp05.png]]
 
----
 
----
{{กล่องทฤษฎีบท|
+
{{กล่องทฤษฎีบท|
 
'''Lemma'''
 
'''Lemma'''
:ถ้า <math>distance(u)\ne\infty</math> , จะมี path จาก s ไป u ที่มีความยาว distance(u)<br>
+
:ถ้า <math>distance(u)\ne\infty</math> , จะมี path จาก s ไป u ที่มีความยาว distance(u)<br>
 
}}
 
}}
{{เริ่มบทพิสูจน์}}
+
{{เริ่มบทพิสูจน์}}
 
'''Proof'''
 
'''Proof'''
: assume ว่า lemma จริงเมื่อตอนต้นการทำงาน<br>
+
: assume ว่า lemma จริงเมื่อตอนต้นการทำงาน<br>
: Proof by induction บนจำนวนของการทำ labelling step  
+
: Proof by induction บนจำนวนของการทำ labelling step  
::assume ว่า lemma จริงก่อนการทำงานของ step ใดๆ<br>
+
::assume ว่า lemma จริงก่อนการทำงานของ step ใดๆ<br>
[[ภาพ:sp06.png]]
+
[[ภาพ:sp06.png]]
::เนื่องจาก <math>distance(u)\ne\infty</math> มี path p จาก s ไป u ที่มีความยาว distance(u) (by induction step)<br>
+
::เนื่องจาก <math>distance(u)\ne\infty</math> มี path p จาก s ไป u ที่มีความยาว distance(u) (by induction step)<br>
::หลังการทำงานตาม labelling step<br>
+
::หลังการทำงานตาม labelling step<br>
 
::<math>distance(v)\leftarrow distance(u) + length(u,v)</math><br>
 
::<math>distance(v)\leftarrow distance(u) + length(u,v)</math><br>
::ซึ่งเท่ากับความยาวของ <math>p' = p \cup \{u,v\}</math>
+
::ซึ่งเท่ากับความยาวของ <math>p' = p \cup \{u,v\}</math>
{{จบบทพิสูจน์}}
+
{{จบบทพิสูจน์}}
 
----
 
----
{{กล่องทฤษฎีบท|
+
{{กล่องทฤษฎีบท|
 
'''Lemma'''
 
'''Lemma'''
:ถ้า labelling step terminate ,parent p จะ form ตัวเป็น shortest path tree T  
+
:ถ้า labelling step terminate ,parent p จะ form ตัวเป็น shortest path tree T  
:และสำหรับ u ที่ <math>distance(u)\ne\infty</math> , distance(u)จะเท่ากับความยาวของ path ใน T จาก s ไป u
+
:และสำหรับ u ที่ <math>distance(u)\ne\infty</math> , distance(u)จะเท่ากับความยาวของ path ใน T จาก s ไป u
 
}}
 
}}
'''กำหนดให้'''
+
'''กำหนดให้'''
 
*<math>p^k(u) = p(p^{k-1}(u))\,</math>
 
*<math>p^k(u) = p(p^{k-1}(u))\,</math>
 
*<math>p^1(u) = p(u)\,</math>
 
*<math>p^1(u) = p(u)\,</math>
{{เริ่มบทพิสูจน์}}
+
{{เริ่มบทพิสูจน์}}
 
'''Proof'''<br>
 
'''Proof'''<br>
 
'''(I)'''
 
'''(I)'''
:ถ้า G มี negative cycle ที่ไปถึงได้จาก s, labelling step จะไม่หยุดการทำงาน<br><br>
+
:ถ้า G มี negative cycle ที่ไปถึงได้จาก s, labelling step จะไม่หยุดการทำงาน<br><br>
:ไม่ว่า distance fucntion บนโหนดจะเป็น อย่างไร<br>
+
:ไม่ว่า distance fucntion บนโหนดจะเป็น อย่างไร<br>
:จะมีบาง edge ที่ทำ labelling step ได้<br>
+
:จะมีบาง edge ที่ทำ labelling step ได้<br>
[[ภาพ:sp08.png]]<br>
+
[[ภาพ:sp08.png]]<br>
:พิจารณา<br>
+
:พิจารณา<br>
 
:<math>distance(v)> distance(u) + length(u,v)\,</math><br>
 
:<math>distance(v)> distance(u) + length(u,v)\,</math><br>
:แสดงว่าจะมีการทำ labelling step เมื่อ <math>distance(u) + length(u,v) - distance(v) < 0\,</math><br>
+
:แสดงว่าจะมีการทำ labelling step เมื่อ <math>distance(u) + length(u,v) - distance(v) < 0\,</math><br>
:จากรูป มีโหนดจำนวน k โหนด เขียนออกมาได้ว่า<br><br>
+
:จากรูป มีโหนดจำนวน k โหนด เขียนออกมาได้ว่า<br><br>
 
:<math>distance(v_1) + length(v_1,v_2) - distance(v_2)\,</math><br>
 
:<math>distance(v_1) + length(v_1,v_2) - distance(v_2)\,</math><br>
 
:<math>distance(v_2) + length(v_2,v_3) - distance(v_3)\,</math><br>
 
:<math>distance(v_2) + length(v_2,v_3) - distance(v_3)\,</math><br>
 
::::::::<math>\vdots</math><br>
 
::::::::<math>\vdots</math><br>
 
:<math>distance(v_k) + length(v_k,v_1) - distance(v_1)\,</math><br><br>
 
:<math>distance(v_k) + length(v_k,v_1) - distance(v_1)\,</math><br><br>
:ซึ่งจะสามารถทำ labelling step ได้ถ้าบางแถวยังมีค่าน้อยกว่า 0<br>
+
:ซึ่งจะสามารถทำ labelling step ได้ถ้าบางแถวยังมีค่าน้อยกว่า 0<br>
:เมื่อลองจับทุกแถวบวกกัน<br>
+
:เมื่อลองจับทุกแถวบวกกัน<br>
:[[ภาพ:sp09.png]]<br><br>
+
:[[ภาพ:sp09.png]]<br><br>
:จะพบว่าเหลือแต่ค่า length รวมกันซึ่งก็คือ ความยาวของ path ใน cycle<br>
+
:จะพบว่าเหลือแต่ค่า length รวมกันซึ่งก็คือ ความยาวของ path ใน cycle<br>
:ซึ่งถ้าเป็น negative cycle แสดงว่าต้องมีตัวใดตัวหนึ่งมีค่าติดลบ
+
:ซึ่งถ้าเป็น negative cycle แสดงว่าต้องมีตัวใดตัวหนึ่งมีค่าติดลบ
:ทำให้สามารถทำ labelling step ได้เสมอ<br>
+
:ทำให้สามารถทำ labelling step ได้เสมอ<br>
 
'''(II)'''
 
'''(II)'''
:ไม่มี v ที่ <math>p^k(v)=v\,</math> สำหรับบางค่าของ k<br>
+
:ไม่มี v ที่ <math>p^k(v)=v\,</math> สำหรับบางค่าของ k<br>
[[ภาพ:sp07.png]]<br>
+
[[ภาพ:sp07.png]]<br>
:แต่เราปรับค่า d(u) นั่นคือ
+
:แต่เราปรับค่า d(u) นั่นคือ
 
:<math>d(u) > d(u) + \sum_{i=1}^{k-1} length(e_i)</math><br>
 
:<math>d(u) > d(u) + \sum_{i=1}^{k-1} length(e_i)</math><br>
 
:<math>d(u) > d(u) + length(c)\,</math><br>
 
:<math>d(u) > d(u) + length(c)\,</math><br>
:นั่นคือ <math>length(c) < 0\,</math><br><br>
+
:นั่นคือ <math>length(c) < 0\,</math><br><br>
: *จากเบอร์ 1 กราฟไม่มี negative cycle<br>
+
: *จากเบอร์ 1 กราฟไม่มี negative cycle<br>
 
'''(III)'''
 
'''(III)'''
:ถ้ามี path จาก s ไป v<br>
+
:ถ้ามี path จาก s ไป v<br>
:<math>dist(v)\ne \infty</math> และ <math>p(v)\ne null</math>
+
:<math>dist(v)\ne \infty</math> และ <math>p(v)\ne null</math>
:เพราะถ้ามี path ถึง v แสดงว่าต้องมีการ update มาถึง v เลยทำให้ <math>dist(v)\ne \infty</math> และ <math>p(v)\ne null</math> ด้วย<br><br>
+
:เพราะถ้ามี path ถึง v แสดงว่าต้องมีการ update มาถึง v เลยทำให้ <math>dist(v)\ne \infty</math> และ <math>p(v)\ne null</math> ด้วย<br><br>
จาก '''(I),(II),(III)''' จะสามารถ proof ได้กว่า <br>
+
จาก '''(I),(II),(III)''' จะสามารถ proof ได้กว่า <br>
# parent จะ form ตัวกันเป็น tree T
+
# parent จะ form ตัวกันเป็น tree T
# ทุกๆ edge ที่สอดคล้องกับ (I) ทำให้ T เป็น shortest path tree<br><br>
+
# ทุกๆ edge ที่สอดคล้องกับ (I) ทำให้ T เป็น shortest path tree<br><br>
{{จบบทพิสูจน์}}
+
{{จบบทพิสูจน์}}
  
 
== Labelling & Scanning Method ==
 
== Labelling & Scanning Method ==
แต่ละโหนดจะมีสถานะได้ดังนี้
+
แต่ละโหนดจะมีสถานะได้ดังนี้
 
:* Unlabelled
 
:* Unlabelled
 
:* Labelled
 
:* Labelled
 
:* Scanned
 
:* Scanned
[[ภาพ:Sp10.png|center]]<br>
+
[[ภาพ:Sp10.png|center]]<br>
:เริ่มต้นโหนดทุกโหนดยกเว้น s จะมีสถานะเป็น Unlabelled และ s มีสถานะเป็น Labelled<br>
+
:เริ่มต้นโหนดทุกโหนดยกเว้น s จะมีสถานะเป็น Unlabelled และ s มีสถานะเป็น Labelled<br>
:และทุกครั้งที่ distance(u) เปลี่ยน u จะมีสถานะเป็น Labelled<br><br>
+
:และทุกครั้งที่ distance(u) เปลี่ยน u จะมีสถานะเป็น Labelled<br><br>
<b><u>Pre-Condition</u></b> u มีสถานะเป็น Labelled<br><br>
+
<b><u>Pre-Condition</u></b> u มีสถานะเป็น Labelled<br><br>
 
:::SCAN(u):
 
:::SCAN(u):
 
::::<math>foreach (u,v) \in E</math><br>
 
::::<math>foreach (u,v) \in E</math><br>
 
:::::if distance(v) > distance(u) + length(u,v)<br>
 
:::::if distance(v) > distance(u) + length(u,v)<br>
 
:::::<math>if distance(v) \leftarrow distance(u) + length(u,v)</math><br>
 
:::::<math>if distance(v) \leftarrow distance(u) + length(u,v)</math><br>
:::::เปลี่ยนสถานะของ v เป็น Labelled<br><br><br>
+
:::::เปลี่ยนสถานะของ v เป็น Labelled<br><br><br>
[[ภาพ:Sp11.png|center]]<br><br>
+
[[ภาพ:Sp11.png|center]]<br><br>
<center><small>แสดงขั้นตอนการทำ Labelling & Spanning Method</small></center><br><br>
+
<center><small>แสดงขั้นตอนการทำ Labelling & Spanning Method</small></center><br><br>
:<b><u>Claim :</u></b> ถ้าทำตามวิธี Labelling & Scanning Method แล้วไม่แหลือโหนดที่มีสถานะเป็น Labelled เลย เราจะไม่สามารถทำ Labelling Step ได้อีก
+
:<b><u>Claim :</u></b> ถ้าทำตามวิธี Labelling & Scanning Method แล้วไม่แหลือโหนดที่มีสถานะเป็น Labelled เลย เราจะไม่สามารถทำ Labelling Step ได้อีก
 
----
 
----
  
 
== Efficient Scanning Order ==
 
== Efficient Scanning Order ==
;<b>(I) กราฟที่ไม่มี cycle [Directed Acyclic Graph - DAG]</b> :คือกราฟที่ไม่มีการเรียงแบบ Topological ของโหนด
+
;<b>(I) กราฟที่ไม่มี cycle [Directed Acyclic Graph - DAG]</b> :คือกราฟที่ไม่มีการเรียงแบบ Topological ของโหนด
[[ภาพ:Sp12.png|center]]<br>
+
[[ภาพ:Sp12.png|center]]<br>
:Running time จาก Algorithm นี้คือ O(m+n)
+
:Running time จาก Algorithm นี้คือ O(m+n)
:<b><u>***Topological ของโหนด</u></b> คือ การเรียงของโหนดที่รับประกันได้ว่าไม่มี edge จากโหนดด้านหลังชี้มายังโหนดด้านหน้า<br><br>
+
:<b><u>***Topological ของโหนด</u></b> คือ การเรียงของโหนดที่รับประกันได้ว่าไม่มี edge จากโหนดด้านหลังชี้มายังโหนดด้านหน้า<br><br>
;<b>(II) กราฟไม่มี edge ที่ความยาวเป็นลบ [Dijkstra's Algorithm]</b><br><br> <br><br>
+
;<b>(II) กราฟไม่มี edge ที่ความยาวเป็นลบ [Dijkstra's Algorithm]</b><br><br> <br><br>
:ในบรรดาโหนดที่มีสถานะเป็น Labelled ให้ Scan โหนด w ที่ distance(w) น้อยที่สุด <u>โดยจะไม่ Scan ซ้ำ</u><br>
+
:ในบรรดาโหนดที่มีสถานะเป็น Labelled ให้ Scan โหนด w ที่ distance(w) น้อยที่สุด <u>โดยจะไม่ Scan ซ้ำ</u><br>
:จะใช้ Priority Queue : เข้ามาช่วยในการทำ Algorithm โดยที่<br><br><br>
+
:จะใช้ Priority Queue : เข้ามาช่วยในการทำ Algorithm โดยที่<br><br><br>
 
<center>
 
<center>
 
{|border="1" width ="600"
 
{|border="1" width ="600"
| Enqueue(k,v) || เพิ่ม (k,v) ลงใน Set
+
| Enqueue(k,v) || เพิ่ม (k,v) ลงใน Set
 
|-
 
|-
| FindMin || <math>Return(k,v) \in S</math> ที่มีค่า k น้อยที่สุด
+
| FindMin || <math>Return(k,v) \in S</math> ที่มีค่า k น้อยที่สุด
 
|-
 
|-
| ExtractMin || <math>Return(k,v) \in S</math> ที่มีค่า k น้อยที่สุดและลบ (k,v) ออกจาก S
+
| ExtractMin || <math>Return(k,v) \in S</math> ที่มีค่า k น้อยที่สุดและลบ (k,v) ออกจาก S
 
|-
 
|-
| Update((k,v),k') || Update k ด้วย k'
+
| Update((k,v),k') || Update k ด้วย k'
 
|}</center><br><br>
 
|}</center><br><br>
 
:<u><i>Dijkstra's Algorithm</i></u><br><br>
 
:<u><i>Dijkstra's Algorithm</i></u><br><br>
แถว 205: แถว 205:
 
::::::<math>Update((distance(v),v'))</math><br>
 
::::::<math>Update((distance(v),v'))</math><br>
 
:::::<math>S \leftarrow S \cup \{u\}</math><br><br><br>
 
:::::<math>S \leftarrow S \cup \{u\}</math><br><br><br>
:Running Time จะแบ่งเป็น 2 ช่วงได้แก่ช่วงของการ ExtractMin (O(n)) และช่วงของการ UpdateQueue (O(m)) ซึ่งจะแตกต่างกันไป
+
:Running Time จะแบ่งเป็น 2 ช่วงได้แก่ช่วงของการ ExtractMin (O(n)) และช่วงของการ UpdateQueue (O(m)) ซึ่งจะแตกต่างกันไป
:ตามการจัดวางของ Graph แบบต่างๆ โดยสามารถเทียบเป็นตารางได้ดังนี้<br><br><br>
+
:ตามการจัดวางของ Graph แบบต่างๆ โดยสามารถเทียบเป็นตารางได้ดังนี้<br><br><br>
 
<center>
 
<center>
 
{|border="1" width="600"
 
{|border="1" width="600"
 
| || ExtractMin || UpdateQueue || Total
 
| || ExtractMin || UpdateQueue || Total
 
|-
 
|-
| Array ของโหนด<br>(Dijkstra)|| O(n) || O(1) || O(n^2)
+
| Array ของโหนด<br>(Dijkstra)|| O(n) || O(1) || O(n^2)
 
|-
 
|-
 
| Binary Heap || O(logn) || O(logn) || O((m+n)logn)
 
| Binary Heap || O(logn) || O(logn) || O((m+n)logn)
แถว 217: แถว 217:
 
| Fibonacci Heap || O(logn) || decrease key<br>O(1)<br>amortized || O(nlogn+m)
 
| Fibonacci Heap || O(logn) || decrease key<br>O(1)<br>amortized || O(nlogn+m)
 
|}</center>
 
|}</center>
<center><small>ตารางแสดง Running Time เทียบกับ form ของ graph แบบต่างๆ</small></center><br><br>
+
<center><small>ตารางแสดง Running Time เทียบกับ form ของ graph แบบต่างๆ</small></center><br><br>
;<b>(III) กราฟทั่วไป [Bellman - Ford - Moore]</b> : เป็นการ Scan ทุกๆ โหนดเป็นจำนวน n-1 รอบ เพราะฉะนั้น Running Time จะเป็น O(nm)
+
;<b>(III) กราฟทั่วไป [Bellman - Ford - Moore]</b> : เป็นการ Scan ทุกๆ โหนดเป็นจำนวน n-1 รอบ เพราะฉะนั้น Running Time จะเป็น O(nm)

รุ่นแก้ไขปัจจุบันเมื่อ 13:33, 18 มีนาคม 2551

ertalia

บันทึกคำบรรยายวิชา 204512 นี้ เป็นบันทึกที่นิสิตเขียนขึ้น เนื้อหาโดยมากยังไม่ผ่านการตรวจสอบอย่างละเอียด การนำไปใช้ควรระมัดระวัง

จดบันทึกคำบรรยายโดย:
ณัฐ เรืองฤทธิ์ 50653773
อมรเดช แจ่มสว่าง 50653963

ในบทนี้จะพูดถึงปัญหาการหาเส้นทางที่สั้นที่สุด โดยจะเริ่มจากนิยามและพิสูจน์การมีอยู่ของเส้นทางที่สั้นที่สุดเมื่อไม่มีวงรอบที่เป็นลบ จากนั้นจะอธิบายถึง Single Source Shortest Path

นิยาม

เราจะเริ่มต้นด้วยนิยามของเส้นทางสั้นที่สุด

ให้ directed graph G = (V,E) และฟังก์ชัน ที่ระบุความยาวบนเส้นเชื่อม กล่าวคือความยาวของเส้นเชื่อม (u,v) คือ length(u,v)

สำหรับเส้นทาง P ใด ๆ เราจะนิยามความยาว length(P) เป็น

เส้นทางที่สั้นที่สุด (shotest path) จาก s ไป t คือเส้นทาง P ที่เริ่มที่ s สิ้นสุดที่ t ที่มีความยาวน้อยที่สุด

วงรอบที่เป็นลบกับเส้นทางที่สั้นที่สุด

ปัญหาแรกที่เราสนใจก็คือ: เส้นทางที่สั้นที่สุดจะมีในทุก ๆ กราฟหรือไม่?

พิจารณากราฟต่อไปนี้
Sp01.png
จากรูปจะเห็นได้ว่าถ้ามีการเลือกเส้นทางวนตรงกลางกราฟ จะสามารถวนซ้ำให้ค่าความยาวติดลบเท่าไหร่ก็ได้

เส้นทางดังกล่าวคือ negative length cycle

นิยาม 
เราจะเรียกวงรอบที่มีความยาวเป็นลบ ว่า negative length cycle หรือ negative cycle

เราจะเรียก path ใด ๆ ว่าเป็น simple path ถ้าไม่มีโหนดใดๆ ประกฎใน path มากกว่า 1 ครั้ง และจะเรียก path ใด ๆ ว่าเป็น s-t path ถ้า path นั้นเริ่มที่ s และสิ้นสุดที่ t

ทฤษฎีบทด้านล่างแสดงว่าถ้ากราฟจะมีเส้นทางที่สั้นที่สุด เมื่อและต่อเมื่อ กราฟไม่มีวงรอบที่เป็นลบ

Theorem: ถ้าไม่มี negative cycle C ที่ไปถึงได้จาก s และบางใหนดใน C สามารถไปถึง t ได้, จะมี shortest path จาก s ไป t


Proof: สังเกตว่าสำหรับ s-t path P ใดๆ จะมี simple s-t path P' ที่มีความยาวไม่มากกว่า P ทั้งนี้เนื่องจากถ้าเส้นทางนั้นมี cycle เราสามารถตัด cycle นั้นออกได้โดยไม่ทำให้ความยาวของเส้นทางที่ได้ยาวขึ้น (ดูรูปด้านล่าง)

Sp02.png

เนื่องจากจำนวน simple s-t path มีจำกัด (ไม่เกิน n! path) เมื่อ n = จำนวนโหนดในกราฟ ดังนั้นจะมี path ที่มีความยาวสั้นที่สุด

Littlebox.png

lirelrol

Single Source Shortest Path

ในปัญหา single source shortest path เราจะได้รับ source s แล้วหา shortest path จาก s ไปยังทุกๆ โหนด

นิยาม 
ต้นไม้ T ที่มี s เป็น root เป็น shortest path tree ถ้าทุกๆ path ใน T เป็น shortest path

ให้ต้นไม้ T, เราให้ distT แทนความยาวของ path ใน T จาก s ไป u ทฤษฎีบทด้านล่างให้เงื่อนไขที่รับรองว่า T เป็น shortest path tree

Theorem: ถ้าสำหรับทุก ๆ เส้นเชื่อม (u,v) ในกราฟ

แล้ว T จะเป็น shortest path tree


Proof

ถ้า T เป็น shortest path tree แล้ว length(u,v) <= 10
พิจารณา s-t path ใดๆ

Sp04.png

P ยาว length(p)
path on tree ยาว dist T(t)
P ต้องมีความยาวไม่น้อยกว่า path on tree ซึ่งเป็น shortest path ทำให้ T จะเป็น shortest path tree

Proof ด้วยวิธี induction บน P
ให้
ซึ่ง =s , =t
ดังนั้น
จาก
เราทราบว่า
นำมา map กับ P
จะได้ว่า


P มีความยาวไมน้อยกว่า path on tree ถ้าเงื่อนไขนี้เป็นตริง T จะเป็น shortest path tree
Littlebox.png


Algorithm

เริ่มต้น
  • for all

  • parent(u)= null for all u
จากนั้นจึงทำ labelling step

Labelling Step

เลือก edge(u,v) ที่ มา
แล้วปรับค่า
และ

Sp05.png


Lemma

ถ้า , จะมี path จาก s ไป u ที่มีความยาว distance(u)

Proof

assume ว่า lemma จริงเมื่อตอนต้นการทำงาน
Proof by induction บนจำนวนของการทำ labelling step
assume ว่า lemma จริงก่อนการทำงานของ step ใดๆ

Sp06.png

เนื่องจาก มี path p จาก s ไป u ที่มีความยาว distance(u) (by induction step)
หลังการทำงานตาม labelling step

ซึ่งเท่ากับความยาวของ
Littlebox.png


Lemma

ถ้า labelling step terminate ,parent p จะ form ตัวเป็น shortest path tree T
และสำหรับ u ที่ , distance(u)จะเท่ากับความยาวของ path ใน T จาก s ไป u

กำหนดให้


Proof
(I)

ถ้า G มี negative cycle ที่ไปถึงได้จาก s, labelling step จะไม่หยุดการทำงาน

ไม่ว่า distance fucntion บนโหนดจะเป็น อย่างไร
จะมีบาง edge ที่ทำ labelling step ได้

Sp08.png

พิจารณา

แสดงว่าจะมีการทำ labelling step เมื่อ
จากรูป มีโหนดจำนวน k โหนด เขียนออกมาได้ว่า






ซึ่งจะสามารถทำ labelling step ได้ถ้าบางแถวยังมีค่าน้อยกว่า 0
เมื่อลองจับทุกแถวบวกกัน
Sp09.png

จะพบว่าเหลือแต่ค่า length รวมกันซึ่งก็คือ ความยาวของ path ใน cycle
ซึ่งถ้าเป็น negative cycle แสดงว่าต้องมีตัวใดตัวหนึ่งมีค่าติดลบ
ทำให้สามารถทำ labelling step ได้เสมอ

(II)

ไม่มี v ที่ สำหรับบางค่าของ k

Sp07.png

แต่เราปรับค่า d(u) นั่นคือ


นั่นคือ

*จากเบอร์ 1 กราฟไม่มี negative cycle

(III)

ถ้ามี path จาก s ไป v
และ
เพราะถ้ามี path ถึง v แสดงว่าต้องมีการ update มาถึง v เลยทำให้ และ ด้วย

จาก (I),(II),(III) จะสามารถ proof ได้กว่า

  1. parent จะ form ตัวกันเป็น tree T
  2. ทุกๆ edge ที่สอดคล้องกับ (I) ทำให้ T เป็น shortest path tree

Littlebox.png

Labelling & Scanning Method

แต่ละโหนดจะมีสถานะได้ดังนี้

  • Unlabelled
  • Labelled
  • Scanned
Sp10.png


เริ่มต้นโหนดทุกโหนดยกเว้น s จะมีสถานะเป็น Unlabelled และ s มีสถานะเป็น Labelled
และทุกครั้งที่ distance(u) เปลี่ยน u จะมีสถานะเป็น Labelled

Pre-Condition u มีสถานะเป็น Labelled

SCAN(u):

if distance(v) > distance(u) + length(u,v)

เปลี่ยนสถานะของ v เป็น Labelled


Sp11.png



แสดงขั้นตอนการทำ Labelling & Spanning Method



Claim : ถ้าทำตามวิธี Labelling & Scanning Method แล้วไม่แหลือโหนดที่มีสถานะเป็น Labelled เลย เราจะไม่สามารถทำ Labelling Step ได้อีก

Efficient Scanning Order

(I) กราฟที่ไม่มี cycle [Directed Acyclic Graph - DAG]
คือกราฟที่ไม่มีการเรียงแบบ Topological ของโหนด
Sp12.png


Running time จาก Algorithm นี้คือ O(m+n)
***Topological ของโหนด คือ การเรียงของโหนดที่รับประกันได้ว่าไม่มี edge จากโหนดด้านหลังชี้มายังโหนดด้านหน้า

(II) กราฟไม่มี edge ที่ความยาวเป็นลบ [Dijkstra's Algorithm]



ในบรรดาโหนดที่มีสถานะเป็น Labelled ให้ Scan โหนด w ที่ distance(w) น้อยที่สุด โดยจะไม่ Scan ซ้ำ
จะใช้ Priority Queue : เข้ามาช่วยในการทำ Algorithm โดยที่


Enqueue(k,v) เพิ่ม (k,v) ลงใน Set
FindMin ที่มีค่า k น้อยที่สุด
ExtractMin ที่มีค่า k น้อยที่สุดและลบ (k,v) ออกจาก S
Update((k,v),k') Update k ด้วย k'



Dijkstra's Algorithm













Running Time จะแบ่งเป็น 2 ช่วงได้แก่ช่วงของการ ExtractMin (O(n)) และช่วงของการ UpdateQueue (O(m)) ซึ่งจะแตกต่างกันไป
ตามการจัดวางของ Graph แบบต่างๆ โดยสามารถเทียบเป็นตารางได้ดังนี้


ExtractMin UpdateQueue Total
Array ของโหนด
(Dijkstra)
O(n) O(1) O(n^2)
Binary Heap O(logn) O(logn) O((m+n)logn)
Fibonacci Heap O(logn) decrease key
O(1)
amortized
O(nlogn+m)
ตารางแสดง Running Time เทียบกับ form ของ graph แบบต่างๆ



(III) กราฟทั่วไป [Bellman - Ford - Moore] 
เป็นการ Scan ทุกๆ โหนดเป็นจำนวน n-1 รอบ เพราะฉะนั้น Running Time จะเป็น O(nm)