const inf = Number.POSITIVE_INFINITY;

// An implementation of the Bellman-Ford algorithm. The algorithm finds the 
// shortest path between a starting node and all other nodes in the graph. 
// The algorithm also detects negative cycles.
class BellmanFord {

    // Constructor takes as input a graph represented as a cost adjacency 
    // matrix. The cost of an edge (i,j) is given by matrix[i][j]. The cost
    // of a non-existing edge is given by inf. The cost of a self-loop (i,i)
    // is 0.
    constructor(matrix) {
        // The cost adjacency matrix.
        this.matrix = matrix;
        // The number of nodes in the graph.
        this.size = matrix.length;
        // The distance from the starting node to each node.
        this.distance = new Array(this.size);
        // The predecessor of each node in the shortest path.
        this.predecessor = new Array(this.size);

        // If the following are set as arrays, they are used to store
        // the distance and predecessor arrays at each iteration.
        this.distances = null;
        this.predecessors = null;
    }

    // Runs the algorithm. Returns false when negative cycles are found, 
    // and true otherwise.
    run(starting = 0) {
        // Initialize the distance to all nodes to be infinity
        // except for the start node which is zero.
        this.distance.fill(inf);
        this.distance[starting] = 0;

        // Initialize predecessor array which will be used in shortest path
        // reconstruction after the algorithm has terminated.
        this.predecessor.fill(null);

        // Repeat relaxations for all edges at most this.size-1 times.
        for (let k = 0; k + 1 < this.size; ++k) {
            let counter = 0; // Count the number of relaxations.
            // Iterate through all edges.
            for (let j = 0; j < this.size; ++j)
                for (let i = 0; i < this.size; ++i)
                    // Relaxation step for edge (j,i). We need to check that j 
                    // and i are different, the distance to j is not infinity, 
                    // and the cost of the edge (j,i) is not infinity.
                    if ((j != i) && (this.distance[j] != inf) &&
                        (this.matrix[j][i] != inf)) {
                        let new_dist = this.distance[j] + this.matrix[j][i];
                        // If the new distance is smaller than the current 
                        // distance to i, update the distance and the 
                        // predecessor of i.
                        if (new_dist < this.distance[i]) {
                            // Relaxation step.
                            this.distance[i] = new_dist;
                            this.predecessor[i] = j;
                            counter++;
                        }
                    }

            // Store the distance and predecessor arrays.
            if (this.distances != null) {
                this.distances.push(copy(this.distance));
                this.predecessors.push(copy(this.predecessor));
            }

            if (counter == 0) // Stop when no more relaxation.
                return true;  // There is no negative cycles.
        }

        return false; // There is a negative cycle.
    }

    // Interpretation of the result that create a path (list of nodes) of the
    // shortest path from starting point to target.
    getPath(target) {
        if (target < 0 || target >= this.size || this.distance[target] == inf)
            return []; // No path from starting point to target.

        let path = [];
        for (let i = target; this.predecessor[i] != null; i = this.predecessor[i])
            path.push(i);
        return path.reverse();
    }

    // Interpretation of the result that create a route (list of edges) of the
    // shortest path from starting point to target. Each edge is represented as
    // a triple (source, target, distance).
    getRoute(target) {
        if (target < 0 || target >= this.size || this.distance[target] == inf)
            return []; // No path from starting point to target.

        let route = [];
        for (let i = target; this.predecessor[i] != null; i = this.predecessor[i])
            route.push([this.predecessor[i], i, this.distance[i]]);
        // The distance of each edge is the distance from the source to the target. 
        // We need to convert it to the distance of the edge itself.
        for (let i = 0; i + 1 < route.length; ++i)
            route[i][2] -= route[i + 1][2];

        return route.reverse();
    }

    // Get a string representation of the result of the algorithm.
    toString() {
        let s = '[';
        for (let i = 0; i < this.size; i++)
            s += (this.distance[i] == inf ?
                'inf' : this.distance[i]) + (i + 1 < this.size ? ',' : '');
        s += '] [';
        for (let i = 0; i < this.size; i++)
            s += (this.predecessor[i] == null ?
                'null' : this.predecessor[i]) + (i + 1 < this.size ? ',' : '');
        s += ']';
        return s;
    }
}