Time complexity of the floyd algorithm for shortest path
Floyd: the shortest path between each pair of nodes.The Floyd-Warshall
algorithm is an algorithm for solving the shortest path between any two points, which can correctly deal with directed graphs or negatively-weighted shortest path problems The Floyd-Warshall algorithm has a time complexity of O(N3) and a space complexity of O(N2).
Dijkstra: O(n2) applies to single-source shortest paths for graphs with non-negative weights, with Fibonacci heap complexity O(E+VlgV),
BellmanFord: applies to single-source shortest paths for graphs with weights that have negative values and are capable of detecting negative circles, with complexity O(VE)
SPFA: single-source shortest path for graphs with negative weights and no negative circles, complexity O(kE) in the paper, k is the number of times each node enters the Queue, and k is generally <=2, but the complexity here proves to be problematic, in fact, the worst case of SPFA should be O(VE).
The conclusion is given first:
(1) When the weights are non-negative, Dijkstra is used.
(2) When the weights have negative values and there are no negative loops, SPFA is used, which detects the negative loops but cannot output them.
(3)When the weights have negative values and there may be negative circles, then BellmanFord is used, which is able to detect and output negative circles.
(4)SPFA detects negative loops: when there exists a point into the queue greater than or equal to V times, there are negative loops, as proven later.
Data structure] shortest path of Dijkstra’s (Dijkstra) algorithm and Floyd’s (Floyd) algorithm
Dijkstra’s (Dijkstra) algorithm core: according to the order of the increasing path length to produce the shortest path.
Dijkstra (Dijkstra) algorithm steps: (the shortest path from v0 to v8 in the graph) is not the shortest path from v0 to v8 at once, but step by step to find the shortest path of the vertices between them, over the course of the process are based on the shortest path that has been found on the basis of the shortest path to the vertices farther away from the shortest path, and ultimately the shortest path to the end of the source and end point.
Floyd (Floyd) algorithm is a classical dynamic programming algorithm.
Advantages and Disadvantages Analysis of Floyd Algorithm
Floyd algorithm is applicable to APSP (AllPairsShortestPaths, Multi-source Shortest Paths), a dynamic planning algorithm that works best for dense graphs, where edge weights can be either positive or negative. This algorithm is simple and effective, due to the compact structure of the triple loop, for dense graphs, the efficiency is higher than the execution of |V| times Dijkstra’s algorithm, but also higher than the execution of V times SPFA algorithm.
Advantages: easy to understand, can calculate the shortest distance between any two nodes, simple code writing.
Disadvantages: time complexity is relatively high, not suitable for calculating large amounts of data.