Johnson's algorithm
You are encouraged to solve this task according to the task description, using any language you may know.
- Johnson's Algorithm
Johnson's algorithm is a procedure for finding the shortest paths between all pairs of vertices in a sparse, edge-weighted, directed graph. It combines elements of the Bellman-Ford algorithm and Dijkstra's algorithm to achieve better performance than the Floyd-Warshall algorithm for sparse graphs.
- Problem Description
- Input
- A directed graph where is the set of vertices and is the set of edges
- A weight function that assigns a real-valued weight to each edge
- The graph may contain negative-weight edges but must not contain any negative-weight cycles
- Output
- A matrix where contains the weight of the shortest path from vertex to vertex
- If no path exists from to ,
- Constraints
- The graph must not contain any negative-weight cycles
- Time complexity:
- Space complexity:
- Key Insight
The key insight of Johnson's algorithm is the use of a reweighting technique to transform all edge weights to be non-negative, while preserving shortest path relationships. This allows the use of Dijkstra's algorithm (which requires non-negative edge weights) for each vertex as a source.
- Applications
Johnson's algorithm is particularly useful in:
- Sparse graphs where is much smaller than
- Network routing optimization
- Traffic flow analysis
- Resource allocation problems
- Any context requiring all-pairs shortest paths in a sparse graph with potential negative edges
C++
#include <cstdint>
#include <iostream>
#include <limits>
#include <map>
#include <optional>
#include <queue>
#include <vector>
constexpr double INF{std::numeric_limits<double>::max()};
struct Edge {
uint32_t u;
uint32_t v;
double weight;
};
struct Vertex_and_Weight {
uint32_t vertex;
double weight;
};
/**
* Return a list of shortest path distances from the source vertex in the original graph to all other vertices
*/
std::vector<double> dijkstra_algorithm(
const uint32_t& vertex_count,
std::map<uint32_t, std::vector<Vertex_and_Weight>>& reweighted_adjacencies,
const uint32_t& source_vertex,
const std::vector<double>& values) {
std::vector<double> distances(vertex_count, INF);
distances[source_vertex] = 0.0;
auto compare = [](const Vertex_and_Weight& a, const Vertex_and_Weight& b) { return a.weight > b.weight; };
std::priority_queue<Vertex_and_Weight, std::vector<Vertex_and_Weight>, decltype(compare)> priority_queue;
priority_queue.emplace(Vertex_and_Weight(source_vertex, 0.0));
std::vector<double> final_distances(vertex_count, INF);
while ( ! priority_queue.empty() ) {
Vertex_and_Weight vertex_and_Weight = priority_queue.top();
priority_queue.pop();
const uint32_t vertex = vertex_and_Weight.vertex;
if ( vertex_and_Weight.weight > distances[vertex] ) {
continue;
}
// Store the final shortest path distance, translated back to the distance in the original graph
// which prevents processing vertices disconnected from the source vertex
if ( final_distances[vertex] == INF ) {
if ( distances[vertex] == INF ) { // This should not happen, but is included as a safety check
final_distances[vertex] = INF;
} else {
// Translate distance back to its original weight: d(u,v) = d'(u,v) - h[u] + h[v]
final_distances[vertex] = distances[vertex] - values[source_vertex] + values[vertex];
}
}
// Relax the edges outgoing from vertex
if ( reweighted_adjacencies.contains(vertex) ) {
for ( Vertex_and_Weight pair : reweighted_adjacencies[vertex] ) {
if ( distances[vertex] != INF
&& distances[vertex] + pair.weight < distances[pair.vertex] ) {
distances[pair.vertex] = distances[vertex] + pair.weight;
priority_queue.emplace(Vertex_and_Weight(pair.vertex, distances[pair.vertex]));
}
}
}
}
// Translate distance back to its original weight for any remaining reachable vertices
// This handles cases where a vertex was reachable, but was not the minimum vertex
// removed from the priority queue when its final distance was determined.
for ( uint32_t i = 0; i < vertex_count; ++i ) {
if ( final_distances[i] == INF && distances[i] != INF ) {
final_distances[i] = distances[i] - values[source_vertex] + values[i];
}
}
return final_distances;
}
/**
* Return a list of shortest distances from the source vertex to all other vertices,
* or an empty optional if a negative cycle is detected
*/
std::optional<std::vector<double>> bellman_ford_algorithm(
const uint32_t& augmented_vertex_count, const std::vector<Edge>& edges, const uint32_t& source_vertex) {
std::vector<double> distances(augmented_vertex_count, INF);
distances[source_vertex] = 0.0;
// Relax the edges (augmentedVertexCount - 1) times
bool updated = true;
for ( uint32_t i = 0; i < augmented_vertex_count - 1 && updated; ++i ) {
updated = false;
for ( uint32_t j = 0; j < edges.size(); ++j ) {
Edge edge = edges[j];
if ( distances[edge.u] != INF && distances[edge.u] + edge.weight < distances[edge.v] ) {
distances[edge.v] = distances[edge.u] + edge.weight;
updated = true;
}
}
}
// Check for negative cycles in the graph
for ( const Edge& edge : edges ) {
if ( distances[edge.u] != INF && distances[edge.u] + edge.weight < distances[edge.v] ) {
return std::nullopt; // Indicates to the calling method that a negative cycle has been detected
}
}
return distances;
}
/**
* Return the shortest path between all pairs of vertices in an edge weighted directed graph
* For a full description of the algorithm visit https://en.wikipedia.org/wiki/Johnson%27s_algorithm
*/
std::optional<std::vector<std::vector<double>>> johnsons_algorithm(const std::vector<std::vector<double>>& graph) {
const uint32_t vertex_count = graph.size();
std::vector<Edge> original_edges;
// Step 0: Build a list of edges for the original graph
for ( uint32_t i = 0; i < vertex_count; ++i ) {
for ( uint32_t j = 0; j < vertex_count; ++j ) {
const double weight = graph[i][j];
if ( i == j ) {
if ( weight != 0.0 ) {
std::cout << "Warning: graph[i][i] for i = " << i << " is " << weight
<< ", expected to be 0.0, resetting it to 0.0" << std::endl;
}
} else if ( weight != INF ) {
original_edges.emplace_back(Edge(i, j, weight));
}
}
}
// Step 1: Form the augmented graph
// Add a new vertex with index 'vertex_count' and having 0-weight edges to all the original vertices
std::vector<Edge> augmented_edges = original_edges;
for ( uint32_t i = 0; i < vertex_count; ++i ) {
augmented_edges.emplace_back(Edge(vertex_count, i, 0.0));
}
// Step 2: Invoke the Bellman-Ford Algorithm starting from the new vertex
std::optional<std::vector<double>> h_values =
bellman_ford_algorithm(vertex_count + 1, augmented_edges, vertex_count);
if ( ! h_values ) {
return std::nullopt; // A negative cycle was detected by the Bellman-Ford Algorithm
}
std::vector<double> values = h_values.value();
values.pop_back(); // Remove the value for the augmented vertex
// Step 3: Reweight the edges
std::map<uint32_t, std::vector<Vertex_and_Weight>> reweighted_adjacencies;
for ( const Edge& edge : original_edges ) {
// Ensure the 'values' are valid before reweighting
if ( values[edge.u] == INF || values[edge.v] == INF ) {
// This can happen if the original graph was not strongly connected to the augmented vertex.
// While not strictly an error for Johnson's Algorithm, because paths might still exist between
// reachable nodes, it means the reweighting might involve INF.
// Computation can proceed since Dijkstra's Algorithm can handle INF.
std::cout << "Warning: invalid hValues detected by the Bellman-Ford Algorithm." << std::endl;
}
const double reweight = edge.weight + values[edge.u] - values[edge.v];
reweighted_adjacencies[edge.u].emplace_back(Vertex_and_Weight(edge.v, reweight));
}
// Step 4: Invoke Dijkstra's Algorithm starting from each vertex on the reweighted graph
std::vector<std::vector<double>> all_pairs_shortest_paths;
for ( uint32_t u = 0; u < vertex_count; ++u ) {
all_pairs_shortest_paths.emplace_back(dijkstra_algorithm(vertex_count, reweighted_adjacencies, u, values));
}
// Step 5: Return the result matrix
return all_pairs_shortest_paths;
}
int main() {
// The element (i, j) is the weight of the edge from vertex i to vertex j.
// INF, for infinity, means that there is no edge from vertex i to vertex j.
const std::vector<std::vector<double>> graph = {
{ 0.0, -5.0, 2.0, 3.0 },
{ INF, 0.0, 4.0, INF },
{ INF, INF, 0.0, 1.0 },
{ INF, INF, INF, 0.0 } };
const std::optional<std::vector<std::vector<double>>> result = johnsons_algorithm(graph);
if ( result ) {
std::cout << "All pairs shortest paths:" << std::endl;
std::cout << "The element (i, j) is the shortest path between vertex i and vertex j." << std::endl;
for ( const std::vector<double>& row : result.value() ) {
std::cout << "[";
for ( const double& number : row ) {
if ( number == INF ) {
std::cout << "INF ";
} else {
std::cout << number << " ";
}
}
std::cout << "]" << std::endl;
}
} else {
std::cout << "A negative cycle was detected in the graph." << std::endl;
}
}
- Output:
All pairs shortest paths: The element (i, j) is the shortest path between vertex i and vertex j. [0 -5 -1 0 ] [INF 0 4 5 ] [INF INF 0 1 ] [INF INF INF 0 ]
FreeBASIC
Const INF As Integer = &H7FFFFFFF
Type Edge
u As Integer
v As Integer
w As Integer
End Type
Function BellmanFord(num_vertices As Integer, edges() As Edge, source As Integer, dist() As Integer) As Boolean
Dim As Integer i, j, updated
For i = 0 To num_vertices - 1
dist(i) = INF
Next
dist(source) = 0
' Relax edges V-1 times
For i = 1 To num_vertices - 1
updated = 0
For j = 0 To Ubound(edges)
With edges(j)
If dist(.u) <> INF Andalso dist(.u) + .w < dist(.v) Then
dist(.v) = dist(.u) + .w
updated = 1
End If
End With
Next
' If no update in a full pass, we can stop early
If updated = 0 Then Exit For
Next
' Check for negative cycles
For j = 0 To Ubound(edges)
With edges(j)
If dist(.u) <> INF Andalso dist(.u) + .w < dist(.v) Then
Print "Graph contains a negative weight cycle"
Return False
End If
End With
Next
Return True
End Function
Sub Dijkstra(num_vertices As Integer, adj() As Edge, source As Integer, h() As Integer, result() As Integer, row As Integer)
Dim As Integer visited(num_vertices - 1), dist(num_vertices - 1)
Dim As Integer i, min_dist, u, cnt
For i = 0 To num_vertices - 1
dist(i) = INF
visited(i) = 0
Next
dist(source) = 0
For cnt = 0 To num_vertices - 1
min_dist = INF
For i = 0 To num_vertices - 1
If visited(i) = 0 Andalso dist(i) < min_dist Then
min_dist = dist(i)
u = i
End If
Next
If min_dist = INF Then Exit For
visited(u) = 1
For i = 0 To Ubound(adj)
With adj(i)
If .u = u Then
If dist(u) <> INF Andalso dist(u) + .w < dist(.v) Then dist(.v) = dist(u) + .w
End If
End With
Next
Next
For i = 0 To num_vertices - 1
result(row, i) = Iif(dist(i) <> INF, dist(i) - h(source) + h(i), INF)
Next
End Sub
Sub JohnsonsAlgorithm(graph() As Integer, result() As Integer)
Dim As Integer V = Ubound(graph, 1) + 1
Dim As Edge edges(), augmented_edges()
Dim As Integer h(V)
Dim As Integer i, j, k
' --- Step 0: Handle Input and Build Edge List for Original Graph ---
k = 0
Redim edges(-1)
For i = 0 To V - 1
For j = 0 To V - 1
If i <> j Andalso graph(i, j) <> 0 Then
Redim Preserve edges(k)
edges(k).u = i
edges(k).v = j
edges(k).w = graph(i, j)
k += 1
End If
Next
Next
' --- Step 1: Form the augmented graph G' ---
Redim augmented_edges(Ubound(edges) + V)
For i = 0 To Ubound(edges)
augmented_edges(i) = edges(i)
Next
For i = 0 To V - 1
augmented_edges(Ubound(edges) + 1 + i).u = V
augmented_edges(Ubound(edges) + 1 + i).v = i
augmented_edges(Ubound(edges) + 1 + i).w = 0
Next
' --- Step 2: Run Bellman-Ford from the new source 's' ---
If Not BellmanFord(V + 1, augmented_edges(), V, h()) Then
Print "Negative cycle detected in the graph."
Exit Sub
End If
' --- Step 3: Reweight the edges ---
For i = 0 To Ubound(edges)
edges(i).w += h(edges(i).u) - h(edges(i).v)
Next
' --- Step 4: Run Dijkstra from each vertex on the reweighted graph ---
Redim result(V - 1, V - 1)
For i = 0 To V - 1
Dijkstra(V, edges(), i, h(), result(), i)
Next
End Sub
' --- Test Case ---
Dim graph(3, 3) As Integer = { _
{0, -5, 2, 3}, _
{0, 0, 4, 0}, _ ' Assuming 0 means no edge from 1->0 and 1->3
{0, 0, 0, 1}, _ ' Assuming 0 means no edge from 2->0 and 2->1
{0, 0, 0, 0} } ' Assuming 0 means no edge from 3->0, 3->1, 3->2
Dim As Integer result(3, 3)
JohnsonsAlgorithm(graph(), result())
Print "All-pairs shortest paths:"
For i As Integer = 0 To 3
For j As Integer = 0 To 3
If result(i, j) = INF Then
Print "INF ";
Else
Print Using "## "; result(i, j);
End If
Next
Print
Next
Sleep
- Output:
All-pairs shortest paths: 0 -5 -1 0 INF 0 4 5 INF INF 0 1 INF INF INF 0
Go
package main
import (
"container/heap"
"fmt"
"math"
)
const INF = math.MaxFloat64
type Edge struct {
u, v int
weight float64
}
type VertexAndWeight struct {
v int
weight float64
}
type WeightAndVertex struct {
weight float64
vertex int
}
// Priority queue implementation for Dijkstra's algorithm
type PriorityQueue []WeightAndVertex
func (pq PriorityQueue) Len() int { return len(pq) }
func (pq PriorityQueue) Less(i, j int) bool { return pq[i].weight < pq[j].weight }
func (pq PriorityQueue) Swap(i, j int) { pq[i], pq[j] = pq[j], pq[i] }
func (pq *PriorityQueue) Push(x interface{}) {
*pq = append(*pq, x.(WeightAndVertex))
}
func (pq *PriorityQueue) Pop() interface{} {
old := *pq
n := len(old)
item := old[n-1]
*pq = old[0 : n-1]
return item
}
func main() {
// The element (i, j) is the weight of the edge from vertex i to vertex j.
// INF, for infinity, means that there is no edge from vertex i to vertex j.
graph := [][]float64{
{0.0, -5.0, 2.0, 3.0},
{INF, 0.0, 4.0, INF},
{INF, INF, 0.0, 1.0},
{INF, INF, INF, 0.0},
}
result, hasNegativeCycle := johnsonsAlgorithm(graph)
if !hasNegativeCycle {
fmt.Println("All pairs shortest paths:")
fmt.Println("The element (i, j) is the shortest path between vertex i and vertex j.")
for _, row := range result {
fmt.Print("[")
for _, number := range row {
if number == INF {
fmt.Print("INF ")
} else {
fmt.Printf("%v ", number)
}
}
fmt.Println("]")
}
} else {
fmt.Println("A negative cycle was detected in the graph.")
}
}
// johnsonsAlgorithm returns the shortest path between all pairs of vertices in an edge weighted directed graph
// and a boolean indicating whether a negative cycle was detected
func johnsonsAlgorithm(graph [][]float64) ([][]float64, bool) {
vertexCount := len(graph)
originalEdges := []Edge{}
// Step 0: Build a list of edges for the original graph
for i := 0; i < vertexCount; i++ {
for j := 0; j < vertexCount; j++ {
weight := graph[i][j]
if i == j {
if weight != 0.0 {
fmt.Printf("Warning: graph[i][i] for i = %d is %v, expected to be 0.0, resetting it to 0.0\n", i, weight)
}
} else if weight != INF {
originalEdges = append(originalEdges, Edge{i, j, weight})
}
}
}
// Step 1: Form the augmented graph
// Add a new vertex with index 'vertexCount' and having 0-weight edges to all the original vertices
augmentedEdges := make([]Edge, len(originalEdges))
copy(augmentedEdges, originalEdges)
for i := 0; i < vertexCount; i++ {
augmentedEdges = append(augmentedEdges, Edge{vertexCount, i, 0.0})
}
// Step 2: Invoke the Bellman-Ford Algorithm starting from the new vertex
hValues, hasNegativeCycle := bellmanFordAlgorithm(vertexCount+1, augmentedEdges, vertexCount)
if hasNegativeCycle {
return nil, true // A negative cycle was detected by the Bellman-Ford Algorithm
}
values := hValues[:vertexCount] // Remove the value for the augmented vertex
// Step 3: Reweight the edges
reweightedAdjacencies := make(map[int][]VertexAndWeight)
for v := 0; v < vertexCount; v++ {
reweightedAdjacencies[v] = []VertexAndWeight{}
}
for _, edge := range originalEdges {
// Ensure the 'values' are valid before reweighting
if values[edge.u] == INF || values[edge.v] == INF {
// This can happen if the original graph was not strongly connected to the augmented vertex.
// While not strictly an error for Johnson's Algorithm, because paths might still exist between
// reachable nodes, it means the reweighting might involve INF.
// Computation can proceed since Dijkstra's Algorithm can handle INF.
fmt.Println("Warning: invalid hValues detected by the Bellman-Ford Algorithm.")
}
reweight := edge.weight + values[edge.u] - values[edge.v]
reweightedAdjacencies[edge.u] = append(reweightedAdjacencies[edge.u], VertexAndWeight{edge.v, reweight})
}
// Step 4: Invoke Dijkstra's Algorithm starting from each vertex on the reweighted graph
allPairsShortestPaths := make([][]float64, vertexCount)
for u := 0; u < vertexCount; u++ {
allPairsShortestPaths[u] = dijkstraAlgorithm(vertexCount, reweightedAdjacencies, u, values)
}
// Step 5: Return the result matrix
return allPairsShortestPaths, false
}
// bellmanFordAlgorithm returns a list of shortest distances from the source vertex to all other vertices,
// and a boolean indicating whether a negative cycle was detected
func bellmanFordAlgorithm(augmentedVertexCount int, edges []Edge, sourceVertex int) ([]float64, bool) {
distances := make([]float64, augmentedVertexCount)
for i := range distances {
distances[i] = INF
}
distances[sourceVertex] = 0.0
// Relax the edges (augmentedVertexCount - 1) times
updated := true
for i := 0; i < augmentedVertexCount-1 && updated; i++ {
updated = false
for j := 0; j < len(edges); j++ {
edge := edges[j]
if distances[edge.u] != INF && distances[edge.u]+edge.weight < distances[edge.v] {
distances[edge.v] = distances[edge.u] + edge.weight
updated = true
}
}
}
// Check for negative cycles in the graph
for _, edge := range edges {
if distances[edge.u] != INF && distances[edge.u]+edge.weight < distances[edge.v] {
return nil, true // Indicates to the calling method that a negative cycle has been detected
}
}
return distances, false
}
// dijkstraAlgorithm returns a list of shortest path distances from the source vertex in the original graph to all other vertices
func dijkstraAlgorithm(vertexCount int, reweightedAdjacencies map[int][]VertexAndWeight, sourceVertex int, values []float64) []float64 {
distances := make([]float64, vertexCount)
for i := range distances {
distances[i] = INF
}
distances[sourceVertex] = 0.0
pq := make(PriorityQueue, 0)
heap.Init(&pq)
heap.Push(&pq, WeightAndVertex{0.0, sourceVertex})
finalDistances := make([]float64, vertexCount)
for i := range finalDistances {
finalDistances[i] = INF
}
for pq.Len() > 0 {
weightAndVertex := heap.Pop(&pq).(WeightAndVertex)
vertex := weightAndVertex.vertex
if weightAndVertex.weight > distances[vertex] {
continue
}
// Store the final shortest path distance, translated back to the distance in the original graph
// which prevents processing vertices disconnected from the source vertex
if finalDistances[vertex] == INF {
if distances[vertex] == INF { // This should not happen, but is included as a safety check
finalDistances[vertex] = INF
} else {
// Translate distance back to its original weight: d(u,v) = d'(u,v) - h[u] + h[v]
finalDistances[vertex] = distances[vertex] - values[sourceVertex] + values[vertex]
}
}
// Relax the edges outgoing from vertex
if adjList, exists := reweightedAdjacencies[vertex]; exists {
for _, pair := range adjList {
if distances[vertex] != INF && distances[vertex]+pair.weight < distances[pair.v] {
distances[pair.v] = distances[vertex] + pair.weight
heap.Push(&pq, WeightAndVertex{distances[pair.v], pair.v})
}
}
}
}
// Translate distance back to its original weight for any remaining reachable vertices
// This handles cases where a vertex was reachable, but was not the minimum vertex
// removed from the priority queue when its final distance was determined.
for i := 0; i < vertexCount; i++ {
if finalDistances[i] == INF && distances[i] != INF {
finalDistances[i] = distances[i] - values[sourceVertex] + values[i]
}
}
return finalDistances
}
- Output:
All pairs shortest paths: The element (i, j) is the shortest path between vertex i and vertex j. [0 -5 -1 0 ] [INF 0 4 5 ] [INF INF 0 1 ] [INF INF INF 0 ]
Java
import java.util.AbstractQueue;
import java.util.ArrayList;
import java.util.List;
import java.util.Map;
import java.util.Optional;
import java.util.PriorityQueue;
import java.util.function.Function;
import java.util.stream.Collectors;
import java.util.stream.IntStream;
import java.util.stream.Stream;
public final class JohnsonsAlgorithm {
public static void main(String[] args) {
// The element (i, j) is the weight of the edge from vertex i to vertex j.
// INF, for infinity, means that there is no edge from vertex i to vertex j.
List<List<Double>> graph = List.of(
List.of( 0.0, -5.0, 2.0, 3.0 ),
List.of( INF, 0.0, 4.0, INF ),
List.of( INF, INF, 0.0, 1.0 ),
List.of( INF, INF, INF, 0.0 ) );
Optional<List<List<Double>>> result = johnsonsAlgorithm(graph);
if ( result.isPresent() ) {
System.out.println("All pairs shortest paths:");
System.out.println("The element (i, j) is the shortest path between vertex i and vertex j.");
for ( List<Double> row : result.get() ) {
System.out.print("[");
for ( double number : row ) {
System.out.print(( number == INF ) ? "INF " : number + " ");
}
System.out.println("]");
}
} else {
System.out.println("A negative cycle was detected in the graph.");
}
}
/**
* Return the shortest path between all pairs of vertices in an edge weighted directed graph
* For a full description of the algorithm visit https://en.wikipedia.org/wiki/Johnson%27s_algorithm
*/
private static Optional<List<List<Double>>> johnsonsAlgorithm(List<List<Double>> graph) {
final int vertexCount = graph.size();
List<Edge> originalEdges = new ArrayList<Edge>();
// Step 0: Build a list of edges for the original graph
IntStream.range(0, vertexCount).forEach( i -> {
IntStream.range(0, vertexCount).forEach( j -> {
final double weight = graph.get(i).get(j);
if ( i == j ) {
if ( weight != 0.0 ) {
System.out.println("Warning: graph[i][i] for i = " + i + " is " + weight
+ ", expected to be 0.0, resetting it to 0.0");
}
} else if ( weight != INF ) {
originalEdges.addLast( new Edge(i, j, weight) );
}
} );
} );
// Step 1: Form the augmented graph
// Add a new vertex with index 'vertexCount' and having 0-weight edges to all the original vertices
List<Edge> augmentedEdges = Stream.concat(originalEdges.stream(),
Stream.iterate(0, i -> i + 1 ).limit(vertexCount).map( i -> new Edge(vertexCount, i, 0.0) )).toList();
// Step 2: Invoke the Bellman-Ford Algorithm starting from the new vertex
Optional<List<Double>> hValues = bellmanFordAlgorithm(vertexCount + 1, augmentedEdges, vertexCount);
if ( hValues.isEmpty() ) {
return Optional.empty(); // A negative cycle was detected by the Bellman-Ford Algorithm
}
List<Double> values = hValues.get();
values.removeLast(); // Remove the value for the augmented vertex
// Step 3: Reweight the edges
Map<Integer, List<VertexAndWeight>> reweightedAdjacencies = IntStream.range(0, vertexCount).boxed()
.collect(Collectors.toMap(Function.identity(), v -> new ArrayList<VertexAndWeight>() ));
originalEdges.stream().forEach( edge -> {
// Ensure the 'values' are valid before reweighting
if ( values.get(edge.u) == INF || values.get(edge.v) == INF ) {
// This can happen if the original graph was not strongly connected to the augmented vertex.
// While not strictly an error for Johnson's Algorithm, because paths might still exist between
// reachable nodes, it means the reweighting might involve INF.
// Computation can proceed since Dijkstra's Algorithm can handle INF.
System.out.println("Warning: invalid hValues detected by the Bellman-Ford Algorithm.");
}
final double reweight = edge.weight + values.get(edge.u) - values.get(edge.v);
reweightedAdjacencies.get(edge.u).addLast( new VertexAndWeight(edge.v, reweight) );
} );
// Step 4: Invoke Dijkstra's Algorithm starting from each vertex on the reweighted graph
List<List<Double>> allPairsShortestPaths = IntStream.range(0, vertexCount).boxed()
.map( u -> dijkstraAlgorithm(vertexCount, reweightedAdjacencies, u, values) ).toList();
// Step 5: Return the result matrix
return Optional.of(allPairsShortestPaths);
}
/**
* Return a list of shortest distances from the source vertex to all other vertices,
* or an empty optional if a negative cycle is detected
*/
private static Optional<List<Double>> bellmanFordAlgorithm(
int augmentedVertexCount, List<Edge> edges, int sourceVertex) {
List<Double> distances = Stream.generate( () -> INF ).limit(augmentedVertexCount).collect(Collectors.toList());
distances.set(sourceVertex, 0.0);
// Relax the edges (augmentedVertexCount - 1) times
boolean updated = true;
for ( int i = 0; i < augmentedVertexCount - 1 && updated; i++ ) {
updated = false;
for ( int j = 0; j < edges.size(); j++ ) {
Edge edge = edges.get(j);
if ( distances.get(edge.u) != INF && distances.get(edge.u) + edge.weight < distances.get(edge.v) ) {
distances.set(edge.v, distances.get(edge.u) + edge.weight);
updated = true;
}
}
}
// Check for negative cycles in the graph
for ( Edge edge : edges ) {
if ( distances.get(edge.u) != INF && distances.get(edge.u) + edge.weight < distances.get(edge.v) ) {
return Optional.empty(); // Indicates to the calling method that a negative cycle has been detected
}
}
return Optional.of(distances);
}
/**
* Return a list of shortest path distances from the source vertex in the original graph to all other vertices
*/
private static List<Double> dijkstraAlgorithm(int vertexCount,
Map<Integer, List<VertexAndWeight>> reweightedAdjacencies, int sourceVertex, List<Double> values) {
List<Double> distances = IntStream.range(0, vertexCount).boxed().map( i -> INF ).collect(Collectors.toList());
distances.set(sourceVertex, 0.0);
AbstractQueue<VertexAndWeight> priorityQueue =
new PriorityQueue<VertexAndWeight>( (a, b) -> Double.compare(a.weight, b.weight) );
priorityQueue.add( new VertexAndWeight(sourceVertex, 0.0) );
List<Double> finalDistances = IntStream.range(0, vertexCount).boxed()
.map( i -> INF ).collect(Collectors.toList());
while ( ! priorityQueue.isEmpty() ) {
VertexAndWeight vertexAndWeigth = priorityQueue.remove();
final int vertex = vertexAndWeigth.vertex;
if ( vertexAndWeigth.weight > distances.get(vertex) ) {
continue;
}
// Store the final shortest path distance, translated back to the distance in the original graph
// which prevents processing vertices disconnected from the source vertex
if ( finalDistances.get(vertex) == INF ) {
if ( distances.get(vertex) == INF ) { // This should not happen, but is included as a safety check
finalDistances.set(vertex, INF);
} else {
// Translate distance back to its original weight: d(u,v) = d'(u,v) - h[u] + h[v]
finalDistances.set(vertex, distances.get(vertex) - values.get(sourceVertex) + values.get(vertex));
}
}
// Relax the edges outgoing from vertex
if ( reweightedAdjacencies.containsKey(vertex) ) {
for ( VertexAndWeight pair : reweightedAdjacencies.get(vertex) ) {
if ( distances.get(vertex) != INF
&& distances.get(vertex) + pair.weight < distances.get(pair.vertex) ) {
distances.set(pair.vertex, distances.get(vertex) + pair.weight);
priorityQueue.add( new VertexAndWeight(pair.vertex, distances.get(pair.vertex)) );
}
}
}
}
// Translate distance back to its original weight for any remaining reachable vertices
// This handles cases where a vertex was reachable, but was not the minimum vertex
// removed from the priority queue when its final distance was determined.
IntStream.range(0, vertexCount).forEach( i -> {
if ( finalDistances.get(i) == INF && distances.get(i) != INF ) {
finalDistances.set(i, distances.get(i) - values.get(sourceVertex) + values.get(i));
}
} );
return finalDistances;
}
private record Edge(int u, int v, double weight) {}
private record VertexAndWeight(int vertex, double weight) {}
private static final double INF = Double.MAX_VALUE;
}
- Output:
All pairs shortest paths: The element (i, j) is the shortest path between vertex i and vertex j. [0.0 -5.0 -1.0 0.0 ] [INF 0.0 4.0 5.0 ] [INF INF 0.0 1.0 ] [INF INF INF 0.0 ]
JavaScript
// Johnson's Algorithm Implementation in JavaScript
// This algorithm finds all-pairs shortest paths in a weighted directed graph
// Constants
const INF = Number.MAX_VALUE;
// Edge class representing a directed edge from vertex u to vertex v with a weight
class Edge {
constructor(u, v, weight) {
this.u = u;
this.v = v;
this.weight = weight;
}
}
// VertexAndWeight class for use in Dijkstra's algorithm
class VertexAndWeight {
constructor(v, weight) {
this.v = v;
this.weight = weight;
}
}
// WeightAndVertex class for use in the priority queue in Dijkstra's algorithm
class WeightAndVertex {
constructor(weight, vertex) {
this.weight = weight;
this.vertex = vertex;
}
}
// PriorityQueue implementation for Dijkstra's algorithm
class PriorityQueue {
constructor() {
this.items = [];
}
enqueue(weightAndVertex) {
let added = false;
for (let i = 0; i < this.items.length; i++) {
if (weightAndVertex.weight < this.items[i].weight) {
this.items.splice(i, 0, weightAndVertex);
added = true;
break;
}
}
if (!added) {
this.items.push(weightAndVertex);
}
}
dequeue() {
if (this.isEmpty()) return null;
return this.items.shift();
}
isEmpty() {
return this.items.length === 0;
}
}
/**
* Bellman-Ford algorithm to find shortest paths from a source vertex to all other vertices
* Returns null if there is a negative cycle
*/
function bellmanFordAlgorithm(augmentedVertexCount, edges, sourceVertex) {
// Initialize distances array with INF, except for the source vertex
const distances = Array(augmentedVertexCount).fill(INF);
distances[sourceVertex] = 0.0;
// Relax the edges (augmentedVertexCount - 1) times
let updated = true;
for (let i = 0; i < augmentedVertexCount - 1 && updated; i++) {
updated = false;
for (let j = 0; j < edges.length; j++) {
const edge = edges[j];
if (distances[edge.u] !== INF && distances[edge.u] + edge.weight < distances[edge.v]) {
distances[edge.v] = distances[edge.u] + edge.weight;
updated = true;
}
}
}
// Check for negative cycles in the graph
for (const edge of edges) {
if (distances[edge.u] !== INF && distances[edge.u] + edge.weight < distances[edge.v]) {
return null; // Indicates a negative cycle has been detected
}
}
return distances;
}
/**
* Dijkstra's algorithm to find shortest paths from a source vertex to all other vertices
* in a graph with non-negative edge weights
*/
function dijkstraAlgorithm(vertexCount, reweightedAdjacencies, sourceVertex, values) {
// Initialize distances array with INF
const distances = Array(vertexCount).fill(INF);
distances[sourceVertex] = 0.0;
const priorityQueue = new PriorityQueue();
priorityQueue.enqueue(new WeightAndVertex(0.0, sourceVertex));
const finalDistances = Array(vertexCount).fill(INF);
while (!priorityQueue.isEmpty()) {
const weightAndVertex = priorityQueue.dequeue();
const vertex = weightAndVertex.vertex;
if (weightAndVertex.weight > distances[vertex]) {
continue;
}
// Store the final shortest path distance, translated back to the distance in the original graph
if (finalDistances[vertex] === INF) {
if (distances[vertex] === INF) { // This should not happen, but is included as a safety check
finalDistances[vertex] = INF;
} else {
// Translate distance back to its original weight: d(u,v) = d'(u,v) - h[u] + h[v]
finalDistances[vertex] = distances[vertex] - values[sourceVertex] + values[vertex];
}
}
// Relax the edges outgoing from vertex
if (reweightedAdjacencies.has(vertex)) {
for (const pair of reweightedAdjacencies.get(vertex)) {
if (distances[vertex] !== INF && distances[vertex] + pair.weight < distances[pair.v]) {
distances[pair.v] = distances[vertex] + pair.weight;
priorityQueue.enqueue(new WeightAndVertex(distances[pair.v], pair.v));
}
}
}
}
// Translate distance back to its original weight for any remaining reachable vertices
for (let i = 0; i < vertexCount; i++) {
if (finalDistances[i] === INF && distances[i] !== INF) {
finalDistances[i] = distances[i] - values[sourceVertex] + values[i];
}
}
return finalDistances;
}
/**
* Johnson's algorithm to find shortest paths between all pairs of vertices
* in a weighted directed graph which may contain negative edge weights
*/
function johnsonsAlgorithm(graph) {
const vertexCount = graph.length;
const originalEdges = [];
// Step 0: Build a list of edges for the original graph
for (let i = 0; i < vertexCount; i++) {
for (let j = 0; j < vertexCount; j++) {
const weight = graph[i][j];
if (i === j) {
if (weight !== 0.0) {
console.log(`Warning: graph[i][i] for i = ${i} is ${weight}, expected to be 0.0, resetting it to 0.0`);
}
} else if (weight !== INF) {
originalEdges.push(new Edge(i, j, weight));
}
}
}
// Step 1: Form the augmented graph
// Add a new vertex with index 'vertexCount' and having 0-weight edges to all the original vertices
const augmentedEdges = [...originalEdges];
for (let i = 0; i < vertexCount; i++) {
augmentedEdges.push(new Edge(vertexCount, i, 0.0));
}
// Step 2: Invoke the Bellman-Ford Algorithm starting from the new vertex
const hValues = bellmanFordAlgorithm(vertexCount + 1, augmentedEdges, vertexCount);
if (hValues === null) {
return null; // A negative cycle was detected by the Bellman-Ford Algorithm
}
// Remove the value for the augmented vertex
hValues.pop();
// Step 3: Reweight the edges
const reweightedAdjacencies = new Map();
for (let i = 0; i < vertexCount; i++) {
reweightedAdjacencies.set(i, []);
}
for (const edge of originalEdges) {
// Ensure the 'hValues' are valid before reweighting
if (hValues[edge.u] === INF || hValues[edge.v] === INF) {
// This can happen if the original graph was not strongly connected to the augmented vertex.
// While not strictly an error for Johnson's Algorithm, because paths might still exist between
// reachable nodes, it means the reweighting might involve INF.
// Computation can proceed since Dijkstra's Algorithm can handle INF.
console.log("Warning: invalid hValues detected by the Bellman-Ford Algorithm.");
}
const reweight = edge.weight + hValues[edge.u] - hValues[edge.v];
reweightedAdjacencies.get(edge.u).push(new VertexAndWeight(edge.v, reweight));
}
// Step 4: Invoke Dijkstra's Algorithm starting from each vertex on the reweighted graph
const allPairsShortestPaths = [];
for (let u = 0; u < vertexCount; u++) {
allPairsShortestPaths.push(dijkstraAlgorithm(vertexCount, reweightedAdjacencies, u, hValues));
}
// Step 5: Return the result matrix
return allPairsShortestPaths;
}
// Example usage
function main() {
// The element (i, j) is the weight of the edge from vertex i to vertex j.
// INF, for infinity, means that there is no edge from vertex i to vertex j.
const graph = [
[0.0, -5.0, 2.0, 3.0],
[INF, 0.0, 4.0, INF],
[INF, INF, 0.0, 1.0],
[INF, INF, INF, 0.0]
];
const result = johnsonsAlgorithm(graph);
if (result) {
console.log("All pairs shortest paths:");
console.log("The element (i, j) is the shortest path between vertex i and vertex j.");
for (const row of result) {
let rowStr = "[";
for (const number of row) {
rowStr += (number === INF) ? "INF " : number + " ";
}
rowStr += "]";
console.log(rowStr);
}
} else {
console.log("A negative cycle was detected in the graph.");
}
}
// Run the example
main();
- Output:
All pairs shortest paths: The element (i, j) is the shortest path between vertex i and vertex j. [0 -5 -1 0 ] [INF 0 4 5 ] [INF INF 0 1 ] [INF INF INF 0 ]
Julia
using Graphs
const edges = [(1, 2), (1, 3), (1, 4), (2, 3), (3, 4)]
const weights = [Inf -5.0 2.0 3.0; Inf 0.0 4.0 Inf; Inf Inf 0.0 1.0; Inf Inf Inf 0.0]
g = SimpleGraph(4) # 4 vertices
for (v1, v2) in edges # edge vertices are from a one-based vertex array
add_edge!(g, v1, v2)
end
johnson_state = johnson_shortest_paths(g, weights)
display(johnson_state.dists)
- Output:
4×4 Matrix{Float64}:
0.0 -5.0 -1.0 0.0
Inf 0.0 4.0 5.0
Inf Inf 0.0 1.0
Inf Inf Inf 0.0
Phix
constant inf = 1e308*1e308
// bellmanFordAlgorithm returns a list of shortest distances from the source vertex to all other vertices,
// and a boolean indicating whether a negative cycle was detected
function bellmanFordAlgorithm(integer augmentedVertexCount, sequence edges, integer sourceVertex)
sequence distances := repeat(inf, augmentedVertexCount)
distances[sourceVertex] = 0.0
// Relax the edges (augmentedVertexCount - 1) times
integer u, v
atom weight
for i=1 to augmentedVertexCount-1 do
bool updated = false
for edge in edges do
{u,v,weight} = edge
if distances[u] != inf and distances[u]+weight < distances[v] then
distances[v] = distances[u] + weight
updated = true
end if
end for
if not updated then exit end if
end for
// Check for negative cycles in the graph
for edge in edges do
{u,v,weight} = edge
if distances[u] != inf and distances[u]+weight < distances[v] then
return {{}, true} // Indicates to the calling method that a negative cycle has been detected
end if
end for
return {distances, false}
end function
// dijkstraAlgorithm returns a list of shortest path distances from the source vertex in the original graph to all other vertices
function dijkstraAlgorithm(integer vertexCount, sequence reweightedAdjacencies, integer sourceVertex, sequence vals)
sequence distances := repeat(inf, vertexCount),
finalDistances := repeat(inf, vertexCount)
distances[sourceVertex] = 0.0
integer pq := pq_new()
pq_add({sourceVertex,0.0},pq)
atom weight
integer vertex, v
while pq_size(pq) do
{vertex,weight} = pq_pop(pq)
if weight <= distances[vertex] then
// Store the final shortest path distance, translated back to the distance in the original graph
// which prevents processing vertices disconnected from the source vertex
if finalDistances[vertex] == inf then
if distances[vertex] == inf then // This should not happen, but is included as a safety check
finalDistances[vertex] = inf
else
// Translate distance back to its original weight: d(u,v) = d'(u,v) - h[u] + h[v]
finalDistances[vertex] = distances[vertex] - vals[sourceVertex] + vals[vertex]
end if
end if
// Relax the edges outgoing from vertex
sequence adjList := reweightedAdjacencies[vertex]
for pair in adjList do
{v,weight} = pair
if distances[vertex] != inf and distances[vertex]+weight < distances[v] then
distances[v] = distances[vertex] + weight
pq_add({v,distances[v]},pq)
end if
end for
end if
end while
pq_destroy(pq)
// Translate distance back to its original weight for any remaining reachable vertices
// This handles cases where a vertex was reachable, but was not the minimum vertex
// removed from the priority queue when its final distance was determined.
for i=1 to vertexCount do
if finalDistances[i] == inf and distances[i] != inf then
finalDistances[i] = distances[i] - vals[sourceVertex] + vals[i]
end if
end for
return finalDistances
end function
// johnsonsAlgorithm returns the shortest path between all pairs of vertices in an edge weighted directed graph
// and a boolean indicating whether a negative cycle was detected
function johnsonsAlgorithm(sequence graph)
integer vertexCount := length(graph)
sequence originalEdges := {}
// Step 0: Build a list of edges for the original graph
for i=1 to vertexCount do
for j=1 to vertexCount do
atom weight := graph[i][j]
if i == j then
assert(weight==0.0)
elsif weight != inf then
originalEdges = append(originalEdges, {i, j, weight})
end if
end for
end for
// Step 1: Form the augmented graph
// Add a new vertex with index 'vertexCount' and having 0-weight edges to all the original vertices
sequence augmentedEdges := deep_copy(originalEdges)
for i=1 to vertexCount do
augmentedEdges = append(augmentedEdges, {vertexCount+1, i, 0.0})
end for
// Step 2: Invoke the Bellman-Ford Algorithm starting from the new vertex
{sequence hValues, bool hasNegativeCycle} := bellmanFordAlgorithm(vertexCount+1, augmentedEdges, vertexCount+1)
if hasNegativeCycle then
return {{}, true} // A negative cycle was detected by the Bellman-Ford Algorithm
end if
sequence vals := hValues[1..vertexCount] // Remove the value for the augmented vertex
// Step 3: Reweight the edges
sequence reweightedAdjacencies := repeat({},vertexCount)
integer u, v
atom weight
for edge in originalEdges do
{u,v,weight} = edge
// Ensure the 'vals' are valid before reweighting
if vals[u] == inf or vals[v] == inf then
// This can happen if the original graph was not strongly connected to the augmented vertex.
// While not strictly an error for Johnson's Algorithm, because paths might still exist between
// reachable nodes, it means the reweighting might involve INF.
// Computation can proceed since Dijkstra's Algorithm can handle INF.
printf(1,"Warning: invalid hValues detected by the Bellman-Ford Algorithm.\n")
end if
atom reweight := weight + vals[u] - vals[v]
reweightedAdjacencies[u] = append(reweightedAdjacencies[u], {v, reweight})
end for
// Step 4: Invoke Dijkstra's Algorithm starting from each vertex on the reweighted graph
sequence allPairsShortestPaths := repeat(0, vertexCount)
for u=1 to vertexCount do
allPairsShortestPaths[u] = dijkstraAlgorithm(vertexCount, reweightedAdjacencies, u, vals)
end for
// Step 5: Return the result matrix
return {allPairsShortestPaths, false}
end function
// The element (i, j) is the weight of the edge from vertex i to vertex j.
// inf, for infinity, means that there is no edge from vertex i to vertex j.
sequence graph := {{0.0,-5.0, 2.0, 3.0},
{inf, 0.0, 4.0, inf},
{inf, inf, 0.0, 1.0},
{inf, inf, inf, 0.0}}
{sequence result, bool hasNegativeCycle} := johnsonsAlgorithm(graph)
if hasNegativeCycle then
printf(1,"A negative cycle was detected in the graph.\n")
else
printf(1,"All pairs shortest paths:\n")
printf(1,"The element (i, j) is the shortest path between vertex i and vertex j.\n")
pp(result,{pp_Nest,1})
end if
- Output:
All pairs shortest paths:
The element (i, j) is the shortest path between vertex i and vertex j.
{{0,-5,-1,0},
{inf,0,4,5},
{inf,inf,0,1},
{inf,inf,inf,0}}
Python
import heapq
import itertools # Used for counter in Bellman-Ford
INF = float('inf')
def bellman_ford(num_vertices, edges, source):
"""
Runs Bellman-Ford algorithm from a source vertex.
Args:
num_vertices: The total number of vertices (including the augmented source).
edges: A list of tuples (u, v, weight) representing directed edges.
source: The index of the source vertex.
Returns:
A list of shortest distances 'h' from the source to all other vertices,
or None if a negative cycle is detected.
"""
dist = [INF] * num_vertices
dist[source] = 0
# Relax edges V-1 times
for _ in range(num_vertices - 1):
updated = False
for u, v, weight in edges:
if dist[u] != INF and dist[u] + weight < dist[v]:
dist[v] = dist[u] + weight
updated = True
# If no update in a full pass, we can stop early
if not updated:
break
# Check for negative cycles
for u, v, weight in edges:
if dist[u] != INF and dist[u] + weight < dist[v]:
print("Graph contains a negative weight cycle")
return None # Indicate negative cycle
return dist
def dijkstra(num_vertices, adj, source, h_values):
"""
Runs Dijkstra's algorithm on a potentially re-weighted graph.
Args:
num_vertices: The number of vertices in the original graph.
adj: Adjacency list of the re-weighted graph {u: [(v, reweighted_weight), ...]}.
source: The source vertex index for this run.
h_values: The potential values calculated by Bellman-Ford.
Returns:
A list of shortest path distances from the source in the original graph.
"""
dist = [INF] * num_vertices
dist[source] = 0
# Priority queue stores (distance, vertex)
pq = [(0, source)]
final_dist = [INF] * num_vertices # To store results
while pq:
d, u = heapq.heappop(pq)
# If we found a shorter path already, skip
if d > dist[u]:
continue
# Store the final shortest path distance (translated back)
# This check prevents processing nodes disconnected from source
if final_dist[u] == INF:
if dist[u] == INF: # Should not happen if popped from pq, but safety check
final_dist[u] = INF
else:
# Translate distance back to original weight: d(u,v) = d'(u,v) - h[u] + h[v]
# Here, d'(source, u) is dist[u]
# So, original distance = dist[u] - h[source] + h[u]
final_dist[u] = dist[u] - h_values[source] + h_values[u]
# Relax edges outgoing from u
if u in adj:
for v, reweighted_weight in adj[u]:
if dist[u] != INF and dist[u] + reweighted_weight < dist[v]:
dist[v] = dist[u] + reweighted_weight
heapq.heappush(pq, (dist[v], v))
# After Dijkstra finishes, translate any remaining reachable vertices
# This handles cases where a node might be reachable but wasn't the
# minimum popped from PQ when its final distance was determined.
for i in range(num_vertices):
if final_dist[i] == INF and dist[i] != INF:
final_dist[i] = dist[i] - h_values[source] + h_values[i]
return final_dist
def johnsons_algorithm(graph_matrix):
"""
Implements Johnson's algorithm for all-pairs shortest paths.
Args:
graph_matrix: An adjacency matrix representation of the graph.
graph_matrix[i][j] is the weight of the edge from i to j.
Use 0 for non-existent edges between different nodes (or INF).
graph_matrix[i][i] should be 0.
Returns:
A matrix containing the shortest path distances between all pairs,
or None if a negative cycle is detected. Returns INF if no path exists.
"""
V = len(graph_matrix)
original_edges = []
# --- Step 0: Handle Input and Build Edge List for Original Graph ---
# Be careful about 0 vs non-existent edge. Assume 0 means no edge if i != j
for i in range(V):
for j in range(V):
weight = graph_matrix[i][j]
# Only add edges that exist. Assuming 0 means no edge unless i==j.
# If 0 could be a valid edge weight, use INF for non-edges in input.
if i == j:
if weight != 0:
print(f"Warning: graph_matrix[{i}][{i}] is {weight}, expected 0. Setting to 0.")
# Optional: Raise error instead? Or just proceed assuming 0?
# graph_matrix[i][i] = 0 # Correct it if needed by Bellman-Ford/Dijkstra logic
elif weight != 0: # Assuming 0 means non-edge here
original_edges.append((i, j, weight))
# If 0 IS a valid weight, the condition should be:
# elif weight != INF: # Use INF in the input matrix for non-edges
# original_edges.append((i, j, weight))
# --- Step 1: Form the augmented graph G' ---
# Add a new vertex 's' (index V) with 0-weight edges to all original vertices
augmented_edges = list(original_edges)
for i in range(V):
augmented_edges.append((V, i, 0)) # New source V connects to all others
num_vertices_augmented = V + 1
# --- Step 2: Run Bellman-Ford from the new source 's' ---
h_values = bellman_ford(num_vertices_augmented, augmented_edges, V)
if h_values is None:
# Negative cycle detected by Bellman-Ford
return None
# Remove the h value for the augmented source, we only need it for original vertices
h_values = h_values[:V] # Keep h[0] to h[V-1]
# --- Step 3: Reweight the edges ---
reweighted_adj = {i: [] for i in range(V)}
for u, v, weight in original_edges:
# Ensure h values are valid before reweighting
if h_values[u] == INF or h_values[v] == INF:
# This can happen if the original graph wasn't strongly connected
# from the augmented source 's'. While not strictly an error for
# Johnson's (paths might still exist between reachable nodes),
# it means the reweighting might involve INF.
# Let's compute the reweighted value anyway; Dijkstra handles INF.
pass # Or print a warning if desired
reweighted_weight = weight + h_values[u] - h_values[v]
# Theoretically, reweighted_weight should be >= 0 if no negative cycle
# Add small tolerance for floating point issues if necessary:
# if reweighted_weight < -1e-9:
# print(f"Warning: Potential negative reweighted edge {u}->{v}: {reweighted_weight}")
reweighted_adj[u].append((v, reweighted_weight))
# --- Step 4: Run Dijkstra from each vertex on the reweighted graph ---
all_pairs_shortest_paths = [[INF for _ in range(V)] for _ in range(V)]
for u in range(V):
# Run Dijkstra on the reweighted graph starting from u
shortest_paths_from_u = dijkstra(V, reweighted_adj, u, h_values)
all_pairs_shortest_paths[u] = shortest_paths_from_u
# The dijkstra implementation now directly calculates the original distance
# --- Step 5: Return the result matrix ---
return all_pairs_shortest_paths
# --- Test Case ---
graph = [[0, -5, 2, 3],
[0, 0, 4, 0], # Assuming 0 means no edge from 1->0 and 1->3
[0, 0, 0, 1], # Assuming 0 means no edge from 2->0 and 2->1
[0, 0, 0, 0]] # Assuming 0 means no edge from 3->0, 3->1, 3->2
result = johnsons_algorithm(graph)
if result:
print("All-pairs shortest paths:")
for row in result:
print([x if x != INF else "INF" for x in row])
else:
print("Negative cycle detected in the graph.")
print("\nExpected for the test case:")
print("[0, -5, -1, 0]")
print("['INF', 0, 4, 5]")
print("['INF', 'INF', 0, 1]")
print("['INF', 'INF', 'INF', 0]")
- Output:
All-pairs shortest paths: [0, -5, -1, 0] ['INF', 0, 4, 5] ['INF', 'INF', 0, 1] ['INF', 'INF', 'INF', 0] Expected for the test case: [0, -5, -1, 0] ['INF', 0, 4, 5] ['INF', 'INF', 0, 1] ['INF', 'INF', 'INF', 0]
Rust
use std::cmp::Ordering;
use std::collections::{BinaryHeap, HashMap};
use std::f64::MAX as INF;
#[derive(Debug, Clone, Copy)]
struct Edge {
u: usize,
v: usize,
weight: f64,
}
#[derive(Debug, Clone, Copy)]
struct VertexAndWeight {
v: usize,
weight: f64,
}
// Custom wrapper for f64 to implement Ord
#[derive(Debug, Clone, Copy)]
struct OrderedFloat(f64);
impl PartialEq for OrderedFloat {
fn eq(&self, other: &Self) -> bool {
self.0.eq(&other.0)
}
}
// This is technically not sound for NaN values, but for our algorithm we won't have NaN
impl Eq for OrderedFloat {}
impl PartialOrd for OrderedFloat {
fn partial_cmp(&self, other: &Self) -> Option<Ordering> {
self.0.partial_cmp(&other.0)
}
}
impl Ord for OrderedFloat {
fn cmp(&self, other: &Self) -> Ordering {
self.partial_cmp(other).unwrap_or(Ordering::Equal)
}
}
#[derive(Debug, Clone, Copy, PartialEq, Eq)]
struct WeightAndVertex {
weight: OrderedFloat,
vertex: usize,
}
impl PartialOrd for WeightAndVertex {
fn partial_cmp(&self, other: &Self) -> Option<Ordering> {
Some(self.cmp(other))
}
}
impl Ord for WeightAndVertex {
fn cmp(&self, other: &Self) -> Ordering {
// Min heap (reverse ordering)
other.weight.cmp(&self.weight)
}
}
fn johnsons_algorithm(graph: &Vec<Vec<f64>>) -> Option<Vec<Vec<f64>>> {
let vertex_count = graph.len();
let mut original_edges = Vec::new();
// Step 0: Build a list of edges for the original graph
for i in 0..vertex_count {
for j in 0..vertex_count {
let weight = graph[i][j];
if i == j {
if weight != 0.0 {
println!("Warning: graph[i][i] for i = {} is {}, expected to be 0.0, resetting it to 0.0", i, weight);
}
} else if weight != INF {
original_edges.push(Edge { u: i, v: j, weight });
}
}
}
// Step 1: Form the augmented graph
// Add a new vertex with index 'vertex_count' and having 0-weight edges to all the original vertices
let mut augmented_edges = original_edges.clone();
for i in 0..vertex_count {
augmented_edges.push(Edge { u: vertex_count, v: i, weight: 0.0 });
}
// Step 2: Invoke the Bellman-Ford Algorithm starting from the new vertex
let h_values_opt = bellman_ford_algorithm(vertex_count + 1, &augmented_edges, vertex_count);
if h_values_opt.is_none() {
return None; // A negative cycle was detected by the Bellman-Ford Algorithm
}
let mut h_values = h_values_opt.unwrap();
h_values.pop(); // Remove the value for the augmented vertex
// Step 3: Reweight the edges
let mut reweighted_adjacencies: HashMap<usize, Vec<VertexAndWeight>> =
(0..vertex_count).map(|v| (v, Vec::new())).collect();
for edge in &original_edges {
// Ensure the 'values' are valid before reweighting
if h_values[edge.u] == INF || h_values[edge.v] == INF {
// This can happen if the original graph was not strongly connected to the augmented vertex.
// While not strictly an error for Johnson's Algorithm, because paths might still exist between
// reachable nodes, it means the reweighting might involve INF.
// Computation can proceed since Dijkstra's Algorithm can handle INF.
println!("Warning: invalid hValues detected by the Bellman-Ford Algorithm.");
}
let reweight = edge.weight + h_values[edge.u] - h_values[edge.v];
reweighted_adjacencies.get_mut(&edge.u).unwrap().push(VertexAndWeight { v: edge.v, weight: reweight });
}
// Step 4: Invoke Dijkstra's Algorithm starting from each vertex on the reweighted graph
let all_pairs_shortest_paths: Vec<Vec<f64>> = (0..vertex_count)
.map(|u| dijkstra_algorithm(vertex_count, &reweighted_adjacencies, u, &h_values))
.collect();
// Step 5: Return the result matrix
Some(all_pairs_shortest_paths)
}
fn bellman_ford_algorithm(
augmented_vertex_count: usize,
edges: &Vec<Edge>,
source_vertex: usize,
) -> Option<Vec<f64>> {
let mut distances = vec![INF; augmented_vertex_count];
distances[source_vertex] = 0.0;
// Relax the edges (augmented_vertex_count - 1) times
let mut updated = true;
for _ in 0..(augmented_vertex_count - 1) {
if !updated {
break;
}
updated = false;
for edge in edges {
if distances[edge.u] != INF && distances[edge.u] + edge.weight < distances[edge.v] {
distances[edge.v] = distances[edge.u] + edge.weight;
updated = true;
}
}
}
// Check for negative cycles in the graph
for edge in edges {
if distances[edge.u] != INF && distances[edge.u] + edge.weight < distances[edge.v] {
return None; // Indicates to the calling method that a negative cycle has been detected
}
}
Some(distances)
}
fn dijkstra_algorithm(
vertex_count: usize,
reweighted_adjacencies: &HashMap<usize, Vec<VertexAndWeight>>,
source_vertex: usize,
values: &Vec<f64>,
) -> Vec<f64> {
let mut distances = vec![INF; vertex_count];
distances[source_vertex] = 0.0;
let mut priority_queue = BinaryHeap::new();
priority_queue.push(WeightAndVertex {
weight: OrderedFloat(0.0),
vertex: source_vertex,
});
let mut final_distances = vec![INF; vertex_count];
while let Some(weight_and_vertex) = priority_queue.pop() {
let vertex = weight_and_vertex.vertex;
if weight_and_vertex.weight.0 > distances[vertex] {
continue;
}
// Store the final shortest path distance, translated back to the distance in the original graph
// which prevents processing vertices disconnected from the source vertex
if final_distances[vertex] == INF {
if distances[vertex] == INF {
// This should not happen, but is included as a safety check
final_distances[vertex] = INF;
} else {
// Translate distance back to its original weight: d(u,v) = d'(u,v) - h[u] + h[v]
final_distances[vertex] = distances[vertex] - values[source_vertex] + values[vertex];
}
}
// Relax the edges outgoing from vertex
if let Some(adjacencies) = reweighted_adjacencies.get(&vertex) {
for pair in adjacencies {
if distances[vertex] != INF && distances[vertex] + pair.weight < distances[pair.v] {
distances[pair.v] = distances[vertex] + pair.weight;
priority_queue.push(WeightAndVertex {
weight: OrderedFloat(distances[pair.v]),
vertex: pair.v,
});
}
}
}
}
// Translate distance back to its original weight for any remaining reachable vertices
// This handles cases where a vertex was reachable, but was not the minimum vertex
// removed from the priority queue when its final distance was determined.
for i in 0..vertex_count {
if final_distances[i] == INF && distances[i] != INF {
final_distances[i] = distances[i] - values[source_vertex] + values[i];
}
}
final_distances
}
fn main() {
// The element (i, j) is the weight of the edge from vertex i to vertex j.
// INF, for infinity, means that there is no edge from vertex i to vertex j.
let graph = vec![
vec![0.0, -5.0, 2.0, 3.0],
vec![INF, 0.0, 4.0, INF],
vec![INF, INF, 0.0, 1.0],
vec![INF, INF, INF, 0.0],
];
match johnsons_algorithm(&graph) {
Some(result) => {
println!("All pairs shortest paths:");
println!("The element (i, j) is the shortest path between vertex i and vertex j.");
for row in result {
print!("[");
for number in row {
if number == INF {
print!("INF ");
} else {
print!("{} ", number);
}
}
println!("]");
}
}
None => {
println!("A negative cycle was detected in the graph.");
}
}
}
- Output:
All pairs shortest paths: The element (i, j) is the shortest path between vertex i and vertex j. [0 -5 -1 0 ] [INF 0 4 5 ] [INF INF 0 1 ] [INF INF INF 0 ]
Wren
var INF = Num.infinity
/* Runs Bellman-Ford algorithm from a source vertex.
Args:
numVertices: The total number of vertices (including the augmented source).
edges: A list of tuples (u, v, weight) representing directed edges.
source: The index of the source vertex.
Returns:
A list of shortest distances 'h' from the source to all other vertices,
or null if a negative cycle is detected.
*/
var bellmanFord = Fn.new { |numVertices, edges, source|
var dist = List.filled(numVertices, INF)
dist[source] = 0
// Relax edges V - 1 times.
for (i in 0...numVertices - 1) {
var updated = false
for (e in edges) {
var u = e[0]
var v = e[1]
var w = e[2]
if (dist[u] != INF && dist[u] + w < dist[v]) {
dist[v] = dist[u] + w
updated = true
}
}
// If no update in a full pass, we can stop early.
if (!updated) break
}
// Check for negative cycles.
for (e in edges) {
var u = e[0]
var v = e[1]
var w = e[2]
if (dist[u] != INF && dist[u] + w < dist[v]) {
System.print("Graph contains a negative weight cycle")
return null // indicate negative cycle
}
}
return dist
}
/* Runs Dijkstra's algorithm on a potentially re-weighted graph.
Args:
numVertices: The number of vertices in the original graph.
adj: Adjacency list of the re-weighted graph.
source: The source vertex index for this run.
hValues: The potential values calculated by Bellman-Ford.
Returns:
A list of shortest path distances from the source in the original graph.
*/
var dijkstra = Fn.new { |numVertices, adj, source, hValues|
var dist = List.filled(numVertices, INF)
dist[source] = 0
// Priority queue stores (distance, vertex).
var pq = [[0, source]]
var finalDist = List.filled(numVertices, INF) // to store results
while (!pq.isEmpty) {
var du = pq.removeAt(0)
var d = du[0]
var u = du[1]
// If we found a shorter path already, skip.
if (d > dist[u]) continue
// Store the final shortest path distance (translated back).
// This check prevents processing nodes disconnected from source.
if (finalDist[u] == INF) {
if (dist[u] == INF) { // Should not happen if popped from pq, but safety check
finalDist[u] = INF
} else {
// Translate distance back to original weight: d(u,v) = d'(u,v) - h[u] + h[v]
// Here, d'(source, u) is dist[u]
// So, original distance = dist[u] - h[source] + h[u]
finalDist[u] = dist[u] - hValues[source] + hValues[u]
}
}
// Relax edges outgoing from u.
if (adj.containsKey(u)) {
for (vr in adj[u]) {
var v = vr[0]
var rw = vr[1]
if (dist[u] != INF && dist[u] + rw < dist[v]) {
dist[v] = dist[u] + rw
pq.add([dist[v], v])
pq.sort { |a, b| a[0] < b[0] }
}
}
}
}
// After Dijkstra finishes, translate any remaining reachable vertices.
// This handles cases where a node might be reachable but wasn't the
// minimum popped from PQ when its final distance was determined.
for (i in 0...numVertices) {
if (finalDist[i] == INF && dist[i] != INF) {
finalDist[i] = dist[i] - hValues[source] + hValues[i]
}
}
return finalDist
}
/* Implements Johnson's algorithm for all-pairs shortest paths.
Args:
graph_matrix: An adjacency matrix representation of the graph.
graphMatrix[i][j] is the weight of the edge from i to j.
Use 0 for non-existent edges between different nodes (or INF).
graphMatrix[i][i] should be 0.
Returns:
A matrix containing the shortest path distances between all pairs,
or null if a negative cycle is detected. Returns INF if no path exists.
*/
var johnsonsAlgorithm = Fn.new { |graphMatrix|
var V = graphMatrix.count
var originalEdges = []
// --- Step 0: Handle Input and Build Edge List for Original Graph ---
// Be careful about 0 vs non-existent edge. Assume 0 means no edge if i != j.
for (i in 0...V) {
for (j in 0...V) {
var weight = graphMatrix[i][j]
// Only add edges that exist. Assuming 0 means no edge unless i==j.
// If 0 could be a valid edge weight, use INF for non-edges in input.
if (i == j) {
if (weight != 0) {
System.print("Warning: graphMatrix[%(i)][%(i)] is %(weight), expected 0. Setting to 0.")
}
} else if (weight != 0) { // assuming 0 means non-edge here
originalEdges.add([i, j, weight])
// If 0 IS a valid weight, the condition should be:
// else if (weight != INF) { // Use INF in the input matrix for non-edges
// originalEdges.add([i, j, weight])
}
}
}
// --- Step 1: Form the augmented graph G' ---
// Add a new vertex 's' (index V) with 0-weight edges to all original vertices.
var augmentedEdges = List.filled(originalEdges.count, null)
for (i in 0...originalEdges.count) augmentedEdges[i] = originalEdges[i].toList
for (i in 0...V) {
augmentedEdges.add([V, i, 0]) // new source V connects to all others
}
var numVerticesAugmented = V + 1
// --- Step 2: Run Bellman-Ford from the new source 's' ---
var hValues = bellmanFord.call(numVerticesAugmented, augmentedEdges, V)
if (!hValues) {
// Negative cycle detected by Bellman-Ford
return null
}
// Remove the h value for the augmented source, we only need it for original vertices.
hValues = hValues[0...V] // Keep h[0] to h[V-1]
// --- Step 3: Reweight the edges ---
var reweightedAdj = {}
for (i in 0...V) reweightedAdj[i] = []
for (e in originalEdges) {
var u = e[0]
var v = e[1]
var w = e[2]
// Ensure h values are valid before reweighting.
if (hValues[u] == INF || hValues[v] == INF) {
// This can happen if the original graph wasn't strongly connected
// from the augmented source 's'. While not strictly an error for
// Johnson's (paths might still exist between reachable nodes),
// it means the reweighting might involve INF.
// Let's compute the reweighted value anyway; Dijkstra handles INF.
System.print("Warning: invalid h values detected.")
}
var rw = w + hValues[u] - hValues[v]
// Theoretically, rw should be >= 0 if no negative cycle.
// Add small tolerance for floating point issues if necessary:
// if (rw < -1e-9) {
// System.print("Warning: Potential negative reweighted edge %(u)->%(v): %(rw)")
// }
reweightedAdj[u].add([v, rw])
}
// --- Step 4: Run Dijkstra from each vertex on the reweighted graph ---
var allPairsShortestPaths = (0...V).map { |i| List.filled(V, INF) }.toList
for (u in 0...V) {
// Run Dijkstra on the reweighted graph starting from u
var shortestPathsFromU = dijkstra.call(V, reweightedAdj, u, hValues)
allPairsShortestPaths[u] = shortestPathsFromU
// The dijkstra implementation now directly calculates the original distance.
}
// --- Step 5: Return the result matrix ---
return allPairsShortestPaths
}
// --- Test Case ---
var graph = [[0, -5, 2, 3],
[0, 0, 4, 0], // assuming 0 means no edge from 1->0 and 1->3
[0, 0, 0, 1], // assuming 0 means no edge from 2->0 and 2->1
[0, 0, 0, 0]] // assuming 0 means no edge from 3->0, 3->1, 3->2
var result = johnsonsAlgorithm.call(graph)
if (result) {
System.print("All-pairs shortest paths:")
for (row in result) {
System.print(row.toString.replace("infinity", "'INF'"))
}
} else {
System.print("Negative cycle detected in the graph.")
}
System.print("\nExpected for the test case:")
System.print("[0, -5, -1, 0]")
System.print("['INF', 0, 4, 5]")
System.print("['INF', 'INF', 0, 1]")
System.print("['INF', 'INF', 'INF', 0]")
- Output:
All-pairs shortest paths: [0, -5, -1, 0] ['INF', 0, 4, 5] ['INF', 'INF', 0, 1] ['INF', 'INF', 'INF', 0] Expected for the test case: [0, -5, -1, 0] ['INF', 0, 4, 5] ['INF', 'INF', 0, 1] ['INF', 'INF', 'INF', 0]
Zig
const std = @import("std");
const Allocator = std.mem.Allocator;
const ArrayList = std.ArrayList;
const AutoHashMap = std.AutoHashMap;
const PriorityQueue = std.PriorityQueue;
// f64_max isn't directly available in Zig 0.14.0, use std.math.floatMax instead
const INF = std.math.floatMax(f64);
const Edge = struct {
u: usize,
v: usize,
weight: f64,
};
const VertexAndWeight = struct {
v: usize,
weight: f64,
};
const WeightAndVertex = struct {
weight: f64,
vertex: usize,
pub fn compare(context: void, a: WeightAndVertex, b: WeightAndVertex) std.math.Order {
_ = context;
// For min-heap, we want to return Less when a is greater (reversed order)
return std.math.order(b.weight, a.weight);
}
};
pub fn johnsonsAlgorithm(allocator: Allocator, graph: []const []const f64) !?ArrayList(ArrayList(f64)) {
const vertex_count = graph.len;
var original_edges = ArrayList(Edge).init(allocator);
defer original_edges.deinit();
// Step 0: Build a list of edges for the original graph
for (0..vertex_count) |i| {
for (0..vertex_count) |j| {
const weight = graph[i][j];
if (i == j) {
if (weight != 0.0) {
std.debug.print("Warning: graph[i][i] for i = {d} is {d}, expected to be 0.0, resetting it to 0.0\n", .{ i, weight });
}
} else if (weight != INF) {
try original_edges.append(Edge{ .u = i, .v = j, .weight = weight });
}
}
}
// Step 1: Form the augmented graph
// Add a new vertex with index 'vertex_count' and having 0-weight edges to all the original vertices
var augmented_edges = ArrayList(Edge).init(allocator);
defer augmented_edges.deinit();
try augmented_edges.appendSlice(original_edges.items);
for (0..vertex_count) |i| {
try augmented_edges.append(Edge{ .u = vertex_count, .v = i, .weight = 0.0 });
}
// Step 2: Invoke the Bellman-Ford Algorithm starting from the new vertex
const h_values_opt = try bellmanFordAlgorithm(allocator, vertex_count + 1,
augmented_edges.items, vertex_count);
if (h_values_opt == null) {
return null; // A negative cycle was detected by the Bellman-Ford Algorithm
}
var h_values = h_values_opt.?;
defer h_values.deinit();
// Remove the value for the augmented vertex
_ = h_values.pop();
// Step 3: Reweight the edges
var reweighted_adjacencies = AutoHashMap(usize, ArrayList(VertexAndWeight)).init(allocator);
defer {
var it = reweighted_adjacencies.valueIterator();
while (it.next()) |value| {
value.deinit();
}
reweighted_adjacencies.deinit();
}
for (0..vertex_count) |v| {
try reweighted_adjacencies.put(v, ArrayList(VertexAndWeight).init(allocator));
}
for (original_edges.items) |edge| {
// Ensure the 'values' are valid before reweighting
if (h_values.items[edge.u] == INF or h_values.items[edge.v] == INF) {
std.debug.print("Warning: invalid hValues detected by the Bellman-Ford Algorithm.\n", .{});
}
const reweight = edge.weight + h_values.items[edge.u] - h_values.items[edge.v];
try reweighted_adjacencies.getPtr(edge.u).?.append(VertexAndWeight{ .v = edge.v, .weight = reweight });
}
// Step 4: Invoke Dijkstra's Algorithm starting from each vertex on the reweighted graph
var all_pairs_shortest_paths = ArrayList(ArrayList(f64)).init(allocator);
var error_occurred = false;
for (0..vertex_count) |u| {
if (error_occurred) break;
// We create a new function that returns a result to handle errors
if (try dijkstraAlgorithm(allocator, vertex_count, &reweighted_adjacencies, u, h_values.items)) |distances| {
try all_pairs_shortest_paths.append(distances);
} else {
error_occurred = true;
// Clean up previously allocated lists
for (all_pairs_shortest_paths.items) |*path| {
path.deinit();
}
all_pairs_shortest_paths.deinit();
return null;
}
}
// Step 5: Return the result matrix
return all_pairs_shortest_paths;
}
fn bellmanFordAlgorithm(
allocator: Allocator,
augmented_vertex_count: usize,
edges: []const Edge,
source_vertex: usize
) !?ArrayList(f64) {
var distances = ArrayList(f64).init(allocator);
try distances.resize(augmented_vertex_count);
for (distances.items, 0..) |*dist, i| {
dist.* = if (i == source_vertex) 0.0 else INF;
}
// Relax the edges (augmented_vertex_count - 1) times
var updated = true;
for (0..augmented_vertex_count - 1) |_| {
if (!updated) break;
updated = false;
for (edges) |edge| {
if (distances.items[edge.u] != INF and
distances.items[edge.u] + edge.weight < distances.items[edge.v]) {
distances.items[edge.v] = distances.items[edge.u] + edge.weight;
updated = true;
}
}
}
// Check for negative cycles in the graph
for (edges) |edge| {
if (distances.items[edge.u] != INF and
distances.items[edge.u] + edge.weight < distances.items[edge.v]) {
distances.deinit();
return null; // Indicates a negative cycle has been detected
}
}
return distances;
}
fn dijkstraAlgorithm(
allocator: Allocator,
vertex_count: usize,
reweighted_adjacencies: *const AutoHashMap(usize, ArrayList(VertexAndWeight)),
source_vertex: usize,
values: []const f64,
) !?ArrayList(f64) {
var distances = ArrayList(f64).init(allocator);
try distances.resize(vertex_count);
for (distances.items, 0..) |*dist, i| {
dist.* = if (i == source_vertex) 0.0 else INF;
}
var priority_queue = PriorityQueue(WeightAndVertex, void, WeightAndVertex.compare).init(allocator, {});
defer priority_queue.deinit();
try priority_queue.add(WeightAndVertex{ .weight = 0.0, .vertex = source_vertex });
var final_distances = ArrayList(f64).init(allocator);
try final_distances.resize(vertex_count);
for (final_distances.items) |*dist| {
dist.* = INF;
}
while (priority_queue.removeOrNull()) |weight_and_vertex| {
const vertex = weight_and_vertex.vertex;
if (weight_and_vertex.weight > distances.items[vertex]) {
continue;
}
// Store the final shortest path distance, translated back to the distance in the original graph
if (final_distances.items[vertex] == INF) {
if (distances.items[vertex] == INF) {
// This should not happen, but is included as a safety check
final_distances.items[vertex] = INF;
} else {
// Translate distance back to its original weight: d(u,v) = d'(u,v) - h[u] + h[v]
final_distances.items[vertex] = distances.items[vertex] - values[source_vertex] + values[vertex];
}
}
// Relax the edges outgoing from vertex
if (reweighted_adjacencies.get(vertex)) |adjacencies| {
for (adjacencies.items) |pair| {
if (distances.items[vertex] != INF and
distances.items[vertex] + pair.weight < distances.items[pair.v]) {
distances.items[pair.v] = distances.items[vertex] + pair.weight;
try priority_queue.add(WeightAndVertex{ .weight = distances.items[pair.v], .vertex = pair.v });
}
}
}
}
// Translate distance back to its original weight for any remaining reachable vertices
for (0..vertex_count) |i| {
if (final_distances.items[i] == INF and distances.items[i] != INF) {
final_distances.items[i] = distances.items[i] - values[source_vertex] + values[i];
}
}
distances.deinit();
return final_distances;
}
pub fn main() !void {
var gpa = std.heap.GeneralPurposeAllocator(.{}){};
defer _ = gpa.deinit();
const allocator = gpa.allocator();
// The element (i, j) is the weight of the edge from vertex i to vertex j.
// INF, for infinity, means that there is no edge from vertex i to vertex j.
const graph = [_][]const f64{
&[_]f64{ 0.0, -5.0, 2.0, 3.0 },
&[_]f64{ INF, 0.0, 4.0, INF },
&[_]f64{ INF, INF, 0.0, 1.0 },
&[_]f64{ INF, INF, INF, 0.0 },
};
if (try johnsonsAlgorithm(allocator, &graph)) |result| {
defer {
for (result.items) |*row| {
row.deinit();
}
result.deinit();
}
std.debug.print("All pairs shortest paths:\n", .{});
std.debug.print("The element (i, j) is the shortest path between vertex i and vertex j.\n", .{});
for (result.items) |row| {
std.debug.print("[", .{});
for (row.items) |number| {
if (number == INF) {
std.debug.print("INF ", .{});
} else {
std.debug.print("{d} ", .{number});
}
}
std.debug.print("]\n", .{});
}
} else {
std.debug.print("A negative cycle was detected in the graph.\n", .{});
}
}
- Output:
All pairs shortest paths: The element (i, j) is the shortest path between vertex i and vertex j. [0 -5 2 3 ] [INF 0 4 5 ] [INF INF 0 1 ] [INF INF INF 0 ]