# Floyd-Warshall's Algorithm
# written in LDPL by Martín del Río
# https://www.ldpl-lang.org/
# Created for LDPL 3.1.0 'Diligent Dreadnoughtus'

# --- Description ------------------------------------
# This algorithm finds the shortest distance from each
# node in the graph to every other node in the graph.
# It allows the graph to have negative edges and can
# detect the presence of negative cycles.
# The complexity of the algorithm is O(nodes ^ 3).
# ----------------------------------------------------

DATA:
∞ is number                   # Infinity value (not really infinity)
nodeCount   is number         # Number of nodes in the graph
distances   is number list    # Number matrix that contains the distance from node i to node j
k is number
i is number
j is number
distanceIKJ is number
IJ is number
IK is number
KJ is number

PROCEDURE:
# Set the value of "infinity" to something big
store 99999 in ∞

# Set number of nodes in graph
store 4 in nodeCount

# Create distances matrix
push  0 to distances # 0->0                | 0 1 2 3
push  3 to distances # 0->1               -+--------
push  ∞ to distances # 0->2               0| 0 3 ∞ 3
push  3 to distances # 0->3               1| 2 0 2 2
push  2 to distances # 1->0               2|-2 ∞ 0 1
push  0 to distances # 1->1               3| ∞ 4 4 0
push  2 to distances # 1->2
push  2 to distances # 1->3               ↑↑↑↑↑↑↑↑↑↑
push -2 to distances # 2->0               This is the matrix we are making.
push  ∞ to distances # 2->1               We use a list to store it, like this:
push  0 to distances # 2->2               [0, 3, ∞, 3, 2, 0, 2, 2, -2, ∞, 0, 1, ∞, 4, 4, 0]
push  1 to distances # 2->3
push  ∞ to distances # 3->0               The value [i][j], i being the rows and j the columns
push  4 to distances # 3->1               stores the length of the shortest known path from i to j.
push  4 to distances # 3->2
push  0 to distances # 3->3

# --- Invariant -------------------------------------------------
# When the k-th iteration is over, our distances matrix stores
# in the position (i, j) the length of the shortest path from i
# to j using only vertices contained in the set {0 .. k}. This
# means that in the second iteration (k = 1), the position (i, j)
# will hold the length of the shortest path from i to j that uses
# only nodes 0 and 1.
# ---------------------------------------------------------------

store 0 in k
while k is less than nodeCount do
    store 0 in i
    while i is less than nodeCount do
        store 0 in j
        while j is less than nodeCount do
            in IJ solve j + (i * nodeCount)
            in IK solve k + (i * nodeCount)
            in KJ solve j + (k * nodeCount)
            in distanceIKJ solve distances:IK + distances:KJ
            # If the length of the path i -> k -> j
            # is shorter than the length of i -> j...
            if distanceIKJ is less than distances:IJ then
                # ...then replace the shortest distance that we've recorded
                # between these two nodes for the one that we've just found.
                store distanceIKJ in distances:IJ
            end if
            in j solve j + 1
        repeat
        in i solve i + 1
    repeat
    in k solve k + 1
repeat

# --- Negative cycles ----------------------------------------------
# While the algorithm asumes that no negative cycles are to be found
# in the graph, we can detect whether the graph has negative cycles
# or not by executing the loop above one more time and inspecting
# the diagonal of the distances matrix: the presence of a negative
# number indicates that the graph contains at least one negative
# cycle.
# ------------------------------------------------------------------

# Print the result:
store 0 in i
while i is less than nodeCount do
    store 0 in j
    while j is less than nodeCount do
        in IJ solve j + (i * nodeCount)
        if distances:IJ is greater than or equal to 0 then
            display " "
        end if
        display distances:IJ " "
        in j solve j + 1
    repeat
    display crlf
    in i solve i + 1
repeat