Computer scienceAlgorithms and data structuresAlgorithmsGraph algorithmsShortest path algorithms

Johnson's algorithm

Optimal graph

Report a typo

Given two directed weighted graphs as shown in the picture below:

two directed weighted graphs

On which graph Johnson's algorithm runs considerably faster than standard all-pairs algorithms?

Select one option from the list

Graph 1

Graph 2

Both

Johnson's algorithm fails to work correctly for both graphs, as negative weights are present

Create a free account to access the full topic