Shortest Paths I
อัลกอริทึมของ Dijkstra

Day 08 Morning: การหาเส้นทางที่สั้นที่สุดจากจุดเริ่มต้นเดียวในกราฟที่มีน้ำหนัก

หัวข้อที่จะเรียนรู้

1

นิยามของ Single-Source Shortest Path (SSSP)

2

กลยุทธ์แบบ Greedy และการเลือกโหนดที่ใกล้ที่สุด

3

การใช้ Priority Queue เพื่อเพิ่มประสิทธิภาพอัลกอริทึม

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

What is SSSP?
นิยามปัญหาเส้นทางสั้นที่สุด

"กำหนดกราฟที่มีน้ำหนัก (G = (V, E)) และจุดเริ่มต้น (s) จงหาระยะทางที่สั้นที่สุด (d(s, v)) สำหรับทุกโหนด (v) ในกราฟ"

● ในกราฟไม่มีน้ำหนัก เราใช้ BFS เพื่อหาคำตอบ
● ในกราฟมีน้ำหนัก ระยะทางคือผลรวมของน้ำหนักเส้นเชื่อมตามเส้นทาง
● Dijkstra เป็นอัลกอริทึมมาตรฐานสำหรับปัญหานี้

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

The Greedy Strategy
แนวคิดพื้นฐาน: ความใกล้ชิดเป็นสำคัญ

Dijkstra ทำงานโดยการ ขยายขอบเขต ของโหนดที่เรามั่นใจระยะทางสั้นที่สุดแล้ว:

เริ่มจากโหนดเริ่มต้น (s) โดยให้ (dist[s] = 0) และโหนดอื่นเป็น (\infty)
เลือกโหนด (u) ที่ ยังไม่ถูกประมวลผล และมี (dist[u]) น้อยที่สุดในขณะนั้น
ทำการ Relax เส้นเชื่อมรอบๆ โหนด (u) เพื่อปรับปรุงระยะทางของเพื่อนบ้าน
ทำซ้ำจนกว่าจะประมวลผลครบทุกโหนดที่เข้าถึงได้

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

Essential Constraint
ข้อจำกัดสำคัญ: น้ำหนักต้องไม่ติดลบ

Dijkstra ไม่รับรอง ความถูกต้องหากกราฟมีเส้นเชื่อมน้ำหนักติดลบ

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

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

Priority Queue Efficiency
โครงสร้างข้อมูลที่ใช้

Distance Array

เก็บระยะทางที่สั้นที่สุดที่พบในปัจจุบันสำหรับแต่ละโหนด (dist[V])

Min-Priority Queue

ใช้เก็บคู่ของ (distance, node) เพื่อดึงโหนดที่มีระยะทางน้อยที่สุดออกมาอย่างรวดเร็ว

"ใน C++ มักใช้ priority_queue และใส่ค่าติดลบเพื่อจำลอง Min-Heap"

แหล่งอ้างอิง: https://www.geeksforgeeks.org/dijkstras-shortest-path-algorithm-greedy-algo-7/

Edge Relaxation
การผ่อนคลายเส้นเชื่อม

if (dist[u] + weight(u, v) < dist[v]) {
dist[v] = dist[u] + weight(u, v);
}

คือการตรวจสอบว่า การเดินทางไปยังโหนด (v) โดยผ่านโหนด (u) นั้น ให้ระยะทางที่ สั้นกว่า เส้นทางที่เราเคยรู้จักมาก่อนหน้านี้หรือไม่

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

Dijkstra's Process
ลำดับการทำงานทีละขั้นตอน

1. ตั้งค่า (dist[start] = 0) และ (dist[others] = \infty)

2. ใส่ (0, start) ลงใน Priority Queue

3. ขณะที่ Queue ไม่ว่าง: ดึงโหนด (u) ที่มีระยะทางน้อยที่สุดออกมา

4. สำคัญ: ถ้าโหนด (u) ถูกประมวลผล (Processed) แล้ว ให้ข้ามไป

