Floyd-Warshall
ফ্লয়েড-ওয়ারশল
Dynamic programming দিয়ে সব node pair-এর shortest path — intermediate vertex হিসেবে k একে একে যোগ করে তিন nested loop-এ O(V³)।
also: floyd warshall, all pairs shortest paths
প্রশ্ন মাত্র একটা: i→j যেতে k-কে intermediate বানানো ভালো, না করা?
for k in range(V):
for i in range(V):
for j in range(V):
if d[i][k] + d[k][j] < d[i][j]:
d[i][j] = d[i][k] + d[k][j]Dense graph-এ (E ≈ V²) V বার Dijkstra চালানোর চেয়ে সোজা আর খরচও কাছাকাছি। Negative cycle detect করতে শেষে d[i][i] < 0 দেখো।
Edge-গুলো boolean হলে min-এর জায়গায় OR বসিয়েই transitive closure বের হয়। Rolling array দিয়ে memory O(V³) থেকে O(V²)-তে নামে।