56 lines
1.7 KiB
Nim
56 lines
1.7 KiB
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)
|