Fast, lightweight library computes single-source shortest path distances on directed graphs with non-negative edges, employing smart algorithm selection for optimal performance without external dependencies.
A fast, lightweight Kotlin Multiplatform library to compute single‑source shortest path (SSSP) distances on directed graphs with non‑negative edge weights.
Artifacts are published with the following coordinates:
com.dayanrubensssp0.4.0Gradle (Kotlin DSL):
// settings.gradle.kts
// Ensure you have Maven Central in repositories
dependencyResolutionManagement {
repositories {
mavenCentral()
}
}
// build.gradle.kts (root or module)
dependencies {
implementation("com.dayanruben:sssp:0.4.0")
}
Gradle (Groovy DSL):
// settings.gradle
pluginManagement {
repositories { mavenCentral() }
}
dependencyResolutionManagement {
repositories { mavenCentral() }
}
// build.gradle
dependencies {
implementation "com.dayanruben:sssp:0.4.0"
}
Compute distances from a single source s to all vertices 0..n-1. Unreachable vertices get Double.POSITIVE_INFINITY.
Undirected graphs: add edges both ways (u->v and v->u).
Public entry point:
fun singleSourceShortestPaths(
n: Int,
adj: List<List<Pair<Int, Double>>>,
s: Int,
dijkstraFallbackThreshold: Int = 64,
): DoubleArray
Parameters
emptyList() if a vertex has no outgoing edgesReturn value
Double.POSITIVE_INFINITY.Performance notes
dijkstraFallbackThreshold.INF.You can see runnable examples in tests under sssp/src/commonTest/kotlin/SSSPTest.kt.
This is a Kotlin Multiplatform library with targets:
This library follows semantic versioning as much as feasible for a small algorithmic library. See the Releases page for changes.
Issues and pull requests are welcome! Please include:
Apache License 2.0 — see LICENSE.
fun main() {
val n = 4
val adj: List<List<Pair<Int, Double>>> = listOf(
listOf(1 to 1.0, 2 to 4.0), // 0 -> 1 (1), 0 -> 2 (4)
listOf(2 to 2.0, 3 to 6.0), // 1 -> 2 (2), 1 -> 3 (6)
listOf(3 to 3.0), // 2 -> 3 (3)
emptyList() // 3 has no outgoing edges
)
val s = 0
val dist: DoubleArray = singleSourceShortestPaths(n, adj, s)
println(dist.joinToString()) // 0.0, 1.0, 3.0, 6.0
}
n <= thresholdSurfaced from shared tags and platforms — no rankings paid for.