import { bellmanFord } from './bellman_ford'
import { dijkstra } from './dijkstra'

/**
 * @function johnson
 * @description Compute the shortest path for all pairs of nodes. The input graph is in adjacency list form. It is a multidimensional array of edges. graph[i] holds the edges for the i'th node. Each edge is a 2-tuple where the 0'th item is the destination node, and the 1'th item is the edge weight. Returned undefined if the graph has negative weighted cycles.
 * @Complexity_Analysis
 * Time complexity: O(VElog(V))
 * Space Complexity: O(V^2) to hold the result
 * @param {[number, number][][]} graph - The graph in adjacency list form
 * @return {number[][]} - A matrix holding the shortest path for each pair of nodes. matrix[i][j] holds the distance of the shortest path (i -> j).
 * @see https://en.wikipedia.org/wiki/Johnson%27s_algorithm
 */
export const johnson = (graph: [number, number][][]): number[][] | undefined => {
  const N = graph.length;

  // Add a new node and 0 weighted edges from the new node to all existing nodes.
  const newNodeGraph = structuredClone(graph);
  const newNode: [number, number][] = [];
  for (let i = 0; i < N; ++i) {
    newNode.push([i, 0]);
  }
  newNodeGraph.push(newNode);

  // Compute distances from the new node to existing nodes using the Bellman-Ford algorithm.
  const adjustedGraph = bellmanFord(newNodeGraph, N);
  if (adjustedGraph === undefined) {
    // Found a negative weight cycle.
    return undefined;
  }

  for (let i = 0; i < N; ++i) {
    for (const edge of graph[i]) {
      // Adjust edge weights using the Bellman Ford output weights. This ensure that:
      // 1. Each weight is non-negative. This is required for the Dijkstra algorithm.
      // 2. The shortest path from node i to node j consists of the same nodes with or without adjustment.
      edge[1] += adjustedGraph[i] - adjustedGraph[edge[0]];
    }
  }

  const shortestPaths: number[][] = [];
  for (let i = 0; i < N; ++i) {
    // Compute Dijkstra weights for each node and re-adjust weights to their original values.
    const dijkstraShorestPaths = dijkstra(graph, i);
    for (let j = 0; j < N; ++j) {
      dijkstraShorestPaths[j] += adjustedGraph[j] - adjustedGraph[i];
    }
    shortestPaths.push(dijkstraShorestPaths);
  }
  return shortestPaths;
}