Finding Shortest Path and Minimum Distance Between Any Two Points Using Floyd's Algorithm

Floyd's algorithm is a classical dynamic programming algorithm used to solve the shortest path problem between any two points in weighted graphs. The algorithm takes an adjacency matrix as input and gradually updates matrix values to obtain final shortest path results through an iterative optimization process.

The core concept utilizes intermediate nodes to optimize path distances. For each vertex k in the graph, we consider it as an intermediate node and check whether passing through k can shorten the path distance from vertex i to vertex j. When a shorter path is identified, the corresponding distance value is updated.

The implementation consists of three main stages: initialization phase, iterative update phase, and path reconstruction phase. During initialization, the algorithm uses the given adjacency matrix D0 where diagonal elements are set to 0 (indicating zero distance from a node to itself) and unreachable node pairs are set to infinity.

The iterative update phase represents the core of Floyd's algorithm. It employs triple nested loops to update the distance matrix: the outer loop iterates through all possible intermediate nodes k, while the middle and inner loops traverse all starting points i and ending points j respectively. In each iteration, the algorithm compares the direct distance from i to j with the distance passing through k, selecting the smaller value as the new distance.

Path reconstruction can be performed after completing the distance matrix calculation. By maintaining a path matrix that records intermediate nodes along shortest paths, specific routes can be traced back through recursive reconstruction.

Floyd's algorithm has a time complexity of O(n³), where n represents the number of nodes in the graph. This makes it particularly suitable for shortest path calculations in dense graphs. Despite the cubic complexity, the algorithm implementation remains concise and can compute all-pairs shortest paths in a single execution.

Notably, Floyd's algorithm can handle graphs with negative-weight edges but cannot process graphs containing negative-weight cycles, as shortest paths may not exist in such cases (one could infinitely traverse negative cycles to reduce path length).