Floyd algorithm is an algorithm to find the shortest path between multi-source points in a given weighted graph. Similar to Diskstra algorithm, the difference is that Diskstra calculates the shortest path between single source points. Floyd algorithm is a path analysis algorithm often used in mathematical modeling and daily work.

Floyd, as a typical algorithm for finding the shortest path from multiple sources, is an algorithm for finding the shortest path between any two points, and its idea is based on the idea of dynamic programming.

See-Chapter 1 Algorithm Basis-Analysis Types of Basic Algorithms.

Freud's core idea is also based on the theory of dynamic programming, and the process is relatively simple.

Let it be expressed as the shortest path length with the node in (1…k) as the intermediate node of the process from point I to point J, then:

(1) If the shortest path passes through point K, then =+

(2) If the shortest path does not pass through point k, then =.

So =

The time complexity of Floyd algorithm is, and the space complexity is.