# Bellman-Ford'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 a
# given node in a graph to all the other nodes in the
# graph. It allows the graph to have negative edges
# and can detect the presence of negative cycles.
# Complexity: O(edges * nodes)
# ----------------------------------------------------

DATA:
∞ is number                 # Infinity value (not really infinity)
nodeCount    is number      # Number of nodes in the graph
edgeCount    is number      # Number of edges in the graph
edgesStart   is number list # List of the starting nodes of each edge in the graph
edgesEnd     is number list # List of the destination nodes of each edge in the graph
edgesWeight  is number list # List of the weight of each edge in the graph
startingNode is number      # The starting node for our algorithm
distances    is number list # List that holds the minimum distance from i to the starting node
i is number
j is number
newDistance  is number

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

# Set number of nodes in graph
store 6 in nodeCount

# Initialize each index of the distances list to infinity
while j is less than nodeCount do
    push ∞ to distances
    in j solve j + 1
repeat

# Set distance from starting node to itself to 0
store 0 in startingNode
store 0 in distances:startingNode

# Set graph edges
push  0 to edgesStart    # l(0 -> 1) = 4
push  1 to edgesEnd
push  4 to edgesWeight
push  0 to edgesStart    # l(0 -> 2) = 7
push  2 to edgesEnd
push  7 to edgesWeight
push  0 to edgesStart    # l(0 -> 5) = 3
push  5 to edgesEnd
push  3 to edgesWeight
push  1 to edgesStart    # l(1 -> 2) = 3
push  2 to edgesEnd
push  3 to edgesWeight
push  1 to edgesStart    # l(1 -> 4) = 1
push  4 to edgesEnd
push  1 to edgesWeight
push  1 to edgesStart    # l(1 -> 5) = -2
push  5 to edgesEnd
push -2 to edgesWeight
push  2 to edgesStart    # l(2 -> 3) = 1
push  3 to edgesEnd
push  1 to edgesWeight
push  2 to edgesStart    # l(2 -> 4) = 1
push  4 to edgesEnd
push  1 to edgesWeight
push  4 to edgesStart    # l(4 -> 3) = 4
push  3 to edgesEnd
push  4 to edgesWeight
push  5 to edgesStart    # l(5 -> 4) = 3
push  4 to edgesEnd
push  3 to edgesWeight

# Store the number of edges in our graph
get length of edgesWeight in edgeCount

# --- Invariant -------------------------------------------------
# When the k-th iteration is over, our distances list holds the
# length of the shortest path from the starting node to every
# other path in the graph of length less than or equal to k.
# This means, the lengths of the paths from 'startingNode' to
# node i that use at most k edges.
# ---------------------------------------------------------------

while i is less than nodeCount do
    # For every edge in the graph
    store 0 in j
    while j is less than edgeCount do
        # If the distance from the starting node to the starting node of
        # this edge plus the weight of this edge...
        in newDistance solve distances:edgesStart:j + edgesWeight:j
        # ...is less that the distance of the ending node of this edge...
        if newDistance is less than distances:edgesEnd:j then
            #...then this path is shorter, so we'll take it.
            store newDistance in distances:edgesEnd:j
        end if
        in j solve j + 1
    repeat
    in i solve i + 1
repeat

# --- Negative cycles ----------------------------------------------
# While the algorithm asumes that no negative cycles are to be found
# in the graph, we can detect wether the graph has negative cycles
# or not by executing the loop above one more time and inspecting
# or list of distances. If any of the values there is lower than it
# was before running the loop again, this means that there are
# negative cycles found within our graph.
# ------------------------------------------------------------------

# Print the result:
display "["
store 0 in i
while i is less than nodeCount do
    display distances:i
    in i solve i + 1
    if i is less than nodeCount then
        display ", "
    end if
repeat
display "]" crlf