59 lines
1.8 KiB
Kotlin
59 lines
1.8 KiB
Kotlin
// version 1.1
|
|
|
|
object FloydWarshall {
|
|
fun doCalcs(weights: Array<IntArray>, nVertices: Int) {
|
|
val dist = Array(nVertices) { DoubleArray(nVertices) { Double.POSITIVE_INFINITY } }
|
|
for (w in weights) dist[w[0] - 1][w[1] - 1] = w[2].toDouble()
|
|
val next = Array(nVertices) { IntArray(nVertices) }
|
|
for (i in 0 until next.size) {
|
|
for (j in 0 until next.size) {
|
|
if (i != j) next[i][j] = j + 1
|
|
}
|
|
}
|
|
for (k in 0 until nVertices) {
|
|
for (i in 0 until nVertices) {
|
|
for (j in 0 until nVertices) {
|
|
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)
|
|
}
|
|
|
|
private fun printResult(dist: Array<DoubleArray>, next: Array<IntArray>) {
|
|
var u: Int
|
|
var v: Int
|
|
var path: String
|
|
println("pair dist path")
|
|
for (i in 0 until next.size) {
|
|
for (j in 0 until next.size) {
|
|
if (i != j) {
|
|
u = i + 1
|
|
v = j + 1
|
|
path = ("%d -> %d %2d %s").format(u, v, dist[i][j].toInt(), u)
|
|
do {
|
|
u = next[u - 1][v - 1]
|
|
path += " -> " + u
|
|
} while (u != v)
|
|
println(path)
|
|
}
|
|
}
|
|
}
|
|
}
|
|
}
|
|
|
|
fun main(args: Array<String>) {
|
|
val weights = arrayOf(
|
|
intArrayOf(1, 3, -2),
|
|
intArrayOf(2, 1, 4),
|
|
intArrayOf(2, 3, 3),
|
|
intArrayOf(3, 4, 2),
|
|
intArrayOf(4, 2, -1)
|
|
)
|
|
val nVertices = 4
|
|
FloydWarshall.doCalcs(weights, nVertices)
|
|
}
|