Computer scienceAlgorithms and Data StructuresAlgorithmsGraph algorithmsShortest path algorithms

Johnson's algorithm

A node's purpose

Report a typo

During the first step of our algorithm, we add a new node and connect it to all other nodes. What is the main purpose of this step?

Select one option from the list

To make sure the graph is strongly connected so that all-pairs shortest paths exist.

To add more edges to the graph so that Johnson's algorithm can be optimal.

To reduce the time taken by the Bellmam-Ford algorithm in step 2.

To help eliminate negative weights later on so that Dijkstra's algorithm works correctly.

___

Create a free account to access the full topic