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

จาก Theory Wiki
ไปยังการนำทาง ไปยังการค้นหา
(แก้ข้อความอ่านไม่ออก(ใช้ wget + KHexedit + HTML Decode) ทั้งหมด)
 
(ไม่แสดง 25 รุ่นระหว่างกลางโดยผู้ใช้ 6 คน)
แถว 1: แถว 1:
== Shortest Path ==
+
ertalia
=== นิยาม ===
+
{{หัวคำบรรยาย|204512}}
 +
'''จดบันทึกคำบรรยายโดย:'''<br>
 +
ณัฐ เรืองฤทธิ์ 50653773<br>
 +
อมรเดช แจ่มสว่าง 50653963<br>
  
ให้ Directed Graph <math>G = (V,E)\,</math><br>
+
ในบทนี้จะพูดถึงปัญหาการหาเส้นทางที่สั้นที่สุด โดยจะเริ่มจากนิยามและพิสูจน์การมีอยู่ของเส้นทางที่สั้นที่สุดเมื่อไม่มีวงรอบที่เป็นลบ จากนั้นจะอธิบายถึง Single Source Shortest Path
และ lengths on edge(u,v) แทนความยาวของเส้นเชื่อม (u,v) | <math>length:E \to R</math><br>
+
 
สำหรับเส้นทาง P , <math>length(P)= \sum length(e) </math> โดย <math>e \in p</math><br>
+
==นิยาม==
Shotest Path จาก s ไป t คือเส้นทาง p ที่เริ่มที่ s สิ้นสุดที่ t ที่มีความยาวน้อยที่สุด<br>
+
เราจะเริ่มต้นด้วยนิยามของเส้นทางสั้นที่สุด
----
+
 
 +
ให้ directed graph ''G = (V,E)'' และฟังก์ชัน <math>length:E \to R</math>  
 +
ที่ระบุความยาวบนเส้นเชื่อม  กล่าวคือความยาวของเส้นเชื่อม ''(u,v)'' คือ ''length''(''u,v'')
 +
 
 +
สำหรับเส้นทาง ''P'' ใด ๆ เราจะนิยามความยาว ''length''(''P'') เป็น
 +
<center><math>length(P)= \sum_{e\in P} length(e)</math></center>
 +
 
 +
''เส้นทางที่สั้นที่สุด'' (shotest path) จาก ''s'' ไป ''t'' คือเส้นทาง ''P'' ที่เริ่มที่ ''s'' สิ้นสุดที่ ''t'' ที่มีความยาวน้อยที่สุด
 +
 
 +
==วงรอบที่เป็นลบกับเส้นทางที่สั้นที่สุด==
 +
ปัญหาแรกที่เราสนใจก็คือ: '''เส้นทางที่สั้นที่สุดจะมีในทุก ๆ กราฟหรือไม่?'''
 +
 
 +
พิจารณากราฟต่อไปนี้<br>
 +
[[ภาพ:sp01.png]]<br>
 +
จากรูปจะเห็นได้ว่าถ้ามีการเลือกเส้นทางวนตรงกลางกราฟ จะสามารถวนซ้ำให้ค่าความยาวติดลบเท่าไหร่ก็ได้
 +
 
 +
เส้นทางดังกล่าวคือ negative length cycle 
 +
 
 +
{{กล่องนิยาม|;นิยาม : เราจะเรียกวงรอบที่มีความยาวเป็นลบ ว่า '''negative length cycle''' หรือ '''negative cycle'''}}
 +
 
 +
เราจะเรียก path ใด ๆ ว่าเป็น <u>simple path</u> ถ้าไม่มีโหนดใดๆ ประกฎใน path มากกว่า 1 ครั้ง และจะเรียก path ใด ๆ ว่าเป็น
 +
<u>''s''-''t'' path</u> ถ้า path นั้นเริ่มที่ ''s'' และสิ้นสุดที่ ''t''
  
