แผนการเรียน
/

Practice: Pathfinding Problems
เซสชันฝึกซ้อม: โจทย์การหาเส้นทางสั้นที่สุด

Day 08 Evening: ลงมือแก้โจทย์จาก CSES Graph Section ด้วย Dijkstra, Bellman-Ford และ Floyd-Warshall

เป้าหมายของเซสชันนี้

  • ฝึกการ Implement Dijkstra ให้แม่นยำและรวดเร็ว
  • จัดการปัญหา All-pairs shortest paths ด้วย Floyd-Warshall
  • ตรวจจับและจัดการกับ Negative Cycles ด้วย Bellman-Ford

แหล่งฝึกฝน: https://cses.fi/problemset/

Shortest Routes I
การประยุกต์ใช้ Dijkstra พื้นฐาน

โจทย์ (Task 1671):

มีเมือง ( n ) เมือง และเส้นทางบิน ( m ) เส้นทาง จงหาระยะทางที่สั้นที่สุดจากเมืองที่ 1 ไปยังทุกเมือง

Key Strategy:

  • ใช้ Priority Queue ร่วมกับ Adjacency List
  • ระวัง: ระยะทางรวมอาจมีค่าสูงมาก ต้องใช้ long long เก็บค่าระยะทาง
  • ใช้โครงสร้าง ( (distance, node) ) ใน PQ และใช้ค่าติดลบหรือ `greater` เพื่อทำ Min-Heap

แหล่งอ้างอิง: https://cses.fi/book/book.pdf

Dijkstra Checklist
ตรวจสอบโค้ดก่อนส่ง

1. Priority Queue

ประกาศเป็น `priority_queue>` และใส่ข้อมูลแบบ `pq.push({-d, u})` หรือใช้ `greater` สม่ำเสมอ

2. Processing Check

ใส่เงื่อนไข `if (d > dist[u]) continue;` เพื่อป้องกันการประมวลผลซ้ำในโหนดที่ระยะทางแย่กว่า

3. Initial Distances

ตั้งค่าเริ่มต้นเป็น 0 สำหรับจุดเริ่ม และ ( \infty ) (ประมาณ 1e18) สำหรับโหนดอื่น

4. Graph Memory

ใช้ `vector> adj[N]` เพื่อเก็บเส้นเชื่อมที่มีน้ำหนักอย่างประหยัดพื้นที่

แหล่งอ้างอิง: https://usaco.guide/CPH.pdf

Shortest Routes II
All-pairs Shortest Paths

โจทย์ (Task 1672):

มีคำถาม ( q ) ข้อ แต่ละข้อถามระยะทางที่สั้นที่สุดระหว่างเมือง ( a ) และ ( b ) โดย ( n \le 500 ) และ ( q \le 10^5 )

Key Strategy:

  • เนื่องจาก ( n ) มีขนาดเล็กพอ แต่อยากรู้ระหว่างทุกคู่โหนด: ใช้ Floyd-Warshall
  • ความซับซ้อน ( O(n^3) ) ซึ่งประมาณ ( 500^3 = 125,000,000 ) การดำเนินการ (ทันใน 1 วินาที)
  • เตรียม Adjacency Matrix และรัน 3 Nested Loops โดยให้ ( k ) (โหนดตัวกลาง) เป็นลูปนอกสุด

แหล่งอ้างอิง: https://cses.fi/book/book.pdf

Floyd-Warshall Tips
ข้อควรระวังสำหรับโจทย์ All-pairs

  • • Multiple Edges: ระหว่างสองเมืองอาจมีถนนมากกว่าหนึ่งเส้น ตอนรับ Input ต้องเก็บเฉพาะเส้นที่สั้นที่สุดไว้ใน Matrix
  • • Initial State: ตั้งค่า ( dist[i][i] = 0 ) และ ( dist[i][j] = \infty ) หากไม่มีเส้นเชื่อมตรง
  • • Infinity Check: เมื่อตอบคำถาม หาก ( dist[a][b] ) ยังเป็น ( \infty ) ให้แสดงผล -1
  • • Complexity: อัลกอริทึมนี้จะช้าเกินไปทันทีถ้า ( n > 500 )

