แหล่งอ้างอิง: https://cses.fi/book/book.pdf
Dijkstra ตั้งอยู่บนสมมติฐานแบบ Greedy: โหนดที่ใกล้ที่สุดที่ถูกเลือกจะไม่ถูกปรับปรุงอีก
แหล่งอ้างอิง: https://roadmap.sh/datastructures-and-algorithms
คุณสมบัติหลัก:
แหล่งอ้างอิง: https://www.geeksforgeeks.org/bellman-ford-algorithm-dp-23/
ในขณะที่ Dijkstra เลือกโหนดที่ใกล้ที่สุดมาพิจารณาเพื่อนบ้าน แต่ Bellman-Ford จะพิจารณา "เส้นเชื่อมทุกเส้น" ในกราฟซ้ำๆ
แหล่งอ้างอิง: https://cses.fi/book/book.pdf
1. distance[source] = 0, others = INF
2. for i = 1 to n-1 rounds:
for each edge (u, v) with weight w:
if distance[u] + w < distance[v]:
distance[v] = distance[u] + w
3. check for negative cycles (round n)
แหล่งอ้างอิง: https://usaco.guide/CPH.pdf
"จะเกิดอะไรขึ้นถ้าเราวนรอบที่ (n)?"
หากหลังจากทำครบ (n-1) รอบแล้ว เรายังสามารถลดระยะทาง (Relax) ได้อีกในรอบที่ (n) แสดงว่ามีวงรอบที่ผลรวมน้ำหนักติดลบอยู่ ซึ่งหมายความว่า ไม่มีทางสั้นที่สุดที่แท้จริง เพราะคุณสามารถเดินวนเพื่อลดระยะทางลงได้เรื่อยๆ จนถึง (-\infty)
แหล่งอ้างอิง: https://cses.fi/book/book.pdf
"ทำไมต้องพิจารณาเส้นเชื่อมทุกเส้นในทุกรอบ?"
แหล่งอ้างอิง: https://www.geeksforgeeks.org/shortest-path-faster-algorithm/
คำนวณหาระยะทางสั้นที่สุด d(u, v) สำหรับทุกๆ คู่ของโหนด u, v ในกราฟ
• รัน Dijkstra จำนวน V ครั้ง: (O(V \cdot E \log V))
• ใช้ Floyd-Warshall: เขียนโค้ดง่ายที่สุดและรองรับน้ำหนักติดลบ
แหล่งอ้างอิง: https://cses.fi/book/book.pdf
"ผ่านโหนด k หรือไม่?"
หัวใจหลักคือการใช้ Dynamic Programming โดยพิจารณาว่า เส้นทางจาก i ไป j จะสั้นลงไหมถ้าเราเลือกเดิน ผ่านโหนดตัวกลาง k
แหล่งอ้างอิง: https://www.geeksforgeeks.org/floyd-warshall-algorithm-dp-16/
// 3 Nested Loops: k ต้องเป็น loop นอกสุดเสมอ!
for (int k = 1; k <= n; k++) {
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]);
}
}
}
แหล่งอ้างอิง: https://cses.fi/book/book.pdf
struct Edge { int a, b, w; };
vector<Edge> edges;
for (int i = 1; i <= n-1; i++) {
for (auto e : edges) {
dist[e.b] = min(dist[e.b], dist[e.a] + e.w);
}
}
// หมายเหตุ: ควรใช้ long long สำหรับระยะทางเพื่อป้องกัน Overflow
แหล่งอ้างอิง: https://cses.fi/book/book.pdf
หลังจากทำครบ (n-1) รอบแล้ว ให้ทำการวนรอบที่ (n) อีกหนึ่งครั้ง:
แหล่งอ้างอิง: https://roadmap.sh/datastructures-and-algorithms
การบันทึกเส้นทางใน Bellman-Ford ทำได้เช่นเดียวกับ Dijkstra:
แหล่งอ้างอิง: https://cses.fi/book/book.pdf
แทนที่จะตรวจเส้นเชื่อมทุกเส้น ให้เราตรวจเฉพาะโหนดที่ระยะทาง "เพิ่งเปลี่ยน" เท่านั้น:
แหล่งอ้างอิง: https://www.geeksforgeeks.org/shortest-path-faster-algorithm/
"ระยะทางสั้นที่สุดจาก i ไป j โดยใช้โหนดตัวกลางจากเซต (1, 2, ..., k)"
dp[k][i][j] = min(dp[k-1][i][j], dp[k-1][i][k] + dp[k-1][k][j])
เราสามารถลดมิติของอาร์เรย์เหลือเพียง 2 มิติได้ในทางปฏิบัติเพื่อประหยัดหน่วยความจำ
แหล่งอ้างอิง: https://cses.fi/book/book.pdf
เราสามารถดัดแปลง Floyd-Warshall เพื่อตรวจสอบว่าโหนด (u) สามารถไปถึงโหนด (v) ได้หรือไม่:
แหล่งอ้างอิง: https://www.geeksforgeeks.org/transitive-closure-of-a-graph/
ขั้นตอนการเก็บข้อมูล:
แหล่งอ้างอิง: https://www.geeksforgeeks.org/finding-shortest-path-between-any-two-nodes-using-floyd-warshall-algorithm/
| Algorithm | Type | Complexity | Negative Edges |
|---|---|---|---|
| Dijkstra | SSSP | (O(E \log V)) | No |
| Bellman-Ford | SSSP | (O(V \cdot E)) | Yes |
| SPFA | SSSP | (O(k \cdot E)) avg | Yes |
| Floyd-Warshall | All-Pairs | (O(V^3)) | Yes |
"SSSP = Single-Source Shortest Path"
Floyd-Warshall ใช้ (N^2) bytes หาก (N=500) จะใช้พื้นที่ (500^2 \times 8) bytes (\approx 2MB) ซึ่งปลอดภัยมาก
อย่าใช้ 0x3f3f3f3f กับ long long หากค่าน้ำหนักมีโอกาสรวมกันเกิน (2 \times 10^9) ให้ใช้ 1e18 หรือ LLONG_MAX
ลืมตั้งค่า (dist[i][i] = 0) ใน Floyd-Warshall มักเป็นสาเหตุของบั๊กยอดนิยม
โจทย์มักถามหา "Negative Cycle" โดยตรง ให้ใช้ Bellman-Ford หรือ Floyd-Warshall (เช็ค (dist[i][i] < 0))
แหล่งอ้างอิง: https://roadmap.sh/datastructures-and-algorithms
แหล่งฝึกฝน: https://cses.fi/problemset/
วันนี้เราผ่าน SSSP ที่ทรงพลังอย่าง Dijkstra
และก้าวข้ามขีดจำกัดด้วย Bellman-Ford รวมถึงความเรียบง่ายของ Floyd-Warshall
"เครื่องมือพร้อมแล้ว ถึงเวลาเปลี่ยนทฤษฎีเป็นผลลัพธ์ในการเขียนโปรแกรม"
"ไปลุยต่อในช่วง Practice (15:00 - 17:00 น.) กันครับ!"