=== Negative Length Cycle ===
+
ทฤษฎีบทด้านล่างแสดงว่าถ้ากราฟจะมีเส้นทางที่สั้นที่สุด เมื่อและต่อเมื่อ กราฟไม่มีวงรอบที่เป็นลบ
Negative Length Cycle  คือ Cycle ที่มีความยาวเป็นลบ<br>
 
[[ภาพ:sp01.png]]<br><br>
 
จากรูปจะเห็นได้ว่าถ้ามีการเลือกเส้นทางวนเป็นวงกลม จะสามารถปั๊มให้ค่า weight ติดลบเท่าไหร่ก็ได้<br>
 
  
'''Thm'''<br>
+
{{กล่องทฤษฎีบท|'''Theorem:''' ถ้าไม่มี negative cycle ''C'' ที่ไปถึงได้จาก ''s'' และบางใหนดใน ''C'' สามารถไปถึง ''t'' ได้,
:ถ้าไม่มี negative cycle c<br>
+
จะมี shortest path จาก ''s'' ไป ''t''}}
:ที่ไปถึงได้จาก s และบางใหนดใน c สามารถไปถึง t ได้<br>
+
{{เริ่มบทพิสูจน์}}
:มี Shortest Path จาก s ไป t<br>
+
'''Proof:'''
 +
สังเกตว่าสำหรับ ''s-t'' path ''P'' ใดๆ จะมี simple ''s''-''t'' path ''P''' ที่มีความยาวไม่มากกว่า ''P'' ทั้งนี้เนื่องจากถ้าเส้นทางนั้นมี cycle เราสามารถตัด cycle นั้นออกได้โดยไม่ทำให้ความยาวของเส้นทางที่ได้ยาวขึ้น  (ดูรูปด้านล่าง)
 +
<center>[[ภาพ:sp02.png]]</center>
  
 +
เนื่องจากจำนวน simple ''s-t'' path มีจำกัด (ไม่เกิน n! path) เมื่อ n = จำนวนโหนดในกราฟ  ดังนั้นจะมี path ที่มีความยาวสั้นที่สุด
 +
{{จบบทพิสูจน์}}
  
'''Proof'''<br>
+
lirelrol
:กำหนดให้<br>
+
==Single Source Shortest Path==
:# path p เป็น <u>simple path</u> ถ้าไม่มีโหนดใดๆ ประกฎใน path มากกว่า 1 ครั้ง<br>
+
ในปัญหา single source shortest path เราจะได้รับ source ''s'' แล้วหา shortest path จาก ''s'' ไปยังทุกๆ โหนด
:# <u>s-t path</u> คือ path ที่เริ่มที่ s และสิ้นสุดที่ t<br><br>
 
:สำหรับ path p ใดๆ จะมี simple s-t path p' ที่มีความยาวไม่มากกว่า p<br><br>
 
[[ภาพ:sp02.png]]<br><br>
 
:สังเกตว่าจำนวน simple s-t path มีจำกัด (ไม่เกิน n! path) เมื่อ n = จำนวนโหนดในกราฟ<br>
 
----
 
  
=== Single Source Shortest Path ===
+
{{กล่องนิยาม|
คือปัญหาที่ให้ source s แล้วหา shortest path จาก s ไปยังทุกๆ โหนด<br><br>
+
;นิยาม : ต้นไม้ ''T'' ที่มี ''s'' เป็น root เป็น '''shortest path tree''' ถ้าทุกๆ path ใน ''T'' เป็น shortest path}}
Tree T  ที่มี s เป็น root เป็น <u>shortest path tree</u> ถ้าทุกๆ path ใน T เป็น shortest path<br><br>
 
:กำหนดให้
 
:: dist <sub>T</sub> แทนความยาวของ path ใน T จาก s ไป u<br>
 
  
'''Thm'''<br>  
+
ให้ต้นไม้ ''T'', เราให้ ''dist<sub>T</sub>'' แทนความยาวของ path ใน ''T'' จาก ''s'' ไป ''u''  ทฤษฎีบทด้านล่างให้เงื่อนไขที่รับรองว่า ''T'' เป็น shortest path tree
  
:ถ้าทุกๆ edge(u,v)<br>
+
{{กล่องทฤษฎีบท|
:<math>dist_T(v)\le dist_T(u) + length(u,v)</math> <br>
+
'''Theorem:'''
:แล้ว T จะเป็น shortest path tree<br>
+
ถ้าสำหรับทุก ๆ เส้นเชื่อม (''u'',''v'') ในกราฟ
[[ภาพ:sp03.png|thumb|left|ถ้า length(u,v) <= 10, T จะเป็น shortest path tree]]<br><br><br><br><br><br><br><br><br><br><br><br><br><br>
+
<center><math>dist_T(v)\le dist_T(u) + length(u,v)</math></center>
 +
แล้ว T จะเป็น shortest path tree
 +
}}
 +
{{เริ่มบทพิสูจน์}}
 
'''Proof'''<br>
 
'''Proof'''<br>
 +
[[ภาพ:sp03.png|thumb|right|ถ้า ''T'' เป็น shortest path tree
 +
แล้ว length(u,v) <= 10]]
 
:พิจารณา s-t path ใดๆ<br>
 
:พิจารณา s-t path ใดๆ<br>
 
[[ภาพ:sp04.png]]<br>
 
[[ภาพ:sp04.png]]<br>
แถว 53: แถว 75:
 
::เราทราบว่า<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-1)-dist_T(v_k))</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'''
 
