// Copyright (c) 2023, Sam Hadow
    //
    //floyd_warshall.js
    //
    //  This program is free software: you can redistribute it and/or modify it under the terms of the GNU General Public License as published by the Free Software Foundation, either version 3 of the License, or (at your option) any later version.
    //
    // This program is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License for more details.
    //
    // You should have received a copy of the GNU General Public License along with this program. If not, see <https://www.gnu.org/licenses/>.

function floyd_warshall(matrix, next, size) {
    // Floyd Warshall algorithm
    for (let k = 0; k < size; k++){
        for (let i = 0; i < size; i++){
            for (let j = 0; j < size; j++){
                // we need to have matrix[i][k] and matrix[k][j] both defined
                if (!((matrix[i][k] == undefined) || (matrix[k][j] == undefined)) ){
                    // here we use !(a<=b) instead of a>b to handle situations where a is undefined
                    // (if a is undefined a <= any_value will be false)
                    if (!(matrix[i][j] <= matrix[i][k] + matrix[k][j])) {
                        matrix[i][j] = matrix[i][k] + matrix[k][j];
                        next[i][j][0] = next[i][k][0]
                        next[i][j][1] = next[i][k][1]
                    }
                }
            }
        }
    }

}