Floyd Algorithm for Shortest Path Calculation with Path Reconstruction

The Floyd-Warshall algorithm represents a fundamental dynamic programming approach for determining shortest paths in weighted graphs. The implementation constructs a distance matrix (dist) to store minimal distances between all vertex pairs, initialized with direct edge weights. Through triple-nested iteration over vertices, the algorithm systematically compares direct paths against intermediary routes via vertex k, updating the matrix when dist[i][k] + dist[k][j] yields a shorter path than dist[i][j].

Path reconstruction is achieved through a parallel predecessor matrix (path) that tracks intermediate vertices. Each distance update triggers corresponding path matrix modifications using path[i][j] = path[k][j] to enable backward traversal. The code incorporates recursive path unpacking functions that navigate the predecessor matrix to construct complete vertex sequences. Extensive commenting elucidates matrix initialization procedures, core relaxation logic in O(n³) complexity, and path retrieval mechanisms using stack-based or recursive approaches. This implementation demonstrates Floyd's algorithm's versatility in handling dense graphs and negative-weight edges (without negative cycles), making it indispensable for network analysis and routing applications.