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$

Step ต่อมา ค่อยๆ ปรับ $D(u)$ และ parent (หัวลูกศรชี้หา parent)

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

Claim 2: ถ้า Ford's Algorithm ทำงานจบ, ระยะทางที่สั้นที่สุดจาก $s$ ไป $u$

$\forall {u}\in V,D(u)\leq d(u)$ (นั่นคือ ระยะที่ estimate ได้ จะไม่มากไปกว่าระยะทางที่สั้นที่สุด)

ถ้า algorithm ทำงานจบ เราจะรู้ว่า $D(a)+l(a,b)\geq D(b)$

Proof: พิจารณาโหนด $u$ ใดๆ ให้ path เป็น shortest path จาก $s$ ไป $u$

ดังนั้น $d(u)=\sum _{i=0}^{k-1}l(v_{i},v_{i+1})$

เนื่องจาก Ford's algorithm ทำงานจบ เราจะได้ว่า $\forall (x,w)\in E$ , $D(x)+l(x,w)\geq D(w)$

นั่นคือ $l(x,w)\geq D(w)-D(x)$

จะได้ว่า $d(u)\geq \sum _{i=0}^{k-1}[D(v_{i+1})-D(v_{i})]$

                  = $(D(v_{1})-D(v_{0}))+(D(v_{2})-D(v_{1}))+(D(v_{3})-D(v_{2}))+...+(D(v_{k})-D(v_{k-1}))$
                  = $-D(v_{0})+D(v_{k})$
                  = $D(v_{k})$        (เนื่องจาก$D(v_{0})=D(s)=0$)
                  = $D(u)$           (เนื่องจาก $D(v_{k})=D(u)$ )

เมื่อนำ Claim 1 มารวมกับ Claim 2 เราจะสรุปได้ว่า ถ้า Ford's algorithm ทำงานจบ เราจะได้ระยะทาง shortest path

คำถามต่อมาคือ เราจะรู้ได้ยังไงว่า algorithm จะทำงานจนจบ

Claim 3: ถ้ามี Negative cycle ที่ไปถึงได้จาก $s$ , algorithm จะทำงานไม่จบ

เนื่องจาก labeling step ของ Ford อิงกับเส้นเชื่อมเป็นหลัก ดังนั้นเพื่อให้พิสูจน์ได้ เราจะปรับโครงสร้างสักเล็กน้อย ซึ่งจะอิงกับ node เป็นหลัก พิจารณารูปข้างล่าง

แต่ละโหนดจะมี 3 state

- UNLABELED หมายถึง โหนดที่ยังไม่เคยถูกกระทำใดๆ เลย

- LABELED หมายถึง โหนดที่โดน update แล้ว

- SCANNED หมายถึง โหนดที่โดน update แล้ว และได้มีการพิจารณาทุกเส้นเชื่อมที่ติดกับโหนดนั้นและกระจายค่าไปให้คนอื่นแล้ว

SCANNING STEP: เลือก labeled node u , scan u แล้วเปลี่ยนสถานะของ u ให้เป็น SCANNED

scan (u)
    for all edge(u,v)
        if  D(u) + l(u,v) < D(v)
              D(v) <- D(u) + l(u,v)
              p(v) <- u
              เปลี่ยนสถานะ v ให้เป็น LABELED

ดูตัวอย่างตามรูปข้างล่าง มีกราฟ

เริ่มต้น

เมื่ออัลกอริทึมเริ่มทำงาน ตามรูป โหนด s มีสถานะเป็น scanned ส่วนโหนด a มีสถานะเป็น labeled

ถ้ามีการ update โหนดที่เป็น scanned อยู่แล้ว โหนดนั้นก็จะกลับมาสู่สถานะ labeled อีกครั้ง

เมื่อทุกโหนดเปลี่ยนสถานะเป็น scanned ทั้งหมด อัลกอรึทึมนี้ก็จะถือว่าทำงานจบ

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

Directed Acyclic Graph (DAG)

กราฟที่มีทิศทาง G จะเป็น DAG ก็ต่อเมื่อ G ไม่มี cycle

ให้กราฟ $G$ , ลำดับของโหนด $v_{1},v_{2},v_{3},...,v_{n}$ จะเป็น topological order ถ้าไม่มีเส้นเชื่อม $(v_{i},v_{j})$ ที่ $i>j$

