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.
You are encouraged to solve this task according to the task description, using any language you may know.
- Johnson's Algorithm
- 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
using System;
using System.Collections.Generic;
using System.Linq;
public class JohnsonsAlgorithm
{
private const double INF = double.MaxValue;
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 = new List<List<double>> {
new List<double> { 0.0, -5.0, 2.0, 3.0 },
new List<double> { INF, 0.0, 4.0, INF },
new List<double> { INF, INF, 0.0, 1.0 },
new List<double> { INF, INF, INF, 0.0 }
};
var result = JohnsonsAlgorithmRunner(graph);
if (result != null)
{
Console.WriteLine("All pairs shortest paths:");
Console.WriteLine("The element (i, j) is the shortest path between vertex i and vertex j.");
foreach (var row in result)
{
Console.Write("[");
foreach (var number in row)
{
Console.Write((number == INF) ? "INF " : number + " ");
}
Console.WriteLine("]");
}
}
else
{
Console.WriteLine("A negative cycle was detected in the graph.");
}
}
private static List<List<double>> JohnsonsAlgorithmRunner(List<List<double>> graph)
{
int vertexCount = graph.Count;
List<Edge> originalEdges = new List<Edge>();
// Step 0: Build a list of edges for the original graph
for (int i = 0; i < vertexCount; i++)
{
for (int j = 0; j < vertexCount; j++)
{
double weight = graph[i][j];
if (i == j)
{
if (weight != 0.0)
{
Console.WriteLine($"Warning: graph[i][i] for i = {i} is {weight}, expected to be 0.0, resetting it to 0.0");
}
}
else if (weight != INF)
{
originalEdges.Add(new Edge(i, j, weight));
}
}
}
// Step 1: Form the augmented graph
List<Edge> augmentedEdges = new List<Edge>(originalEdges);
for (int i = 0; i < vertexCount; i++)
{
augmentedEdges.Add(new Edge(vertexCount, i, 0.0));
}
// Step 2: Invoke the Bellman-Ford Algorithm starting from the new vertex
var hValues = BellmanFordAlgorithm(vertexCount + 1, augmentedEdges, vertexCount);
if (hValues == null)
{
return null; // A negative cycle was detected by the Bellman-Ford Algorithm
}
List<double> values = hValues;
values.RemoveAt(values.Count - 1); // Remove the value for the augmented vertex
// Step 3: Reweight the edges
Dictionary<int, List<VertexAndWeight>> reweightedAdjacencies = Enumerable.Range(0, vertexCount).ToDictionary(v => v, v => new List<VertexAndWeight>());
foreach (var edge in originalEdges)
{
if (values[edge.U] == INF || values[edge.V] == INF)
{
Console.WriteLine("Warning: invalid hValues detected by the Bellman-Ford Algorithm.");
}
double reweight = edge.Weight + values[edge.U] - values[edge.V];
reweightedAdjacencies[edge.U].Add(new VertexAndWeight(edge.V, reweight));
}
// Step 4: Invoke Dijkstra's Algorithm starting from each vertex on the reweighted graph
List<List<double>> allPairsShortestPaths = Enumerable.Range(0, vertexCount).Select(u => DijkstraAlgorithm(vertexCount, reweightedAdjacencies, u, values)).ToList();
// Step 5: Return the result matrix
return allPairsShortestPaths;
}
private static List<double> BellmanFordAlgorithm(int augmentedVertexCount, List<Edge> edges, int sourceVertex)
{
List<double> distances = Enumerable.Repeat(INF, augmentedVertexCount).ToList();
distances[sourceVertex] = 0.0;
// Relax the edges (augmentedVertexCount - 1) times
bool updated = true;
for (int i = 0; i < augmentedVertexCount - 1 && updated; i++)
{
updated = false;
foreach (var 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
foreach (var edge in edges)
{
if (distances[edge.U] != INF && distances[edge.U] + edge.Weight < distances[edge.V])
{
return null; // Indicates to the calling method that a negative cycle has been detected
}
}
return distances;
}
private static List<double> DijkstraAlgorithm(int vertexCount, Dictionary<int, List<VertexAndWeight>> reweightedAdjacencies, int sourceVertex, List<double> values)
{
List<double> distances = Enumerable.Repeat(INF, vertexCount).ToList();
distances[sourceVertex] = 0.0;
var priorityQueue = new PriorityQueue<VertexAndWeight>();
priorityQueue.Enqueue(new VertexAndWeight(sourceVertex, 0.0));
List<double> finalDistances = Enumerable.Repeat(INF, vertexCount).ToList();
while (priorityQueue.Count > 0)
{
VertexAndWeight vertexAndWeight = priorityQueue.Dequeue();
int vertex = vertexAndWeight.Vertex;
if (vertexAndWeight.Weight > distances[vertex])
{
continue;
}
if (finalDistances[vertex] == INF)
{
if (distances[vertex] == INF)
{
finalDistances[vertex] = INF;
}
else
{
finalDistances[vertex] = distances[vertex] - values[sourceVertex] + values[vertex];
}
}
if (reweightedAdjacencies.ContainsKey(vertex))
{
foreach (var pair in reweightedAdjacencies[vertex])
{
if (distances[vertex] != INF && distances[vertex] + pair.Weight < distances[pair.Vertex])
{
distances[pair.Vertex] = distances[vertex] + pair.Weight;
priorityQueue.Enqueue(new VertexAndWeight(pair.Vertex, distances[pair.Vertex]));
}
}
}
}
for (int i = 0; i < vertexCount; i++)
{
if (finalDistances[i] == INF && distances[i] != INF)
{
finalDistances[i] = distances[i] - values[sourceVertex] + values[i];
}
}
return finalDistances;
}
private class Edge
{
public int U { get; }
public int V { get; }
public double Weight { get; }
public Edge(int u, int v, double weight)
{
U = u;
V = v;
Weight = weight;
}
}
private class VertexAndWeight : IComparable<VertexAndWeight>
{
public int Vertex { get; }
public double Weight { get; }
public VertexAndWeight(int vertex, double weight)
{
Vertex = vertex;
Weight = weight;
}
public int CompareTo(VertexAndWeight other)
{
return Weight.CompareTo(other.Weight);
}
}
private class PriorityQueue<T> where T : IComparable<T>
{
private List<T> data;
public PriorityQueue()
{
this.data = new List<T>();
}
public void Enqueue(T item)
{
data.Add(item);
int childIndex = data.Count - 1;
while (childIndex > 0)
{
int parentIndex = (childIndex - 1) / 2;
if (data[childIndex].CompareTo(data[parentIndex]) >= 0)
break;
T tmp = data[childIndex];
data[childIndex] = data[parentIndex];
data[parentIndex] = tmp;
childIndex = parentIndex;
}
}
public T Dequeue()
{
int lastIndex = data.Count - 1;
T frontItem = data[0];
data[0] = data[lastIndex];
data.RemoveAt(lastIndex);
lastIndex--;
int parentIndex = 0;
while (true)
{
int childIndex = parentIndex * 2 + 1;
if (childIndex > lastIndex)
break;
int rightChild = childIndex + 1;
if (rightChild <= lastIndex && data[rightChild].CompareTo(data[childIndex]) < 0)
childIndex = rightChild;
if (data[parentIndex].CompareTo(data[childIndex]) <= 0)
break;
T tmp = data[parentIndex];
data[parentIndex] = data[childIndex];
data[childIndex] = tmp;
parentIndex = childIndex;
}
return frontItem;
}
public int Count => data.Count;
}
}
- 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 ]
#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 ]
>>SOURCE FORMAT IS FREE
IDENTIFICATION DIVISION.
PROGRAM-ID. JohnsonsAlgo.
ENVIRONMENT DIVISION.
DATA DIVISION.
WORKING-STORAGE SECTION.
01 CONSTANTS.
05 INF PIC S9(9)V9(2) COMP-3 VALUE 9999999.00.
01 GRAPH-DATA.
05 VCOUNT PIC 9(4) COMP VALUE 4.
05 G-MAT OCCURS 10 TIMES.
10 G-ROW OCCURS 10 TIMES.
15 MW PIC S9(9)V9(2) COMP-3.
01 EDGE-LIST-DATA.
05 ECOUNT PIC 9(4) COMP VALUE 0.
05 EDGES OCCURS 100 TIMES.
10 EU PIC 9(4) COMP.
10 EV PIC 9(4) COMP.
10 EW PIC S9(9)V9(2) COMP-3.
01 AUG-DATA.
05 AUG-V PIC 9(4) COMP.
05 AUG-ECOUNT PIC 9(4) COMP.
05 AUG-EDGES OCCURS 110 TIMES.
10 AU PIC 9(4) COMP.
10 AV PIC 9(4) COMP.
10 AW PIC S9(9)V9(2) COMP-3.
01 BF-DATA.
05 H-VALS OCCURS 11 TIMES PIC S9(9)V9(2) COMP-3.
05 BF-UPD PIC X.
88 IS-UPD VALUE 'Y'.
88 NOT-UPD VALUE 'N'.
05 NEG-CYC PIC X VALUE 'N'.
01 RW-ADJ.
05 RW-ECOUNTS OCCURS 10 TIMES PIC 9(4) COMP.
05 RW-EDGES OCCURS 10 TIMES.
10 RW-EDGE OCCURS 10 TIMES.
15 RW-V PIC 9(4) COMP.
15 RW-W PIC S9(9)V9(2) COMP-3.
01 DIJKSTRA-DATA.
05 DDIST OCCURS 10 TIMES PIC S9(9)V9(2) COMP-3.
05 FDIST OCCURS 10 TIMES PIC S9(9)V9(2) COMP-3.
05 D-VIS OCCURS 10 TIMES PIC X.
88 IS-VIS VALUE 'Y'.
88 NOT-VIS VALUE 'N'.
01 ALL-PAIRS-SP.
05 SP-ROW OCCURS 10 TIMES.
10 SP-VAL OCCURS 10 TIMES PIC S9(9)V9(2) COMP-3.
01 TEMP-VARS.
05 TWEIGHT PIC S9(9)V9(2) COMP-3.
05 TVAL PIC S9(9)V9(2) COMP-3.
05 MDIST PIC S9(9)V9(2) COMP-3.
05 MU PIC 9(4) COMP.
05 I PIC 9(4) COMP.
05 J PIC 9(4) COMP.
05 S PIC 9(4) COMP.
05 IDX PIC 9(4) COMP.
05 ITER PIC 9(4) COMP.
01 PRINT-DATA.
05 OUT-STR PIC X(100).
05 OUT-POS PIC 9(3) COMP.
05 NUM-STR PIC ----9.9.
05 T-STR PIC X(20).
PROCEDURE DIVISION.
TEST-MAIN.
PERFORM INIT-G
PERFORM STEP1-AUG
PERFORM BF-ALGO
IF NEG-CYC = 'Y'
DISPLAY "A negative cycle was detected in the graph."
ELSE
PERFORM RW-EDGES-PROC
PERFORM RUN-DIJK
DISPLAY "All pairs shortest paths:"
DISPLAY "The element (i, j) is the shortest path between vertex i and vertex j."
PERFORM PRINT-RES
END-IF
STOP RUN.
INIT-G.
MOVE 4 TO VCOUNT.
PERFORM VARYING I FROM 1 BY 1 UNTIL I > VCOUNT
PERFORM VARYING J FROM 1 BY 1 UNTIL J > VCOUNT
MOVE INF TO MW (I, J)
END-PERFORM
END-PERFORM.
MOVE 0.0 TO MW (1, 1).
MOVE -5.0 TO MW (1, 2).
MOVE 2.0 TO MW (1, 3).
MOVE 3.0 TO MW (1, 4).
MOVE 0.0 TO MW (2, 2).
MOVE 4.0 TO MW (2, 3).
MOVE 0.0 TO MW (3, 3).
MOVE 1.0 TO MW (3, 4).
MOVE 0.0 TO MW (4, 4).
MOVE 0 TO ECOUNT.
PERFORM VARYING I FROM 1 BY 1 UNTIL I > VCOUNT
PERFORM VARYING J FROM 1 BY 1 UNTIL J > VCOUNT
MOVE MW (I, J) TO TWEIGHT
IF I = J
IF TWEIGHT NOT = 0.0
DISPLAY "Warning: graph[i][i] expected 0"
END-IF
ELSE
IF TWEIGHT < 9999990.00
ADD 1 TO ECOUNT
MOVE I TO EU (ECOUNT)
MOVE J TO EV (ECOUNT)
MOVE TWEIGHT TO EW (ECOUNT)
END-IF
END-IF
END-PERFORM
END-PERFORM.
STEP1-AUG.
COMPUTE AUG-V = VCOUNT + 1
MOVE ECOUNT TO AUG-ECOUNT
PERFORM VARYING I FROM 1 BY 1 UNTIL I > ECOUNT
MOVE EU (I) TO AU (I)
MOVE EV (I) TO AV (I)
MOVE EW (I) TO AW (I)
END-PERFORM
PERFORM VARYING I FROM 1 BY 1 UNTIL I > VCOUNT
ADD 1 TO AUG-ECOUNT
MOVE AUG-V TO AU (AUG-ECOUNT)
MOVE I TO AV (AUG-ECOUNT)
MOVE 0.0 TO AW (AUG-ECOUNT)
END-PERFORM.
BF-ALGO.
MOVE 'N' TO NEG-CYC
PERFORM VARYING I FROM 1 BY 1 UNTIL I > AUG-V
MOVE INF TO H-VALS (I)
END-PERFORM
MOVE 0 TO H-VALS (AUG-V)
PERFORM VARYING ITER FROM 1 BY 1 UNTIL ITER >= AUG-V
SET NOT-UPD TO TRUE
PERFORM VARYING J FROM 1 BY 1 UNTIL J > AUG-ECOUNT
IF H-VALS (AU (J)) < 9999990.00
COMPUTE TVAL = H-VALS (AU (J)) + AW (J)
IF TVAL < H-VALS (AV (J))
MOVE TVAL TO H-VALS (AV (J))
SET IS-UPD TO TRUE
END-IF
END-IF
END-PERFORM
IF NOT-UPD
EXIT PERFORM
END-IF
END-PERFORM
PERFORM VARYING J FROM 1 BY 1 UNTIL J > AUG-ECOUNT
IF H-VALS (AU (J)) < 9999990.00
COMPUTE TVAL = H-VALS (AU (J)) + AW (J)
IF TVAL < H-VALS (AV (J))
MOVE 'Y' TO NEG-CYC
END-IF
END-IF
END-PERFORM.
RW-EDGES-PROC.
PERFORM VARYING I FROM 1 BY 1 UNTIL I > VCOUNT
MOVE 0 TO RW-ECOUNTS (I)
END-PERFORM
PERFORM VARYING J FROM 1 BY 1 UNTIL J > ECOUNT
IF H-VALS (EU (J)) > 9999990.00 OR
H-VALS (EV (J)) > 9999990.00
DISPLAY "Warning: invalid hValues detected"
END-IF
ADD 1 TO RW-ECOUNTS (EU (J))
MOVE RW-ECOUNTS (EU (J)) TO IDX
MOVE EV (J) TO RW-V (EU (J), IDX)
COMPUTE RW-W (EU (J), IDX) = EW (J)
+ H-VALS (EU (J))
- H-VALS (EV (J))
END-PERFORM.
RUN-DIJK.
PERFORM VARYING S FROM 1 BY 1 UNTIL S > VCOUNT
PERFORM DIJK-FOR-V
PERFORM VARYING I FROM 1 BY 1 UNTIL I > VCOUNT
MOVE FDIST (I) TO SP-VAL (S, I)
END-PERFORM
END-PERFORM.
DIJK-FOR-V.
PERFORM VARYING I FROM 1 BY 1 UNTIL I > VCOUNT
MOVE INF TO DDIST (I)
MOVE INF TO FDIST (I)
SET NOT-VIS (I) TO TRUE
END-PERFORM
MOVE 0 TO DDIST (S)
PERFORM VCOUNT TIMES
MOVE INF TO MDIST
MOVE 0 TO MU
PERFORM VARYING I FROM 1 BY 1 UNTIL I > VCOUNT
IF NOT IS-VIS (I) AND DDIST (I) < MDIST
MOVE DDIST (I) TO MDIST
MOVE I TO MU
END-IF
END-PERFORM
IF MU = 0
EXIT PERFORM
END-IF
SET IS-VIS (MU) TO TRUE
IF FDIST (MU) > 9999990.00
IF DDIST (MU) > 9999990.00
MOVE INF TO FDIST (MU)
ELSE
COMPUTE FDIST (MU) = DDIST (MU) - H-VALS (S) + H-VALS (MU)
END-IF
END-IF
PERFORM VARYING IDX FROM 1 BY 1 UNTIL IDX > RW-ECOUNTS (MU)
MOVE RW-V (MU, IDX) TO J
IF DDIST (MU) < 9999990.00
COMPUTE TVAL = DDIST (MU) + RW-W (MU, IDX)
IF TVAL < DDIST (J)
MOVE TVAL TO DDIST (J)
END-IF
END-IF
END-PERFORM
END-PERFORM
PERFORM VARYING I FROM 1 BY 1 UNTIL I > VCOUNT
IF FDIST (I) > 9999990.00 AND DDIST (I) < 9999990.00
COMPUTE FDIST (I) = DDIST (I) - H-VALS (S) + H-VALS (I)
END-IF
END-PERFORM.
PRINT-RES.
PERFORM VARYING I FROM 1 BY 1 UNTIL I > VCOUNT
MOVE SPACES TO OUT-STR
MOVE "[" TO OUT-STR
MOVE 2 TO OUT-POS
PERFORM VARYING J FROM 1 BY 1 UNTIL J > VCOUNT
IF SP-VAL (I, J) > 9999990.00
STRING "INF " DELIMITED BY SIZE
INTO OUT-STR WITH POINTER OUT-POS
ELSE
MOVE SP-VAL (I, J) TO NUM-STR
MOVE FUNCTION TRIM(NUM-STR) TO T-STR
STRING FUNCTION TRIM(T-STR) DELIMITED BY SIZE
" " DELIMITED BY SIZE
INTO OUT-STR WITH POINTER OUT-POS
END-IF
END-PERFORM
STRING "]" DELIMITED BY SIZE
INTO OUT-STR WITH POINTER OUT-POS
DISPLAY FUNCTION TRIM(OUT-STR)
END-PERFORM.
- 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 ]
import 'dart:collection';
import 'dart:math' as math;
// Use a very large number to represent infinity since Dart's double.infinity
// might not behave as expected in all comparison contexts.
// A finite value is often preferred for algorithms like these.
const double INF = 1e300;
class Edge {
final int u;
final int v;
final double weight;
Edge(this.u, this.v, this.weight);
}
class VertexAndWeight {
final int vertex;
final double weight;
VertexAndWeight(this.vertex, this.weight);
}
/// Return a list of shortest path distances from the source vertex in the original graph to all other vertices
List<double> dijkstraAlgorithm(
int vertexCount,
Map<int, List<VertexAndWeight>> reweightedAdjacencies,
int sourceVertex,
List<double> values) {
List<double> distances = List.filled(vertexCount, INF);
distances[sourceVertex] = 0.0;
// Using a simple list-based priority queue simulation for clarity.
// A more efficient heap-based implementation would be better for performance.
List<VertexAndWeight> priorityQueue = [VertexAndWeight(sourceVertex, 0.0)];
void addToQueue(VertexAndWeight item) {
priorityQueue.add(item);
priorityQueue.sort((a, b) => a.weight.compareTo(b.weight)); // Min-heap
}
List<double> finalDistances = List.filled(vertexCount, INF);
while (priorityQueue.isNotEmpty) {
VertexAndWeight vertexAndWeight = priorityQueue.removeAt(0); // Remove min
final int vertex = vertexAndWeight.vertex;
if (vertexAndWeight.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
// Check if the key exists and the list is not empty
if (reweightedAdjacencies.containsKey(vertex) && reweightedAdjacencies[vertex].isNotEmpty) {
for (VertexAndWeight pair in reweightedAdjacencies[vertex]) {
if (distances[vertex] != INF &&
distances[vertex] + pair.weight < distances[pair.vertex]) {
distances[pair.vertex] = distances[vertex] + pair.weight;
addToQueue(VertexAndWeight(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 (int i = 0; i < vertexCount; ++i) {
if (finalDistances[i] == INF && distances[i] != INF) {
finalDistances[i] = distances[i] - values[sourceVertex] + values[i];
}
}
return finalDistances;
}
/// Return a list of shortest distances from the source vertex to all other vertices,
/// or an empty list if a negative cycle is detected
List<double> bellmanFordAlgorithm(
int augmentedVertexCount, List<Edge> edges, int sourceVertex) {
List<double> distances = List.filled(augmentedVertexCount, INF);
distances[sourceVertex] = 0.0;
// Relax the edges (augmentedVertexCount - 1) times
bool updated = true;
for (int i = 0; i < augmentedVertexCount - 1 && updated; ++i) {
updated = false;
for (int j = 0; j < edges.length; ++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 (Edge edge in edges) {
if (distances[edge.u] != INF &&
distances[edge.u] + edge.weight < distances[edge.v]) {
// Indicates a negative cycle was detected, return an empty list
return List(); // Return an empty list instead of List<double>.empty()
}
}
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
List<List<double>> johnsonsAlgorithm(List<List<double>> graph) {
final int vertexCount = graph.length;
List<Edge> originalEdges = [];
// Step 0: Build a list of edges for the original graph
for (int i = 0; i < vertexCount; ++i) {
for (int j = 0; j < vertexCount; ++j) {
final double weight = graph[i][j];
if (i == j) {
if (weight != 0.0) {
print('Warning: graph[$i][$i] is $weight, expected to be 0.0, '
'resetting it to 0.0');
// Note: Original graph is not modified here, only the edge list is built.
}
} else if (weight != INF) {
originalEdges.add(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 = List.from(originalEdges);
for (int i = 0; i < vertexCount; ++i) {
augmentedEdges.add(Edge(vertexCount, i, 0.0));
}
// Step 2: Invoke the Bellman-Ford Algorithm starting from the new vertex
List<double> hValues =
bellmanFordAlgorithm(vertexCount + 1, augmentedEdges, vertexCount);
// Check if Bellman-Ford returned an empty list (indicating a negative cycle)
if (hValues.isEmpty) {
// A negative cycle was detected by the Bellman-Ford Algorithm, return an empty list
return List(); // Return an empty list instead of List<List<double>>.empty()
}
// The hValues list is valid, proceed.
// Create a new growable list from hValues so we can modify it
List<double> values = List.from(hValues);
values.removeLast(); // Remove the value for the augmented vertex
// Step 3: Reweight the edges
Map<int, List<VertexAndWeight>> reweightedAdjacencies = {};
for (Edge edge in 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.
print('Warning: invalid hValues detected by the Bellman-Ford Algorithm.');
}
final double reweight = edge.weight + values[edge.u] - values[edge.v];
if (!reweightedAdjacencies.containsKey(edge.u)) {
reweightedAdjacencies[edge.u] = [];
}
reweightedAdjacencies[edge.u].add(VertexAndWeight(edge.v, reweight));
}
// Step 4: Invoke Dijkstra's Algorithm starting from each vertex on the reweighted graph
List<List<double>> allPairsShortestPaths = [];
for (int u = 0; u < vertexCount; ++u) {
allPairsShortestPaths
.add(dijkstraAlgorithm(vertexCount, reweightedAdjacencies, u, values));
}
// Step 5: Return the result matrix
return allPairsShortestPaths;
}
void 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.
final List<List<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]
];
final List<List<double>> result = johnsonsAlgorithm(graph);
// Check if the result is an empty list (indicating a negative cycle)
if (result.isEmpty) {
print('A negative cycle was detected in the graph.');
} else {
print('All pairs shortest paths:');
print(
'The element (i, j) is the shortest path between vertex i and vertex j.');
for (List<double> row in result) {
StringBuffer sb = StringBuffer('[');
for (int j = 0; j < row.length; j++) {
double number = row[j];
if (number >= INF / 2) { // Heuristic check for infinity
sb.write('INF');
} else {
sb.write(number.toStringAsFixed(1)); // Format number for display
}
if (j < row.length - 1) {
sb.write(', ');
}
}
sb.write(']');
print(sb.toString());
}
}
}
- 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]
program johnsons_algorithm
implicit none
! Constants
integer, parameter :: dp = selected_real_kind(15, 307)
real(dp), parameter :: INF = huge(0.0_dp)
integer, parameter :: MAX_VERTICES = 100
integer, parameter :: MAX_EDGES = 1000
! Type definitions
type :: edge_type
integer :: u, v
real(dp) :: weight
end type edge_type
type :: vertex_weight_type
integer :: vertex
real(dp) :: weight
end type vertex_weight_type
! Variables
integer :: vertex_count, edge_count
real(dp) :: graph(4, 4)
real(dp), allocatable :: result(:, :)
logical :: success
integer :: i, j
! Initialize the test graph
vertex_count = 4
! Initialize all elements to INF
graph = INF
! Set diagonal to 0
do i = 1, vertex_count
graph(i, i) = 0.0_dp
end do
! Set the actual edges (converting from 0-based to 1-based indexing)
graph(1, 2) = -5.0_dp
graph(1, 3) = 2.0_dp
graph(1, 4) = 3.0_dp
graph(2, 3) = 4.0_dp
graph(3, 4) = 1.0_dp
! Allocate result matrix
allocate(result(vertex_count, vertex_count))
! Run Johnson's algorithm
call run_johnsons_algorithm(graph, vertex_count, result, success)
! Print results
if (success) then
write(*, '(A)') 'All pairs shortest paths:'
write(*, '(A)') 'The element (i, j) is the shortest path between vertex i and vertex j.'
do i = 1, vertex_count
write(*, '(A)', advance='no') '['
do j = 1, vertex_count
if (result(i, j) >= INF * 0.9_dp) then
write(*, '(A)', advance='no') 'INF '
else
write(*, '(F8.1)', advance='no') result(i, j)
write(*, '(A)', advance='no') ' '
end if
end do
write(*, '(A)') ']'
end do
else
write(*, '(A)') 'A negative cycle was detected in the graph.'
end if
deallocate(result)
contains
subroutine run_johnsons_algorithm(graph_matrix, n_vertices, shortest_paths, success)
implicit none
real(dp), intent(in) :: graph_matrix(:, :)
integer, intent(in) :: n_vertices
real(dp), intent(out) :: shortest_paths(:, :)
logical, intent(out) :: success
type(edge_type) :: original_edges(MAX_EDGES)
type(edge_type) :: augmented_edges(MAX_EDGES)
real(dp) :: h_values(n_vertices + 1)
real(dp) :: values(n_vertices)
integer :: n_original_edges, n_augmented_edges
integer :: adjacency_list(n_vertices, n_vertices)
real(dp) :: adjacency_weights(n_vertices, n_vertices)
integer :: adjacency_counts(n_vertices)
integer :: i, j, u
real(dp) :: reweight
logical :: bf_success
success = .true.
! Step 0: Build list of edges for the original graph
n_original_edges = 0
do i = 1, n_vertices
do j = 1, n_vertices
if (i == j) then
if (abs(graph_matrix(i, j)) > 1e-10) then
write(*, '(A, I0, A, F8.3, A)') 'Warning: graph(', i, ',', i, ') is ', &
graph_matrix(i, j), ', expected to be 0.0, resetting it to 0.0'
end if
else if (graph_matrix(i, j) < INF * 0.9_dp) then
n_original_edges = n_original_edges + 1
original_edges(n_original_edges)%u = i
original_edges(n_original_edges)%v = j
original_edges(n_original_edges)%weight = graph_matrix(i, j)
end if
end do
end do
! Step 1: Form the augmented graph
n_augmented_edges = n_original_edges
do i = 1, n_original_edges
augmented_edges(i) = original_edges(i)
end do
! Add edges from new vertex (n_vertices + 1) to all original vertices
do i = 1, n_vertices
n_augmented_edges = n_augmented_edges + 1
augmented_edges(n_augmented_edges)%u = n_vertices + 1
augmented_edges(n_augmented_edges)%v = i
augmented_edges(n_augmented_edges)%weight = 0.0_dp
end do
! Step 2: Run Bellman-Ford algorithm
call bellman_ford_algorithm(n_vertices + 1, augmented_edges, n_augmented_edges, &
n_vertices + 1, h_values, bf_success)
if (.not. bf_success) then
success = .false.
return
end if
! Extract h values for original vertices
do i = 1, n_vertices
values(i) = h_values(i)
end do
! Step 3: Reweight the edges and build adjacency representation
adjacency_counts = 0
do i = 1, n_original_edges
u = original_edges(i)%u
reweight = original_edges(i)%weight + values(u) - values(original_edges(i)%v)
adjacency_counts(u) = adjacency_counts(u) + 1
adjacency_list(u, adjacency_counts(u)) = original_edges(i)%v
adjacency_weights(u, adjacency_counts(u)) = reweight
end do
! Step 4: Run Dijkstra's algorithm from each vertex
do u = 1, n_vertices
call dijkstra_algorithm(n_vertices, adjacency_list, adjacency_weights, &
adjacency_counts, u, values, shortest_paths(u, :))
end do
end subroutine run_johnsons_algorithm
subroutine dijkstra_algorithm(n_vertices, adj_list, adj_weights, adj_counts, &
source_vertex, h_vals, distances)
implicit none
integer, intent(in) :: n_vertices
integer, intent(in) :: adj_list(:, :)
real(dp), intent(in) :: adj_weights(:, :)
integer, intent(in) :: adj_counts(:)
integer, intent(in) :: source_vertex
real(dp), intent(in) :: h_vals(:)
real(dp), intent(out) :: distances(:)
real(dp) :: dist(n_vertices)
real(dp) :: final_dist(n_vertices)
logical :: visited(n_vertices)
integer :: i, j, u, v, min_vertex
real(dp) :: min_dist, alt_dist
! Initialize distances
dist = INF
final_dist = INF
visited = .false.
dist(source_vertex) = 0.0_dp
do i = 1, n_vertices
! Find minimum distance vertex not yet visited
min_dist = INF
min_vertex = -1
do j = 1, n_vertices
if (.not. visited(j) .and. dist(j) < min_dist) then
min_dist = dist(j)
min_vertex = j
end if
end do
if (min_vertex == -1) exit
u = min_vertex
visited(u) = .true.
! Store final distance (translated back to original graph)
if (dist(u) >= INF * 0.9_dp) then
final_dist(u) = INF
else
final_dist(u) = dist(u) - h_vals(source_vertex) + h_vals(u)
end if
! Relax edges
do j = 1, adj_counts(u)
v = adj_list(u, j)
if (.not. visited(v)) then
alt_dist = dist(u) + adj_weights(u, j)
if (alt_dist < dist(v)) then
dist(v) = alt_dist
end if
end if
end do
end do
! Handle remaining vertices
do i = 1, n_vertices
if (final_dist(i) >= INF * 0.9_dp .and. dist(i) < INF * 0.9_dp) then
final_dist(i) = dist(i) - h_vals(source_vertex) + h_vals(i)
end if
end do
distances = final_dist
end subroutine dijkstra_algorithm
subroutine bellman_ford_algorithm(n_vertices, edges, n_edges, source_vertex, distances, success)
implicit none
integer, intent(in) :: n_vertices, n_edges, source_vertex
type(edge_type), intent(in) :: edges(:)
real(dp), intent(out) :: distances(:)
logical, intent(out) :: success
integer :: i, j
logical :: updated
real(dp) :: new_dist
success = .true.
! Initialize distances
distances = INF
distances(source_vertex) = 0.0_dp
! Relax edges (n_vertices - 1) times
do i = 1, n_vertices - 1
updated = .false.
do j = 1, n_edges
if (distances(edges(j)%u) < INF * 0.9_dp) then
new_dist = distances(edges(j)%u) + edges(j)%weight
if (new_dist < distances(edges(j)%v)) then
distances(edges(j)%v) = new_dist
updated = .true.
end if
end if
end do
if (.not. updated) exit
end do
! Check for negative cycles
do j = 1, n_edges
if (distances(edges(j)%u) < INF * 0.9_dp) then
new_dist = distances(edges(j)%u) + edges(j)%weight
if (new_dist < distances(edges(j)%v)) then
success = .false.
return
end if
end if
end do
end subroutine bellman_ford_algorithm
end program johnsons_algorithm
- 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 ]
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
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 ]
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 ]
// 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 ]
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
import java.util.*
import kotlin.collections.ArrayList
import kotlin.collections.HashMap
object MainKt {
private val INF = Double.MAX_VALUE
data class Edge(val u: Int, val v: Int, val weight: Double)
data class VertexAndWeight(val vertex: Int, val weight: Double)
@JvmStatic
fun main(args: Array<String>) {
// 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.
val graph = listOf(
listOf(0.0, -5.0, 2.0, 3.0),
listOf(INF, 0.0, 4.0, INF),
listOf(INF, INF, 0.0, 1.0),
listOf(INF, INF, INF, 0.0)
)
val result = johnsonsAlgorithm(graph)
if (result.isPresent) {
println("All pairs shortest paths:")
println("The element (i, j) is the shortest path between vertex i and vertex j.")
result.get().forEach { row ->
print("[")
row.forEach { number ->
print(if (number == INF) "INF " else "$number ")
}
println("]")
}
} else {
println("A negative cycle was detected in the graph.")
}
}
private fun johnsonsAlgorithm(graph: List<List<Double>>): Optional<List<List<Double>>> {
val vertexCount = graph.size
val originalEdges = ArrayList<Edge>()
// Step 0: Build a list of edges for the original graph
for (i in 0 until vertexCount) {
for (j in 0 until vertexCount) {
val weight = graph[i][j]
if (i == j) {
if (weight != 0.0) {
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.add(Edge(i, j, weight))
}
}
}
// Step 1: Form the augmented graph
val augmentedEdges = originalEdges + (0 until vertexCount).map { Edge(vertexCount, it, 0.0) }
// Step 2: Invoke the Bellman-Ford Algorithm starting from the new vertex
val hValues = bellmanFordAlgorithm(vertexCount + 1, augmentedEdges, vertexCount)
if (hValues.isEmpty) {
return Optional.empty() // A negative cycle was detected by the Bellman-Ford Algorithm
}
val values = hValues.get().toMutableList()
values.removeAt(values.size - 1) // Remove the value for the augmented vertex
// Step 3: Reweight the edges
val reweightedAdjacencies = HashMap<Int, MutableList<VertexAndWeight>>()
for (v in 0 until vertexCount) {
reweightedAdjacencies[v] = ArrayList()
}
originalEdges.forEach { edge ->
if (values[edge.u] == INF || values[edge.v] == INF) {
println("Warning: invalid hValues detected by the Bellman-Ford Algorithm.")
}
val reweight = edge.weight + values[edge.u] - values[edge.v]
reweightedAdjacencies[edge.u]?.add(VertexAndWeight(edge.v, reweight))
}
// Step 4: Invoke Dijkstra's Algorithm starting from each vertex on the reweighted graph
val allPairsShortestPaths = (0 until vertexCount).map { u ->
dijkstraAlgorithm(vertexCount, reweightedAdjacencies, u, values)
}
// Step 5: Return the result matrix
return Optional.of(allPairsShortestPaths)
}
private fun bellmanFordAlgorithm(
augmentedVertexCount: Int,
edges: List<Edge>,
sourceVertex: Int
): Optional<List<Double>> {
val distances = MutableList(augmentedVertexCount) { INF }
distances[sourceVertex] = 0.0
// Relax the edges (augmentedVertexCount - 1) times
var updated: Boolean
for (i in 0 until augmentedVertexCount - 1) {
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
}
}
if (!updated) break
}
// 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 Optional.empty() // Indicates to the calling method that a negative cycle has been detected
}
}
return Optional.of(distances)
}
private fun dijkstraAlgorithm(
vertexCount: Int,
reweightedAdjacencies: Map<Int, List<VertexAndWeight>>,
sourceVertex: Int,
values: List<Double>
): List<Double> {
val distances = MutableList(vertexCount) { INF }
distances[sourceVertex] = 0.0
val priorityQueue = PriorityQueue<VertexAndWeight>(compareBy { it.weight })
priorityQueue.add(VertexAndWeight(sourceVertex, 0.0))
val finalDistances = MutableList(vertexCount) { INF }
while (priorityQueue.isNotEmpty()) {
val vertexAndWeight = priorityQueue.remove()
val vertex = vertexAndWeight.vertex
if (vertexAndWeight.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) {
finalDistances[vertex] = INF
} else {
finalDistances[vertex] = distances[vertex] - values[sourceVertex] + values[vertex]
}
}
// Relax the edges outgoing from vertex
reweightedAdjacencies[vertex]?.forEach { pair ->
if (distances[vertex] != INF && distances[vertex] + pair.weight < distances[pair.vertex]) {
distances[pair.vertex] = distances[vertex] + pair.weight
priorityQueue.add(VertexAndWeight(pair.vertex, distances[pair.vertex]))
}
}
}
// Translate distance back to its original weight for any remaining reachable vertices
for (i in 0 until vertexCount) {
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.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 ]
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}}
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]
# Define a constant for infinity
INF <- .Machine$double.xmax
# Function to perform Bellman-Ford algorithm
bellman_ford <- function(augmented_vertex_count, edges, source_vertex) {
distances <- rep(INF, augmented_vertex_count)
distances[source_vertex] <- 0 # R uses 1-based indexing
# Relax edges repeatedly
for (i in 1:(augmented_vertex_count - 1)) {
for (j in 1:nrow(edges)) {
u <- edges[j, 1]
v <- edges[j, 2]
weight <- edges[j, 3]
if (distances[u] != INF && distances[u] + weight < distances[v]) {
distances[v] <- distances[u] + weight
}
}
}
# Check for negative-weight cycles
for (j in 1:nrow(edges)) {
u <- edges[j, 1]
v <- edges[j, 2]
weight <- edges[j, 3]
if (distances[u] != INF && distances[u] + weight < distances[v]) {
return(list()) # Indicates a negative cycle
}
}
return(distances)
}
# Function to perform Dijkstra's algorithm
dijkstra <- function(vertex_count, adjacency_list, source_vertex, h_values) {
distances <- rep(INF, vertex_count)
distances[source_vertex] <- 0
priority_queue <- list(list(vertex = source_vertex, weight = 0))
while (length(priority_queue) > 0) {
# Extract min
priority_queue <- priority_queue[order(sapply(priority_queue, function(x) x$weight))]
current <- priority_queue[[1]]
priority_queue <- priority_queue[-1]
u <- current$vertex
if (current$weight > distances[u]) {
next
}
for (edge in adjacency_list[[u]]) {
v <- edge[1]
weight <- edge[2]
if (distances[u] != INF && distances[u] + weight < distances[v]) {
distances[v] <- distances[u] + weight
priority_queue <- append(priority_queue, list(list(vertex = v, weight = distances[v])))
}
}
}
# Adjust distances
final_distances <- rep(INF, vertex_count)
for (i in 1:vertex_count) {
if (distances[i] != INF) {
final_distances[i] <- distances[i] - h_values[source_vertex] + h_values[i]
}
}
return(final_distances)
}
# Main function to perform Johnson's algorithm
johnsons_algorithm <- function(graph) {
vertex_count <- nrow(graph)
original_edges <- matrix(nrow = 0, ncol = 3)
# Step 0: Build a list of edges for the original graph
for (i in 1:vertex_count) {
for (j in 1:vertex_count) {
weight <- graph[i, j]
if (i != j && weight != INF) {
original_edges <- rbind(original_edges, c(i, j, weight))
}
}
}
# Step 1: Form the augmented graph
augmented_edges <- rbind(original_edges, cbind(vertex_count + 1, 1:vertex_count, rep(0, vertex_count)))
# Step 2: Invoke the Bellman-Ford Algorithm
h_values <- bellman_ford(vertex_count + 1, augmented_edges, vertex_count + 1)
if (length(h_values) == 0) {
return("A negative cycle was detected in the graph.")
}
h_values <- h_values[-length(h_values)] # Remove the value for the augmented vertex
# Step 3: Reweight the edges
adjacency_list <- vector("list", vertex_count)
for (i in 1:nrow(original_edges)) {
u <- original_edges[i, 1]
v <- original_edges[i, 2]
weight <- original_edges[i, 3]
reweight <- weight + h_values[u] - h_values[v]
adjacency_list[[u]] <- append(adjacency_list[[u]], list(c(v, reweight)))
}
# Step 4: Invoke Dijkstra's Algorithm for each vertex
all_pairs_shortest_paths <- list()
for (u in 1:vertex_count) {
all_pairs_shortest_paths[[u]] <- dijkstra(vertex_count, adjacency_list, u, h_values)
}
return(all_pairs_shortest_paths)
}
# Example usage
graph <- matrix(c(0, -5, 2, 3,
INF, 0, 4, INF,
INF, INF, 0, 1,
INF, INF, INF, 0), nrow = 4, byrow = TRUE)
result <- johnsons_algorithm(graph)
if (is.list(result)) {
print("All pairs shortest paths:")
for (i in 1:length(result)) {
print(result[[i]])
}
} else {
print(result)
}
- Output:
[1] "All pairs shortest paths:" [1] 0 -5 -1 0 [1] 1.797693e+308 0.000000e+00 4.000000e+00 5.000000e+00 [1] 1.797693e+308 1.797693e+308 0.000000e+00 1.000000e+00 [1] 1.797693e+308 1.797693e+308 1.797693e+308 0.000000e+00
# 20250614 Raku programming solution
class Edge { # Edge structure
has Int ($.u, $.v);
has Num $.weight;
}
sub bellman-ford(Int $num-vertices, @edges, Int $source) {
my @dist = Inf xx $num-vertices;
@dist[$source] = 0;
for ^($num-vertices - 1) { # Relax edges V-1 times
my $updated = False;
for @edges -> $edge {
if @dist[$edge.u] != Inf && @dist[$edge.u]+$edge.weight < @dist[$edge.v] {
@dist[$edge.v] = @dist[$edge.u] + $edge.weight;
$updated = True;
}
}
last unless $updated;
}
for @edges -> $edge { # Check for negative cycles
if @dist[$edge.u] != Inf && @dist[$edge.u] + $edge.weight < @dist[$edge.v] {
say "Graph contains a negative weight cycle";
return Nil;
}
}
return @dist;
}
sub dijkstra(Int $num-vertices, %adj, Int $source, @h-values) {
my @dist = Inf xx $num-vertices;
@dist[$source] = 0;
my @final-dist = Inf xx $num-vertices;
my @pq = [[0, $source],]; # Priority queue: array of [distance, vertex] pairs
my %visited;
while @pq {
# Sort by distance, then vertex index for stability
@pq.sort({ $^a[0] <=> $^b[0] || $^a[1] <=> $^b[1] });
my ($d, $u) = @pq.shift;
# Skip if already processed or distance is outdated
next if %visited{$u}:exists || $d > @dist[$u];
%visited{$u} = True;
if %adj{$u}:exists { # Relax edges
for %adj{$u}.List -> ($v, $weight) {
if @dist[$u] != Inf && @dist[$u] + $weight < @dist[$v] {
@dist[$v] = @dist[$u] + $weight;
@pq.push: [@dist[$v], $v] unless %visited{$v}:exists;
}
}
}
}
for ^$num-vertices -> $i { # Finalize distances, updating even if previously set
if @dist[$i] != Inf {
@final-dist[$i] = @dist[$i] - @h-values[$source] + @h-values[$i];
}
}
return @final-dist;
}
sub johnsons-algorithm(@graph) {
my ($V, @original-edges) = @graph.elems;
for ^$V X ^$V -> ($i, $j) { # Step 0: Build edge list
my $weight = @graph[$i][$j];
if $i == $j {
if $weight != 0 {
say "Warning: graph[$i][$i] is $weight, expected 0. Setting to 0."
}
} elsif $weight != Inf && $weight != 0 {
@original-edges.push: Edge.new(u => $i, v => $j, weight => $weight.Num)
}
}
my @augmented-edges = @original-edges; # Step 1: Create augmented graph
for ^$V -> $i {
@augmented-edges.push: Edge.new(u => $V, v => $i, weight => 0.Num);
}
my @h-values = bellman-ford($V + 1, @augmented-edges, $V); # Step 2: Run Bellman-Ford
return Nil if @h-values ~~ Nil;
@h-values = @h-values[^$V]; # Remove augmented vertex h-value
my %reweighted-adj; # Step 3: Reweight edges
for ^$V -> $u { %reweighted-adj{$u} = [] }
for @original-edges -> $edge {
if @h-values[$edge.u] == Inf || @h-values[$edge.v] == Inf {
say "Warning: invalid h-values detected.";
}
my $reweight = $edge.weight + @h-values[$edge.u] - @h-values[$edge.v];
%reweighted-adj{$edge.u}.push: [$edge.v, $reweight];
}
my @result = []; # Step 4: Run Dijkstra for each vertex
for ^$V -> $u { @result[$u] = dijkstra($V, %reweighted-adj, $u, @h-values) }
return @result;
}
my @graph = [ # Test case
[0, -5, 2, 3],
[Inf, 0, 4, Inf],
[Inf, Inf, 0, 1],
[Inf, Inf, Inf, 0]
];
with johnsons-algorithm(@graph) {
.say for @_
} else {
say "Negative cycle detected in the graph."
}
You may Attempt This Online!
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 ]
import scala.collection.mutable
import scala.collection.mutable.PriorityQueue
import scala.util.{Success, Try}
object JohnsonsAlgorithm {
private val INF = Double.MaxValue
case class Edge(u: Int, v: Int, weight: Double)
case class VertexAndWeight(vertex: Int, weight: Double)
def main(args: Array[String]): Unit = {
// 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.
val graph = Vector(
Vector( 0.0, -5.0, 2.0, 3.0 ),
Vector( INF, 0.0, 4.0, INF ),
Vector( INF, INF, 0.0, 1.0 ),
Vector( INF, INF, INF, 0.0 )
)
johnsonsAlgorithm(graph) match {
case Some(result) =>
println("All pairs shortest paths:")
println("The element (i, j) is the shortest path between vertex i and vertex j.")
result.foreach { row =>
print("[")
row.foreach { number =>
print(if (number == INF) "INF " else s"$number ")
}
println("]")
}
case None =>
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
*/
def johnsonsAlgorithm(graph: Vector[Vector[Double]]): Option[Vector[Vector[Double]]] = {
val vertexCount = graph.length
// Step 0: Build a list of edges for the original graph
val originalEdges = (for {
i <- graph.indices
j <- graph.indices
weight = graph(i)(j)
if i != j && weight != INF
} yield {
if (i == j && weight != 0.0) {
println(s"Warning: graph[$i][$i] is $weight, expected to be 0.0, resetting it to 0.0")
}
Edge(i, j, weight)
}).toVector
// Step 1: Form the augmented graph
// Add a new vertex with index 'vertexCount' and having 0-weight edges to all the original vertices
val augmentedEdges = originalEdges ++ (0 until vertexCount).map(i => Edge(vertexCount, i, 0.0))
// Step 2: Invoke the Bellman-Ford Algorithm starting from the new vertex
bellmanFordAlgorithm(vertexCount + 1, augmentedEdges, vertexCount) match {
case None => None // A negative cycle was detected
case Some(hValues) =>
val values = hValues.dropRight(1) // Remove the value for the augmented vertex
// Step 3: Reweight the edges
val reweightedAdjacencies = mutable.Map.empty[Int, mutable.ListBuffer[VertexAndWeight]]
(0 until vertexCount).foreach(v => reweightedAdjacencies(v) = mutable.ListBuffer.empty)
originalEdges.foreach { edge =>
// Ensure the 'values' are valid before reweighting
if (values(edge.u) == INF || values(edge.v) == INF) {
println("Warning: invalid hValues detected by the Bellman-Ford Algorithm.")
}
val reweight = edge.weight + values(edge.u) - values(edge.v)
reweightedAdjacencies(edge.u) += VertexAndWeight(edge.v, reweight)
}
// Step 4: Invoke Dijkstra's Algorithm starting from each vertex on the reweighted graph
val allPairsShortestPaths = (0 until vertexCount).map { u =>
dijkstraAlgorithm(vertexCount, reweightedAdjacencies.toMap, u, values)
}.toVector
// Step 5: Return the result matrix
Some(allPairsShortestPaths)
}
}
/**
* Return a list of shortest distances from the source vertex to all other vertices,
* or None if a negative cycle is detected
*/
def bellmanFordAlgorithm(augmentedVertexCount: Int, edges: Vector[Edge], sourceVertex: Int): Option[Vector[Double]] = {
val distances = Array.fill(augmentedVertexCount)(INF)
distances(sourceVertex) = 0.0
// Relax the edges (augmentedVertexCount - 1) times
var updated = true
for (i <- 0 until augmentedVertexCount - 1 if updated) {
updated = false
edges.foreach { edge =>
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
val hasNegativeCycle = edges.exists { edge =>
distances(edge.u) != INF && distances(edge.u) + edge.weight < distances(edge.v)
}
if (hasNegativeCycle) None else Some(distances.toVector)
}
/**
* Return a list of shortest path distances from the source vertex in the original graph to all other vertices
*/
def dijkstraAlgorithm(vertexCount: Int,
reweightedAdjacencies: Map[Int, mutable.ListBuffer[VertexAndWeight]],
sourceVertex: Int,
values: Vector[Double]): Vector[Double] = {
val distances = Array.fill(vertexCount)(INF)
distances(sourceVertex) = 0.0
// Use reverse ordering for min-heap behavior
implicit val ordering: Ordering[VertexAndWeight] = Ordering.by[VertexAndWeight, Double](_.weight).reverse
val priorityQueue = mutable.PriorityQueue[VertexAndWeight]()
priorityQueue.enqueue(VertexAndWeight(sourceVertex, 0.0))
val finalDistances = Array.fill(vertexCount)(INF)
while (priorityQueue.nonEmpty) {
val VertexAndWeight(vertex, weight) = priorityQueue.dequeue()
if (weight <= distances(vertex)) {
// Store the final shortest path distance, translated back to the distance in the original graph
if (finalDistances(vertex) == INF) {
if (distances(vertex) == INF) { // 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
reweightedAdjacencies.get(vertex).foreach { adjacentVertices =>
adjacentVertices.foreach { case VertexAndWeight(adjVertex, adjWeight) =>
if (distances(vertex) != INF && distances(vertex) + adjWeight < distances(adjVertex)) {
distances(adjVertex) = distances(vertex) + adjWeight
priorityQueue.enqueue(VertexAndWeight(adjVertex, distances(adjVertex)))
}
}
}
}
}
// Translate distance back to its original weight for any remaining reachable vertices
(0 until vertexCount).foreach { i =>
if (finalDistances(i) == INF && distances(i) != INF) {
finalDistances(i) = distances(i) - values(sourceVertex) + values(i)
}
}
finalDistances.toVector
}
}
- 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 ]
import Foundation
struct Edge {
let u: Int
let v: Int
let weight: Double
}
struct VertexAndWeight {
let vertex: Int
let weight: Double
}
class JohnsonAlgorithm {
private static let INF = Double.greatestFiniteMagnitude
static 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.
let 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]
]
let result = johnsonsAlgorithm(graph: graph)
if let shortestPaths = result {
print("All pairs shortest paths:")
print("The element (i, j) is the shortest path between vertex i and vertex j.")
for row in shortestPaths {
print("[", terminator: "")
for number in row {
print(number == INF ? "INF" : "\(number)", terminator: " ")
}
print("]")
}
} else {
print("A negative cycle was detected in the graph.")
}
}
private static func johnsonsAlgorithm(graph: [[Double]]) -> [[Double]]? {
let vertexCount = graph.count
var originalEdges = [Edge]()
// Step 0: Build a list of edges for the original graph
for i in 0..<vertexCount {
for j in 0..<vertexCount {
let weight = graph[i][j]
if i == j {
if weight != 0.0 {
print("Warning: graph[i][i] for i = \(i) is \(weight), expected to be 0.0, resetting it to 0.0")
}
} else if weight != INF {
originalEdges.append(Edge(u: i, v: j, weight: weight))
}
}
}
// Step 1: Form the augmented graph
var augmentedEdges = originalEdges
for i in 0..<vertexCount {
augmentedEdges.append(Edge(u: vertexCount, v: i, weight: 0.0))
}
// Step 2: Invoke the Bellman-Ford Algorithm starting from the new vertex
guard let hValues = bellmanFordAlgorithm(augmentedVertexCount: vertexCount + 1, edges: augmentedEdges, sourceVertex: vertexCount) else {
return nil // A negative cycle was detected by the Bellman-Ford Algorithm
}
var values = hValues
values.removeLast() // Remove the value for the augmented vertex
// Step 3: Reweight the edges
var reweightedAdjacencies = [Int: [VertexAndWeight]]()
for v in 0..<vertexCount {
reweightedAdjacencies[v] = [VertexAndWeight]()
}
for edge in originalEdges {
if values[edge.u] == INF || values[edge.v] == INF {
print("Warning: invalid hValues detected by the Bellman-Ford Algorithm.")
}
let reweight = edge.weight + values[edge.u] - values[edge.v]
reweightedAdjacencies[edge.u]?.append(VertexAndWeight(vertex: edge.v, weight: reweight))
}
// Step 4: Invoke Dijkstra's Algorithm starting from each vertex on the reweighted graph
var allPairsShortestPaths = [[Double]]()
for u in 0..<vertexCount {
let shortestPaths = dijkstraAlgorithm(vertexCount: vertexCount, reweightedAdjacencies: reweightedAdjacencies, sourceVertex: u, values: values)
allPairsShortestPaths.append(shortestPaths)
}
// Step 5: Return the result matrix
return allPairsShortestPaths
}
private static func bellmanFordAlgorithm(augmentedVertexCount: Int, edges: [Edge], sourceVertex: Int) -> [Double]? {
var distances = [Double](repeating: INF, count: augmentedVertexCount)
distances[sourceVertex] = 0.0
// Relax the edges (augmentedVertexCount - 1) times
var updated: Bool
for _ in 0..<augmentedVertexCount - 1 {
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
}
}
if !updated { break }
}
// 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 nil // Indicates to the calling method that a negative cycle has been detected
}
}
return distances
}
private static func dijkstraAlgorithm(vertexCount: Int, reweightedAdjacencies: [Int: [VertexAndWeight]], sourceVertex: Int, values: [Double]) -> [Double] {
var distances = [Double](repeating: INF, count: vertexCount)
distances[sourceVertex] = 0.0
var priorityQueue = [VertexAndWeight]()
priorityQueue.append(VertexAndWeight(vertex: sourceVertex, weight: 0.0))
var finalDistances = [Double](repeating: INF, count: vertexCount)
while !priorityQueue.isEmpty {
priorityQueue.sort { $0.weight < $1.weight }
let vertexAndWeight = priorityQueue.removeFirst()
let vertex = vertexAndWeight.vertex
if vertexAndWeight.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 {
finalDistances[vertex] = INF
} else {
finalDistances[vertex] = distances[vertex] - values[sourceVertex] + values[vertex]
}
}
// Relax the edges outgoing from vertex
if let adjacencies = reweightedAdjacencies[vertex] {
for pair in adjacencies {
if distances[vertex] != INF && distances[vertex] + pair.weight < distances[pair.vertex] {
distances[pair.vertex] = distances[vertex] + pair.weight
priorityQueue.append(VertexAndWeight(vertex: pair.vertex, weight: distances[pair.vertex]))
}
}
}
}
// Translate distance back to its original weight for any remaining reachable vertices
for i in 0..<vertexCount {
if finalDistances[i] == INF && distances[i] != INF {
finalDistances[i] = distances[i] - values[sourceVertex] + values[i]
}
}
return finalDistances
}
}
// Run the algorithm
JohnsonAlgorithm.main()
- 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 ]
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]
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 ]