Floyd-Warshall algorithm: Difference between revisions

=={{header|Nim}}==

{{trans|D}}

<lang Nim>import sequtils, strformat

type

Weight = tuple[src, dest, value: int]

Weights = seq[Weight]

#---------------------------------------------------------------------------------------------------

proc printResult(dist: seq[seq[float]]; next: seq[seq[int]]) =

echo "pair dist path"

for i in 0..next.high:

for j in 0..next.high:

if i != j:

var u = i + 1

let v = j + 1

var path = fmt"{u} -> {v} {dist[i][j].toInt:2d} {u}"

while true:

u = next[u-1][v-1]

path &= fmt" -> {u}"

if u == v: break

echo path

#---------------------------------------------------------------------------------------------------

proc floydWarshall(weights: Weights; numVertices: Positive) =

var dist = repeat(repeat(Inf, numVertices), numVertices)

for w in weights:

dist[w.src - 1][w.dest - 1] = w.value.toFloat

var next = repeat(newSeq[int](numVertices), numVertices)

for i in 0..<numVertices:

for j in 0..<numVertices:

if i != j:

next[i][j] = j + 1

for k in 0..<numVertices:

for i in 0..<numVertices:

for j in 0..<numVertices:

if dist[i][j] > dist[i][k] + dist[k][j]:

dist[i][j] = dist[i][k] + dist[k][j]

next[i][j] = next[i][k]

printResult(dist, next)

#———————————————————————————————————————————————————————————————————————————————————————————————————

let weights: Weights = @[(1, 3, -2), (2, 1, 4), (2, 3, 3), (3, 4, 2), (4, 2, -1)]

let numVertices = 4

floydWarshall(weights, numVertices)</lang>

{{out}}

<pre>pair dist path

1 -> 2 -1 1 -> 3 -> 4 -> 2

1 -> 3 -2 1 -> 3

1 -> 4 0 1 -> 3 -> 4

2 -> 1 4 2 -> 1

2 -> 3 2 2 -> 1 -> 3

2 -> 4 4 2 -> 1 -> 3 -> 4

3 -> 1 5 3 -> 4 -> 2 -> 1

3 -> 2 1 3 -> 4 -> 2

3 -> 4 2 3 -> 4

4 -> 1 3 4 -> 2 -> 1

4 -> 2 -1 4 -> 2

4 -> 3 1 4 -> 2 -> 1 -> 3</pre>