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