Master Floyd Warshall for APSP and see when a Dijkstra-per-source loop beats it. Clear intuition, Python code, and complexity breakdown.<\/p>\n\n\n\n
Here’s the [Problem Link<\/span><\/mark><\/a><\/strong>] to begin with.<\/p>\n\n\n Given an n \u00d7 n<\/em><\/strong> weighted graph matrix We will implement both and compare.<\/p>\n\n\n\n This is classic DP on triples<\/strong> \u2013 indices mean \u201cshortest path that only uses Total complexity scales with 1. Problem in one line<\/h2>\n\n\n\n
dist<\/code>, replace each dist[i][j]<\/code> with the weight of the shortest path<\/strong> from vertex i<\/code> to vertex j<\/code>. 10**8<\/code> stands for \u201c\u221e\u201d.<\/p>\n\n\n\n
\n\n\n\n2. Why two algorithms?<\/h2>\n\n\n\n
Goal<\/th> Works with negative edges?<\/th> Typical graph size<\/th><\/tr><\/thead> Floyd Warshall<\/strong> \u2013 triple-loop DP<\/td> \u2705 (no negative cycles)<\/td> small\/medium dense<\/td><\/tr> Dijkstra from every source<\/strong> \u2013 heap<\/td> \u274c (needs \u2265 0 weights)<\/td> larger sparse<\/td><\/tr><\/tbody><\/table><\/figure>\n\n\n\n
\n\n\n\n3. Intuition & approach<\/h2>\n\n\n\n
3.1\u2002Floyd Warshall (dynamic programming)<\/h3>\n\n\n\n
\n
via<\/code> as a possible intermediate stop<\/strong>.<\/li>\n\n\n\n(i, j)<\/code> test whether going i \u2192 via \u2192 j<\/code> is cheaper than the best path already known.<\/li>\n\n\n\nvia \u2208 [0, n-1]<\/code>. After n<\/code> rounds, every indirect shortcut is tried.<\/li>\n<\/ol>\n\n\n\n
vertices \u2264 via as intermediates\u201d.<\/p>\n\n\n\n3.2\u2002Dijkstra run
n<\/code> times<\/strong><\/h3>\n\n\n\n\n
\u221e<\/code> entries.<\/li>\n\n\n\nsrc<\/code> run standard min-heap Dijkstra<\/strong> to fill row src<\/code>.<\/li>\n\n\n\nn<\/code> times the cost of one Dijkstra.<\/p>\n\n\n\n
\n\n\n\n4. Python code<\/h2>\n\n\n\n
4.1 Floyd Warshall<\/h3>\n\n\n\n