Computer scienceAlgorithms and Data StructuresAlgorithmsGraph algorithmsShortest path algorithms

Comparing the shortest path algorithms

Back to Alice

Report a typo

Remember the graph from Alice's paper on gravitational interaction? It is also known as $K_5$ graph.

Graph and adjacency matrix

The task remains unchanged: calculate all-pairs shortest paths. Which algorithm is more efficient in this case?

Select one option from the list

Johnson's algorithm

Floyd-Warshall algorithm

Both — for this graph, their time complexities are equal

None — negative edges are present, hence they both work incorrectly

___

Create a free account to access the full topic