52 lines
1.5 KiB
Swift
52 lines
1.5 KiB
Swift
func floydWarshall(_ weights: [[Int]], _ numVertices: Int) {
|
|
var dist = Array(repeating: Array(repeating: Double.infinity, count: numVertices), count: numVertices)
|
|
var next = Array(repeating: Array(repeating: 0, count: numVertices), count: numVertices)
|
|
|
|
for weight in weights {
|
|
dist[weight[0] - 1][weight[1] - 1] = Double(weight[2])
|
|
}
|
|
|
|
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][k] + dist[k][j] < dist[i][j] {
|
|
dist[i][j] = dist[i][k] + dist[k][j]
|
|
next[i][j] = next[i][k]
|
|
}
|
|
}
|
|
}
|
|
}
|
|
|
|
printResult(dist, next)
|
|
}
|
|
|
|
func printResult(_ dist: [[Double]], _ next: [[Int]]) {
|
|
print("pair dist path")
|
|
for i in 0..<next.count {
|
|
for j in 0..<next.count {
|
|
if i != j {
|
|
var u = i + 1
|
|
let v = j + 1
|
|
var path = "\(u) -> \(v) \(Int(dist[i][j])) \(u)"
|
|
repeat {
|
|
u = next[u - 1][v - 1]
|
|
path += " -> \(u)"
|
|
} while u != v
|
|
print(path)
|
|
}
|
|
}
|
|
}
|
|
}
|
|
|
|
let weights = [[1, 3, -2], [2, 1, 4], [2, 3, 3], [3, 4, 2], [4, 2, -1]]
|
|
let numVertices = 4
|
|
floydWarshall(weights, numVertices)
|