204512/บรรยาย 6

ertalia

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

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

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

นิยาม

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

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

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

$length(P)=\sum _{e\in P}length(e)$

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

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

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

พิจารณากราฟต่อไปนี้

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

เส้นทางดังกล่าวคือ 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 นั้นออกได้โดยไม่ทำให้ความยาวของเส้นทางที่ได้ยาวขึ้น (ดูรูปด้านล่าง)

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

---

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, เราให้ dist_T แทนความยาวของ path ใน T จาก s ไป u ทฤษฎีบทด้านล่างให้เงื่อนไขที่รับรองว่า T เป็น shortest path tree

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

$dist_{T}(v)\leq dist_{T}(u)+length(u,v)$

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

---

Proof

ถ้า T เป็น shortest path tree แล้ว length(u,v) <= 10

พิจารณา s-t path ใดๆ

P ยาว length(p)

path on tree ยาว dist _T(t)

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

Proof ด้วยวิธี induction บน P

ให้ $P=<v_{0},v_{1},...,v_{k}>\,$

ซึ่ง $v_{0}\,$=s , $v_{k}\,$=t

ดังนั้น $length(P)=length(v_{0},v_{1})+length(v_{1},v_{2})+...+length(v_{k}-1,v_{k})\,$

จาก $dist_{T}(v)\leq dist_{T}(u)+length(u,v)$

เราทราบว่า$length(u,v)\geq dist_{T}(v)-dist_{T}(u)$

นำมา map กับ P

จะได้ว่า $length(P)\geq (dist_{T}(v_{1})-dist_{T}(v_{0}))+(dist_{T}(v_{2})-dist_{T}(v1))+...+(dist_{T}(v_{k})-dist_{T}(v_{k}-1))$

$length(P)\geq dist_{T}(v_{k})-dist_{T}(v_{0})$

$length(P)\geq dist_{T}(t)-0$

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

---

Algorithm

เริ่มต้น

• $distance(u)\leftarrow \infty$ for all $u\in V$
  
• $distance(s)\leftarrow 0$
  
• parent(u)= null for all u
  

จากนั้นจึงทำ labelling step

Labelling Step

เลือก edge(u,v) ที่ $distance(v)>distance(u)+length(u,v)\,$ มา

แล้วปรับค่า $distance(v)\leftarrow distance(u)+length(u,v)$

และ $p(v)\leftarrow u$

---

Lemma

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

---

Proof

assume ว่า lemma จริงเมื่อตอนต้นการทำงาน

Proof by induction บนจำนวนของการทำ labelling step

assume ว่า lemma จริงก่อนการทำงานของ step ใดๆ

เนื่องจาก $distance(u)\neq \infty$ มี path p จาก s ไป u ที่มีความยาว distance(u) (by induction step)

หลังการทำงานตาม labelling step

$distance(v)\leftarrow distance(u)+length(u,v)$

ซึ่งเท่ากับความยาวของ $p'=p\cup \{u,v\}$

---

---

Lemma

ถ้า labelling step terminate ,parent p จะ form ตัวเป็น shortest path tree T

และสำหรับ u ที่ $distance(u)\neq \infty$ , distance(u)จะเท่ากับความยาวของ path ใน T จาก s ไป u

กำหนดให้

• $p^{k}(u)=p(p^{k-1}(u))\,$
• $p^{1}(u)=p(u)\,$

---

Proof
(I)

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

ไม่ว่า distance fucntion บนโหนดจะเป็น อย่างไร

จะมีบาง edge ที่ทำ labelling step ได้

พิจารณา

$distance(v)>distance(u)+length(u,v)\,$

แสดงว่าจะมีการทำ labelling step เมื่อ $distance(u)+length(u,v)-distance(v)<0\,$

จากรูป มีโหนดจำนวน k โหนด เขียนออกมาได้ว่า

$distance(v_{1})+length(v_{1},v_{2})-distance(v_{2})\,$

$distance(v_{2})+length(v_{2},v_{3})-distance(v_{3})\,$

$\vdots$

$distance(v_{k})+length(v_{k},v_{1})-distance(v_{1})\,$

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

เมื่อลองจับทุกแถวบวกกัน

จะพบว่าเหลือแต่ค่า length รวมกันซึ่งก็คือ ความยาวของ path ใน cycle

ซึ่งถ้าเป็น negative cycle แสดงว่าต้องมีตัวใดตัวหนึ่งมีค่าติดลบ

ทำให้สามารถทำ labelling step ได้เสมอ

(II)

ไม่มี v ที่ $p^{k}(v)=v\,$ สำหรับบางค่าของ k

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

$d(u)>d(u)+\sum _{i=1}^{k-1}length(e_{i})$

$d(u)>d(u)+length(c)\,$

นั่นคือ $length(c)<0\,$

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

(III)

ถ้ามี path จาก s ไป v

$dist(v)\neq \infty$ และ $p(v)\neq null$

เพราะถ้ามี path ถึง v แสดงว่าต้องมีการ update มาถึง v เลยทำให้ $dist(v)\neq \infty$ และ $p(v)\neq null$ ด้วย

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

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

---

Labelling & Scanning Method

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

• Unlabelled
• Labelled
• Scanned

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

และทุกครั้งที่ distance(u) เปลี่ยน u จะมีสถานะเป็น Labelled

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

SCAN(u):

$foreach(u,v)\in E$

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

$ifdistance(v)\leftarrow distance(u)+length(u,v)$

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

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

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

---

Efficient Scanning Order

(I) กราฟที่ไม่มี cycle [Directed Acyclic Graph - DAG]

คือกราฟที่ไม่มีการเรียงแบบ Topological ของโหนด

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	$Return(k,v)\in S$ ที่มีค่า k น้อยที่สุด
ExtractMin	$Return(k,v)\in S$ ที่มีค่า k น้อยที่สุดและลบ (k,v) ออกจาก S
Update((k,v),k')	Update k ด้วย k'

Dijkstra's Algorithm

$S\leftarrow \emptyset$

$Forall\ v,\ distance(v)\leftarrow \infty$

$distance(s)\leftarrow 0,\ Q.enqueue(0,s)$

$While(Q\ is\ not\ empty)$

$u\leftarrow Q.ExtractMin$

$Foreach\ (u,v)\in E$

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

$distance(v)\leftarrow distance(u)\ +\ length(u,v)$

$Update((distance(v),v'))$

$S\leftarrow S\cup \{u\}$

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)