Skip to content
Permalink
Branch: master
Find file Copy path
Find file Copy path
Fetching contributors…
Cannot retrieve contributors at this time
107 lines (98 sloc) 4.05 KB
# 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
You can’t perform that action at this time.