Search⌘ K
AI Features
Home
Courses
Mastering Algorithms for Problem Solving in C++

Solution: All-Pairs Shortest Paths

Explore the implementation of Johnson’s algorithm to compute all-pairs shortest paths in a graph or identify negative cycles. Understand the integration of Bellman-Ford and Dijkstra’s algorithms and their time complexity. This lesson provides a detailed algorithmic solution and hands-on C++ code to enhance your graph algorithm skills.

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 C++ 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

  1. Let G=(V,E)G = (V, E) be the input graph, with vertices VV and edges EE.
  2. Add a new vertex ss to GG and add zero-weight edges from ss
...