:เริ่มต้น
 
:เริ่มต้น
แถว 70: แถว 95:
 
[[ภาพ: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>
แถว 81: แถว 109:
 
::<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 o จะ 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(n) = p(p^{k-1}(n))\,</math>
+
*<math>p^k(u) = p(p^{k-1}(u))\,</math>
*<math>p^1(n) = p(n)\,</math>
+
*<math>p^1(u) = p(u)\,</math>
 +
{{เริ่มบทพิสูจน์}}
 
'''Proof'''<br>
 
'''Proof'''<br>
 
'''(I)'''
 
'''(I)'''
แถว 123: แถว 155:
 
# parent จะ form ตัวกันเป็น tree T
 
# parent จะ form ตัวกันเป็น tree T
 
# ทุกๆ edge ที่สอดคล้องกับ (I) ทำให้ T เป็น shortest path tree<br><br>
 
# ทุกๆ edge ที่สอดคล้องกับ (I) ทำให้ T เป็น shortest path tree<br><br>
--[[ผู้ใช้:Dejzy|Dejzy]] 18:53, 15 กรกฎาคม 2007 (ICT)
+
{{จบบทพิสูจน์}}
 +
 
 +
== Labelling & Scanning Method ==
 +
แต่ละโหนดจะมีสถานะได้ดังนี้
 +
:* Unlabelled
 +
:* Labelled
 +
:* Scanned
 +
[[ภาพ:Sp10.png|center]]<br>
 +
:เริ่มต้นโหนดทุกโหนดยกเว้น s จะมีสถานะเป็น Unlabelled และ s มีสถานะเป็น Labelled<br>
 +
:และทุกครั้งที่ distance(u) เปลี่ยน u จะมีสถานะเป็น Labelled<br><br>
 +
<b><u>Pre-Condition</u></b> u มีสถานะเป็น Labelled<br><br>
 +
:::SCAN(u):
 +
::::<math>foreach (u,v) \in E</math><br>
 +
:::::if distance(v) > distance(u) + length(u,v)<br>
 +
:::::<math>if distance(v) \leftarrow distance(u) + length(u,v)</math><br>
 +
:::::เปลี่ยนสถานะของ v เป็น Labelled<br><br><br>
 +
[[ภาพ:Sp11.png|center]]<br><br>
 +
<center><small>แสดงขั้นตอนการทำ Labelling & Spanning Method</small></center><br><br>
 +
:<b><u>Claim :</u></b> ถ้าทำตามวิธี Labelling & Scanning Method แล้วไม่แหลือโหนดที่มีสถานะเป็น Labelled เลย เราจะไม่สามารถทำ Labelling Step ได้อีก
 
----
 
----
 +
 +
== Efficient Scanning Order ==
 +
;<b>(I) กราฟที่ไม่มี cycle [Directed Acyclic Graph - DAG]</b> :คือกราฟที่ไม่มีการเรียงแบบ Topological ของโหนด
 +
[[ภาพ:Sp12.png|center]]<br>
 +
:Running time จาก Algorithm นี้คือ O(m+n)
 +
:<b><u>***Topological ของโหนด</u></b> คือ การเรียงของโหนดที่รับประกันได้ว่าไม่มี edge จากโหนดด้านหลังชี้มายังโหนดด้านหน้า<br><br>
 +
;<b>(II) กราฟไม่มี edge ที่ความยาวเป็นลบ [Dijkstra's Algorithm]</b><br><br> <br><br>
 +
:ในบรรดาโหนดที่มีสถานะเป็น Labelled ให้ Scan โหนด w ที่ distance(w) น้อยที่สุด <u>โดยจะไม่ Scan ซ้ำ</u><br>
 +
:จะใช้ Priority Queue : เข้ามาช่วยในการทำ Algorithm โดยที่<br><br><br>
 +
<center>
 +
{|border="1" width ="600"
 +
| Enqueue(k,v) || เพิ่ม (k,v) ลงใน Set
 +
|-
 +
| FindMin || <math>Return(k,v) \in S</math> ที่มีค่า k น้อยที่สุด
 +
|-
 +
| ExtractMin || <math>Return(k,v) \in S</math> ที่มีค่า k น้อยที่สุดและลบ (k,v) ออกจาก S
 +
|-
 +
| Update((k,v),k') || Update k ด้วย k'
 +
|}</center><br><br>
 +
:<u><i>Dijkstra's Algorithm</i></u><br><br>
 +
::::<math>S \leftarrow \emptyset</math><br>
 +
::::<math>Forall\ v,\ distance(v) \leftarrow \infty</math><br>
 +
:::::<math>distance(s) \leftarrow 0,\ Q.enqueue(0,s)</math><br>
 +
::::<math>While(Q\ is\ not\ empty)</math><br>
 +
:::::<math>u \leftarrow Q.ExtractMin</math><br>
 +
::::<math>Foreach\ (u,v) \in E</math><br>
 +
:::::<math>if\ distance(v)\ >\ distance(u)\ +\ length(u,v)</math><br>
 +
::::::<math>distance(v) \leftarrow distance(u)\ +\ length(u,v)</math><br>
 +
::::::<math>Update((distance(v),v'))</math><br>
 +
:::::<math>S \leftarrow S \cup \{u\}</math><br><br><br>
 +
:Running Time จะแบ่งเป็น 2 ช่วงได้แก่ช่วงของการ ExtractMin (O(n)) และช่วงของการ UpdateQueue (O(m)) ซึ่งจะแตกต่างกันไป
 +
:ตามการจัดวางของ Graph แบบต่างๆ โดยสามารถเทียบเป็นตารางได้ดังนี้<br><br><br>
 +
<center>
 +
{|border="1" width="600"
 +
| || ExtractMin || UpdateQueue || Total
 +
|-
 +
| Array ของโหนด<br>(Dijkstra)|| O(n) || O(1) || O(n^2)
 +
|-
 +
| Binary Heap || O(logn) || O(logn) || O((m+n)logn)
 +
|-
 +
| Fibonacci Heap || O(logn) || decrease key<br>O(1)<br>amortized || O(nlogn+m)
 +
|}</center>
 +
<center><small>ตารางแสดง Running Time เทียบกับ form ของ graph แบบต่างๆ</small></center><br><br>
 +
;<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)