แหล่งอ้างอิง: https://www.geeksforgeeks.org/floyd-warshall-algorithm-dp-16/

High Score
Longest Path & Negative Cycles

โจทย์ (Task 1673):

ต้องการหาทางที่ได้ "คะแนนรวมสูงสุด" จากโหนด 1 ไป ( n ) โดยกราฟมีน้ำหนักได้ทั้งบวกและลบ

Challenge: การหาคะแนนสูงสุด คือการหาเส้นทางที่ "ติดลบน้อยที่สุด" หากกลับค่าน้ำหนักเป็น ( -w ) จะเปลี่ยนเป็นปัญหาหา Shortest Path ในกราฟที่มีน้ำหนักติดลบได้ ซึ่งต้องใช้ Bellman-Ford

แหล่งอ้างอิง: https://cses.fi/book/book.pdf

Handling -Infinity
เมื่อคะแนนสามารถเพิ่มได้ไม่จำกัด

ขั้นตอนการตรวจสอบ:

  1. โจทย์ถามคะแนนสูงสุด ( ( \infty ) ) หากพบวงรอบที่เพิ่มคะแนนได้เรื่อยๆ (Positive Cycle ในโจทย์เดิม หรือ Negative Cycle หลังกลับค่า)
  2. แต่ระวัง: วงรอบนั้นต้องอยู่บน เส้นทาง จาก 1 ไป ( n ) เท่านั้น
  3. วิธีเช็ค: โหนด ( u ) ที่อยู่ในวงรอบต้องสามารถไปถึง ( n ) ได้ และ ( 1 ) ต้องสามารถไปถึง ( u ) ได้ (ใช้ DFS/BFS ตรวจสอบ Reachability)

แหล่งอ้างอิง: https://roadmap.sh/datastructures-and-algorithms

Cycle Finding
การตรวจจับวงรอบติดลบและการสร้างใหม่

โจทย์ (Task 1197):

จงหาว่ามี Negative Cycle ในกราฟหรือไม่ หากมี ให้แสดงผลโหนดที่อยู่ในวงรอบนั้น

Key Strategy:

  • รัน Bellman-Ford จำนวน ( n ) รอบ
  • หากในรอบที่ ( n ) ยังมีการ Relax สำเร็จ แสดงว่าพบวงรอบติดลบ
  • ใช้โหนดก่อนหน้า (Parent) ที่เก็บไว้ตอน Relax เพื่อย้อนรอยหาโหนดทั้งหมดในวงรอบ

แหล่งอ้างอิง: https://cses.fi/book/book.pdf

Optimization for Limits
เทคนิคเพื่อความเร็ว

1. Fast I/O

ใช้ `ios::sync_with_stdio(0); cin.tie(0);` เสมอเพราะ Input กราฟมักมีขนาดใหญ่

2. Array vs Vector

จองอาร์เรย์ขนาดใหญ่แบบ Global ดีกว่าประกาศ Vector ในฟังก์ชัน

3. INF Constant

ใช้ค่าที่ใหญ่พอ เช่น `1e18` ( (10^{18}) ) สำหรับ `long long` เพื่อป้องกันระยะทางหลอก

4. Self-loops

ระวังเมืองที่มีถนนเชื่อมหาตัวเองและมีน้ำหนักติดลบ (Self-negative-cycle)

แหล่งอ้างอิง: https://roadmap.sh/datastructures-and-algorithms

Go Solve!
เริ่มการฝึกซ้อม

"เครื่องมือพร้อม ทฤษฎีแน่น ถึงเวลาพิสูจน์ฝีมือในระบบ CSES"

ลำดับแนะนำ:

  • Shortest Routes I (Dijkstra)
  • Shortest Routes II (Floyd-Warshall)
  • High Score (Bellman-Ford)
  • Cycle Finding (Cycle reconstruction)

"Happy Coding!"

URL: https://cses.fi/problemset/list/