ถ้ากราฟใดๆ มี topological order ก็สรุปได้ว่าเราสามารถไล่ scan โหนดไปในทิศทางเดียวโดยที่ไม่ต้องย้อนกลับมา scan โหนดเดิมอีกได้

รูปข้างล่างแสดงตัวอย่างของกราฟที่ไม่มี topological order

นั่นคือ ถ้ากราฟมี cycle กราฟนั้นจะไม่มี topological order

คำถาม ถ้ากราฟไม่มี cycle กราฟนั้นจะมี topological order รึเปล่า

ตอบ มีเสมอ สามารถพิสูจน์ได้โดยแสดงอัลกอริทึม topological sort

   Topological Sort 
   - โหนดที่ไม่มี edge ใดๆ ชี้หาเรียกว่า "source"
   - วิธีการคือ วิ่งหา source แล้วก็ลบโหนดนั้นทิ้ง แล้วก็ไล่หา source ตัวถัดไปแล้วก็ลบโหนดนั้นทิ้งอีก ทำเช่นนี้ไปเรื่อยๆ ลำดับในการลบที่ได้คือ topological order

   พิสูจน์ว่า DAG ใดๆ มี topological order โดยใช้วิธีการ contradiction
       เนื่องจากกราฟมีโหนดจำนวนจำกัด ถ้าหากอัลกอริทึม topological sort สามารถทำงานไปได้เรื่อยๆ ไม่จบ แสดงว่ากราฟนั้นมี cycle ซึ่งไม่เป็น DAG

Dijkstra's Algorithm ใช้กับกราฟที่ไม่มี negative cycle

เป็นวิธีการแบบหนึ่งที่ใช้สำหรับหา shortest path โดยใช้หลักการ เลือกสแกน labeled node u ที่มี $D(u)$ น้อยที่สุด ซึ่งทำให้รับประกันได้ว่าเมื่อเราสแกนโหนดนี้ไปแล้วจะไม่ต้องกลับมาสแกนที่โหนดเดียวกันอีก

$algorithm:$

$S\leftarrow \emptyset$

$D(u)\leftarrow \infty ,forallu$

$D(s)\leftarrow 0$

$whiles\neq vdo$

เลือก $u\in S$ ที่มีค่า $D(u)$ น้อยที่สุด _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ ขั้นตอนนี้เรียกว่าการทำ Extract Min

$scan(u)$

$S\leftarrow S\cup {u}$

$scan(u):$

$for$ $all$ $edge(u,v)$

$ifD(u)+l(u,v)<D(v)$

$D(v)\leftarrow D(u)+l(u,v)$ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ ขั้นตอนนี้เรียกว่าการทำ Decrease Key

$p(v)\leftarrow u$

เปลี่ยนสถานะ $v$ ให้เป็น Labeled

Data structure ที่เหมาะนำมาใช้กับ algorithm นี้คือ priority queue , ถ้ามี priority queue ที่สามารถ

• Extract Min ได้ในเวลา $\alpha$
  
• Decrease Key ได้ในเวลา $\beta$
  

ดังนั้น เมื่อวิเคราะห์เวลาการทำงานของ Dijkstra's algorithm จะได้ว่า algorithm ทำงานในเวลา $O(n*\alpha +m*\beta )$

เมื่อวิเคราะห์เวลาการทำงานของ Dijkstra's algorithm เมื่อใช้ data structure แบบอื่นๆ จะได้ตามตารางข้างล่าง

Data Structure	$\alpha$	$\beta$	Dijkstra
Array	$O(n)$	$O(1)$	$O(n^{2})$
Heap	$O(logn)$	$O(logn)$	$O((m+n)logn)$
Fibonacci Heap	$O(logn)$	$O(1)$ amortized	$O(nlogn+m)$

General Case (general weights)

Bellman-Ford-Moore

$While$ $True$

$for$ $all$ $node$ $u$ $\in$ $V$

$scan(u)$

Claim

  หลังการทำงานของ BFM ไป i รอบ  โหนด $u$ ที่มี shortest path จาก $u$ ไป $s$ ไม่เกิน i เส้น จะมี $D(u)=d(v)$ 

Thm

  ถ้ากราฟไม่มี negative cycle, BFM  จะทำงานไม่เกิน n-1 รอบ

ดังนั้น BFM ทำงานในเวลา $O(nm)$