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

Challenge: All-Pairs Shortest Paths

Explore how to implement the all-pairs shortest paths algorithm in Java with a focus on detecting negative cycles. Learn to modify Johnson's algorithm by combining Bellman-Ford and Dijkstra’s techniques to compute shortest paths or identify negative cycles in weighted graphs.

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)
...