Computer scienceAlgorithms and Data StructuresAlgorithmsGraph algorithmsShortest path algorithms

Johnson's algorithm

Worst-case complexity

Report a typo

As we mentioned, Johnson's algorithm is optimal for sparse graphs. On the other hand, if the graph is complete, our algorithm will work no faster than other standard all-pairs algorithms. What will be its time complexity in the case of complete graphs?

Denote $|V| = n$ ∣ and $|E| = m$ .

Select one option from the list

O(n^2)

O(n^2\log n)

O(n^2\log n + m^2)

O(n^3)

___

Create a free account to access the full topic