Search⌘ K
Home
Courses
Mastering Algorithms for Problem Solving in Java

Solution: All-Pairs Shortest Paths

Explore the implementation of Johnson’s algorithm for solving all-pairs shortest paths in a weighted graph. Understand how to detect negative cycles with Bellman-Ford, reweight edges, and run Dijkstra’s algorithm efficiently in Java. Gain practical skills by analyzing and coding this solution to enhance your algorithmic problem-solving.

We'll cover the following...

Let's practice what we've learned so far.

Task

The algorithms described in this chapter can also be modified to return an explicit description of some negative cycle in the input graph GG, if one exists, instead of only reporting whether or not GG contains a negative cycle. Analyze the provided algorithm and then provide its Java implementation in the coding workspace provided below.

Logic building

Here’s an algorithm for the modified version of Johnson’s algorithm that returns either the array of all shortest-path distances or a negative cycle.

Algorithm

  • Let G=(V,E)G = (V, E) be the input graph, with vertices VV and edges EE.
  • Add a new vertex ss to GG and add zero-weight edges from ss to all vertices in VV.
  • Run the Bellman-Ford algorithm with ss as the source vertex to compute a new set of edge weights h:E−>Rh: E -> R that satisfy the following property: for any edge (u,v)(u, v)
...