5. สำหรับแต่ละโหนดเพื่อนบ้าน (v) ของ (u): ถ้าเส้นเชื่อม (u \to v) ช่วยลดระยะทาง (Relax) ให้ปรับปรุง (dist[v]) และใส่เข้า Queue ใหม่

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

Implementation in C++
ตัวอย่างโค้ดมาตรฐาน

priority_queue<pair<int,int>> q;

distance[x] = 0; q.push({0, x});

while (!q.empty()) {

int a = q.top().second; q.pop();

if (processed[a]) continue;

processed[a] = true;

for (auto u : adj[a]) {

int b = u.first, w = u.second;

if (distance[a]+w < distance[b]) {

distance[b] = distance[a]+w;

q.push({-distance[b], b}); // Use negative for min-heap

}

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

Time Complexity
วิเคราะห์ประสิทธิภาพ

(O(V + E \log E))

• (V) คือจำนวนโหนด และ (E) คือจำนวนเส้นเชื่อม

• การวนรอบผ่านเส้นเชื่อมทุกเส้นใช้ (E)

• การดำเนินการใน Priority Queue (push/pop) ใช้ (\log E)

• ในกราฟทั่วไป มักเขียนในรูป (O(E \log V))

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

BFS vs. Dijkstra
ความแตกต่างที่ต้องจำ

BFS

• ใช้กับกราฟ ไม่มีน้ำหนัก
• ใช้ Queue ธรรมดา (FIFO)
• เร็วกว่า ((O(V+E)))
• โหนดที่ดึงออกมาครั้งแรกคือทางที่สั้นที่สุดเสมอ

Dijkstra

• ใช้กับกราฟ มีน้ำหนัก (เป็นบวก)
• ใช้ Priority Queue
• ซับซ้อนกว่า ((O(E \log V)))
• ต้องมีการ Relax เส้นเชื่อม

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

Path Reconstruction
การหาเส้นทางจริงไม่ใช่แค่ระยะทาง

ในการหาว่าเส้นทางที่สั้นที่สุดผ่านโหนดใดบ้าง เราต้องบันทึกโหนดก่อนหน้า (Parent):

1. สร้าง Array parent[V] เพื่อเก็บโหนดที่เป็นทางผ่านก่อนจะถึงโหนดปัจจุบัน
2. เมื่อมีการ Relax สำเร็จ: (parent[v] = u)
3. Backtrack: เริ่มจากโหนดปลายทาง ไล่ย้อนกลับไปหาต้นทางผ่าน parent array

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

Dijkstra on Dense Graphs
เมื่อกราฟมีเส้นเชื่อมหนาแน่นมาก

หากกราฟมีจำนวนเส้นเชื่อมใกล้เคียงกับ (V^2) (Dense Graphs):

การใช้ Priority Queue อาจช้าลงเนื่องจาก overhead ของ heap
การใช้อัลกอริทึมเวอร์ชัน (O(V^2)) แบบวนรอบหาโหนดที่สั้นที่สุดโดยตรงจาก Array จะมีประสิทธิภาพดีกว่า
เหมาะสำหรับการใช้คู่กับ Adjacency Matrix

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

Zero-Weight Edges
เส้นเชื่อมที่มีน้ำหนักเป็นศูนย์

"Dijkstra ยังคงทำงานได้ถูกต้อง!"

ตราบใดที่น้ำหนักเส้นเชื่อม ไม่ติดลบ ((\ge 0)) Dijkstra จะหาคำตอบที่สั้นที่สุดได้เสมอ แต่ระวังหากกราฟมี Cycle ที่เป็นศูนย์ทั้งหมด อาจทำให้มีหลายเส้นทางที่สั้นที่สุดเท่ากัน

หมายเหตุ: หากกราฟมีน้ำหนัก 0 และเราต้องการจำนวนโหนดที่น้อยที่สุดในเส้นทางด้วย อาจต้องปรับจูนเงื่อนไขการ Relax เล็กน้อย

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

Why Processed Check?
ความสำคัญของการตรวจสอบโหนดซ้ำ

// บรรทัดที่ห้ามลืม!

if (d > distance[u]) continue;

เนื่องจาก Priority Queue ใน STL ไม่รองรับการอัปเดตค่า (Decrease Key) เราจึงต้องใส่โหนดเดิมที่มีระยะทางใหม่เข้าไป บรรทัดนี้จะช่วยข้ามโหนด "ขยะ" ที่มีระยะทางมากกว่าค่าปัจจุบัน ทำให้ความซับซ้อนคงอยู่ที่ (O(E \log E))

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

Pathfinding on Grids
การประยุกต์ใช้กับตาราง 2 มิติ

โหนดในที่นี้คือพิกัด (r, c) และเส้นเชื่อมคือการเคลื่อนที่ไปยังช่องข้างเคียง:

State: (r, c) แทนตำแหน่งในตาราง
Weight: ค่าน้ำหนักในช่องตารางหรือค่าผ่านทาง
Neighbors: โดยทั่วไปจะมี 4 ทิศทาง (บน, ล่าง, ซ้าย, ขวา) หรือ 8 ทิศทาง
ใช้ Priority Queue เก็บคู่ของ (distance, (r, c))

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

Multi-Source Dijkstra
จุดเริ่มต้นหลายจุด

"โหนดใดอยู่ใกล้สถานีดับเพลิงที่สุด?"

แทนที่จะรัน Dijkstra ทีละสถานี เราสามารถใส่โหนดสถานีทั้งหมดลงใน Priority Queue พร้อมกันตั้งแต่เริ่มต้น:

for (int start_node : all_sources) {
dist[start_node] = 0;
pq.push({0, start_node});
}

ผลลัพธ์คือระยะทางสั้นที่สุดจากโหนดใดก็ได้ในกลุ่มต้นทางไปยังจุดอื่นๆ

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

Min-Heap Implementation
เทคนิคการใช้ Priority Queue ใน C++

แบบที่ 1: Negative Values

ใส่ระยะทางเป็นค่าติดลบเพื่อให้ตัวที่น้อยที่สุด (แต่ค่าลบมากสุด) อยู่บนสุด

pq.push({-d, u});

แบบที่ 2: std::greater

ใช้ตัวดำเนินการเปรียบเทียบมาตรฐานของ C++ เพื่อสร้าง Min-Heap โดยตรง

priority_queue<T, vector<T>, greater<T>> pq;

แหล่งอ้างอิง: https://www.geeksforgeeks.org/custom-comparator-in-priority_queue-in-cpp-stl/

Why it Fails?
กรณีตัวอย่างน้ำหนักติดลบ

พิจารณาทางเดิน: A → B (น้ำหนัก 2), A → C (น้ำหนัก 5), B → C (น้ำหนัก -10)

1. Dijkstra จะเลือก B ก่อน (ระยะทาง 2) แล้วข้ามไปที่ C (ระยะทาง 5)
2. Dijkstra จะมองว่า C "เสร็จแล้ว" และจะไม่กลับมาแก้ไขระยะทางผ่าน B (ซึ่งจริงๆ คือ 2 - 10 = -8)

สรุป: ความละโมบ (Greedy) ของ Dijkstra จะใช้งานไม่ได้เมื่อ "ทางอ้อม" สามารถให้ผลลัพธ์ที่สั้นกว่าได้ไม่จำกัด

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

Dijkstra on State Space
การหาเส้นทางบน "สถานะ"

เทคนิคขั้นสูง: โหนดไม่จำเป็นต้องเป็นจุดในแผนที่

โหนด (Node): อาจเป็นสถานะของปัญหา เช่น (ตำแหน่งปัจจุบัน, พลังงานที่เหลือ, รายการไอเทมที่เก็บ)
เส้นเชื่อม (Edge): การเปลี่ยนสถานะด้วยต้นทุน (น้ำหนัก) ที่ต่างกัน
ช่วยแก้ปัญหาที่มีเงื่อนไขซับซ้อน เช่น "หาทางสั้นที่สุดแต่ต้องเติมน้ำมันไม่เกิน 3 ครั้ง"

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

Scaling for Competition
ขีดจำกัดและการประมวลผล

รองรับ (V, E) ได้ถึงระดับ (10^5) ถึง (10^6) ภายในเวลา 1 วินาที
ใช้หน่วยความจำส่วนใหญ่ไปกับ Adjacency List
ระวัง: หากน้ำหนักรวมเกิน (2 \times 10^9) ต้องใช้ long long เก็บระยะทาง

"เตรียมพร้อมสู่เซสชันบ่าย: เมื่อ Dijkstra รับมือไม่ได้ เราจะทำอย่างไร?"

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

Counting Shortest Paths
การนับจำนวนเส้นทางที่สั้นที่สุด

เราสามารถดัดแปลง Dijkstra เพื่อหาว่ามีกี่เส้นทางที่ให้ระยะทางสั้นที่สุดเท่ากัน:

สร้าง Array count[V] โดยให้ (count[start] = 1)
เมื่อพบทางที่สั้นกว่าเดิม (Relax สำเร็จ): ให้ (count[v] = count[u])
เมื่อพบทางที่มีระยะทาง เท่ากับ ค่าปัจจุบัน: ให้ (count[v] = (count[v] + count[u]) \pmod M)
เทคนิคนี้ใช้บ่อยในโจทย์ที่ต้องการหาโครงสร้างของกราฟที่สั้นที่สุด

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

Dijkstra with std::set
ทางเลือกอื่นในการ Implement

นอกจากการใช้ Priority Queue เรายังสามารถใช้ std::set ใน C++ ได้:

std::set เก็บข้อมูลแบบเรียงลำดับและลบโหนดเดิมออกได้ (Actual Decrease Key)
ขั้นตอน: ลบ (dist[v], v) เดิมออก -> อัปเดตค่า -> ใส่ (dist[v], v) ใหม่เข้าไป
ข้อดี: ไม่ต้องมีเช็ค `processed[u]` และประหยัดหน่วยความจำในบางกรณี
ข้อเสีย: ความเร็วในทางปฏิบัติอาจช้ากว่า Priority Queue เล็กน้อยเนื่องจากโครงสร้าง Tree

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

Priority Queue vs std::set
เปรียบเทียบประสิทธิภาพ

Feature	Priority Queue (Lazy)	std::set (Red-Black Tree)
Memory	High (up to (E) entries)	Low (exactly (V) entries)
Complexity	(O(E \log E))	(O(E \log V))
Coding Speed	Fast/Simple	Slightly complex

"ในสมรภูมิ Competitive Programming ส่วนใหญ่ Priority Queue คือผู้ชนะ"

Bidirectional Dijkstra
การค้นหาจากสองทิศทาง

เพื่อหาทางสั้นที่สุดระหว่าง (s) และ (t) เราสามารถรัน Dijkstra สองตัวพร้อมกัน:

ตัวแรกเริ่มจาก (s) ไปข้างหน้า (Forward Search)
ตัวที่สองเริ่มจาก (t) ย้อนกลับมา (Backward Search - ต้องกลับทิศเส้นเชื่อม)
อัลกอริทึมหยุดเมื่อขอบเขตการค้นหาทั้งสองมาบรรจบกัน
ทำไม? ช่วยลดจำนวนโหนดที่ต้องประมวลผลลงมหาศาล (พื้นที่วงกลมใหญ่ 1 วง vs วงกลมเล็ก 2 วง)

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

CSES: Shortest Routes I
โจทย์ตัวอย่างคลาสสิก

Problem Description:

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

Constraints:
(n \le 10^5, m \le 2 \times 10^5)
(w_i \le 10^9) (ค่าน้ำหนักมหาศาล!)

แหล่งอ้างอิง: https://cses.fi/problemset/task/1671

Beware of Overflows!
ระวังเรื่องชนิดข้อมูล

"น้ำหนักรวมของเส้นทางอาจเกินช่วงของ int ((\approx 2 \times 10^9))"

typedef long long ll;
vector<pair<int, ll>> adj[N];
priority_queue<pair<ll, int>> pq;
const ll INF = 1e18; // ใช้ค่าที่ใหญ่พอจริงๆ

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

Memory Management
การจองหน่วยความจำเพื่อความเร็ว

Arrays (N): ประกาศ Global รวดเร็วที่สุด เข้าถึงหน่วยความจำแบบต่อเนื่อง
std::vector: ยืดหยุ่นแต่มีการ Re-allocation อาจช้ากว่าในโจทย์ที่มี Time Limit บีบมากๆ
Tip: หากทราบขนาดที่แน่นอน (N) การใช้ Global Array `ll dist` มักเป็นทางเลือกที่ปลอดภัยที่สุดในโอลิมปิกคอมพิวเตอร์

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

Debugging Tips
ข้อผิดพลาดที่พบบ่อย

1. PQ Ordering

ลืมใส่ค่าติดลบหรือลืมใช้ `greater<>` ทำให้กลายเป็น Max-Heap (ช้ามาก!)

2. Processing Check

ลืมเช็ค `if (d > dist[u]) continue;` ทำให้วนซ้ำโหนดเดิมหลายรอบ

3. Initial dist[s]

ลืมตั้งระยะทางเริ่มต้นเป็น 0 (ทำให้ Dijkstra ไม่เริ่มทำงาน)

4. Directed Graphs

ใส่เส้นเชื่อมสลับทิศทางหรือไม่ครบตามโจทย์กำหนด

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

Why Dijkstra Wins?
สรุปความทรงพลัง

"ประสิทธิภาพที่เหนือชั้นในทางปฏิบัติ"

เป็นอัลกอริทึมที่ให้ผลลัพธ์ที่ถูกต้องที่สุดในกราฟบวก
ความเร็ว (O(V + E \log V)) เพียงพอสำหรับเกือบทุกสถานการณ์
เป็นรากฐานของอัลกอริทึมขั้นสูง เช่น A* หรือ Johnson's Algorithm

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

Morning Wrap-up
สรุปบทเรียนช่วงเช้าวันที่ 8

Core Dijkstra

Greedy selection of nearest node
Priority Queue for efficiency
Positive weights only!

Key Skills

Implementation with long long
Path reconstruction
Avoiding TLE with proper checks

"พักเที่ยง! กลับมาพบกับ Bellman-Ford และคู่อริอย่าง Negative Cycles"

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

Next Session Preview
เมื่อความละโมบ (Greedy) พ่ายแพ้

ในช่วงบ่าย เราจะมาดูสถานการณ์ที่ Dijkstra รับมือไม่ได้...
13.00 - 15.00 น. Shortest Paths II Bellman-Ford, Floyd-Warshall และการค้นหาเส้นทางในกราฟ "ติดลบ"

เตรียมโจทย์ CSES: Shortest Routes II ไว้รอกันได้เลยครับ

Shortest Paths I อัลกอริทึมของ Dijkstra

หัวข้อที่จะเรียนรู้

What is SSSP? นิยามปัญหาเส้นทางสั้นที่สุด

The Greedy Strategy แนวคิดพื้นฐาน: ความใกล้ชิดเป็นสำคัญ

Essential Constraint ข้อจำกัดสำคัญ: น้ำหนักต้องไม่ติดลบ

Priority Queue Efficiency โครงสร้างข้อมูลที่ใช้

Distance Array

Min-Priority Queue

Edge Relaxation การผ่อนคลายเส้นเชื่อม

Dijkstra's Process ลำดับการทำงานทีละขั้นตอน

Implementation in C++ ตัวอย่างโค้ดมาตรฐาน

Time Complexity วิเคราะห์ประสิทธิภาพ

BFS vs. Dijkstra ความแตกต่างที่ต้องจำ

BFS

Dijkstra

Path Reconstruction การหาเส้นทางจริงไม่ใช่แค่ระยะทาง

Dijkstra on Dense Graphs เมื่อกราฟมีเส้นเชื่อมหนาแน่นมาก

Zero-Weight Edges เส้นเชื่อมที่มีน้ำหนักเป็นศูนย์

"Dijkstra ยังคงทำงานได้ถูกต้อง!"

Why Processed Check? ความสำคัญของการตรวจสอบโหนดซ้ำ

Pathfinding on Grids การประยุกต์ใช้กับตาราง 2 มิติ

Multi-Source Dijkstra จุดเริ่มต้นหลายจุด

Min-Heap Implementation เทคนิคการใช้ Priority Queue ใน C++

แบบที่ 1: Negative Values

แบบที่ 2: std::greater

Why it Fails? กรณีตัวอย่างน้ำหนักติดลบ

Dijkstra on State Space การหาเส้นทางบน "สถานะ"

Scaling for Competition ขีดจำกัดและการประมวลผล

Counting Shortest Paths การนับจำนวนเส้นทางที่สั้นที่สุด

Dijkstra with std::set ทางเลือกอื่นในการ Implement

Priority Queue vs std::set เปรียบเทียบประสิทธิภาพ

Bidirectional Dijkstra การค้นหาจากสองทิศทาง

CSES: Shortest Routes I โจทย์ตัวอย่างคลาสสิก

Beware of Overflows! ระวังเรื่องชนิดข้อมูล

Memory Management การจองหน่วยความจำเพื่อความเร็ว

Debugging Tips ข้อผิดพลาดที่พบบ่อย

1. PQ Ordering

2. Processing Check

3. Initial dist[s]

4. Directed Graphs

Why Dijkstra Wins? สรุปความทรงพลัง

Morning Wrap-up สรุปบทเรียนช่วงเช้าวันที่ 8

Core Dijkstra

Key Skills

Next Session Preview เมื่อความละโมบ (Greedy) พ่ายแพ้

Shortest Paths I
อัลกอริทึมของ Dijkstra

What is SSSP?
นิยามปัญหาเส้นทางสั้นที่สุด

The Greedy Strategy
แนวคิดพื้นฐาน: ความใกล้ชิดเป็นสำคัญ

Essential Constraint
ข้อจำกัดสำคัญ: น้ำหนักต้องไม่ติดลบ

Priority Queue Efficiency
โครงสร้างข้อมูลที่ใช้

Edge Relaxation
การผ่อนคลายเส้นเชื่อม

Dijkstra's Process
ลำดับการทำงานทีละขั้นตอน

Implementation in C++
ตัวอย่างโค้ดมาตรฐาน

Time Complexity
วิเคราะห์ประสิทธิภาพ

BFS vs. Dijkstra
ความแตกต่างที่ต้องจำ

Path Reconstruction
การหาเส้นทางจริงไม่ใช่แค่ระยะทาง

Dijkstra on Dense Graphs
เมื่อกราฟมีเส้นเชื่อมหนาแน่นมาก

Zero-Weight Edges
เส้นเชื่อมที่มีน้ำหนักเป็นศูนย์

Why Processed Check?
ความสำคัญของการตรวจสอบโหนดซ้ำ

Pathfinding on Grids
การประยุกต์ใช้กับตาราง 2 มิติ

Multi-Source Dijkstra
จุดเริ่มต้นหลายจุด

Min-Heap Implementation
เทคนิคการใช้ Priority Queue ใน C++

Why it Fails?
กรณีตัวอย่างน้ำหนักติดลบ

Dijkstra on State Space
การหาเส้นทางบน "สถานะ"

Scaling for Competition
ขีดจำกัดและการประมวลผล

Counting Shortest Paths
การนับจำนวนเส้นทางที่สั้นที่สุด

Dijkstra with std::set
ทางเลือกอื่นในการ Implement

Priority Queue vs std::set
เปรียบเทียบประสิทธิภาพ

Bidirectional Dijkstra
การค้นหาจากสองทิศทาง

CSES: Shortest Routes I
โจทย์ตัวอย่างคลาสสิก

Beware of Overflows!
ระวังเรื่องชนิดข้อมูล

Memory Management
การจองหน่วยความจำเพื่อความเร็ว

Debugging Tips
ข้อผิดพลาดที่พบบ่อย

Why Dijkstra Wins?
สรุปความทรงพลัง

Morning Wrap-up
สรุปบทเรียนช่วงเช้าวันที่ 8

Next Session Preview
เมื่อความละโมบ (Greedy) พ่ายแพ้