Skip to content

Instantly share code, notes, and snippets.

@ramdhanjr11

ramdhanjr11/dijkstra.kt

Created November 26, 2022 03:33
Show Gist options

  • Select an option

    Learn more about clone URLs
  • Save ramdhanjr11/e9cb77cded6e355125fec36f82b4f7e4 to your computer and use it in GitHub Desktop.

Select an option

Learn more about clone URLs
Save ramdhanjr11/e9cb77cded6e355125fec36f82b4f7e4 to your computer and use it in GitHub Desktop.
Download ZIP
Raw
dijkstra.kt
package dijkstra
fun <T> dijkstra(graph: Graph<T>, start: T): Map<T, T?> {
val S: MutableSet<T> = mutableSetOf() // subset dari simpul yang kita ketahui jarak sebenarnya, contoh [A, B, C, D, E]
/*
* variable delta mewakili jumlah dari banyaknya jalur terpendek
* Isi pertama adalah infinity dengan Int.MAX_VALUE untuk nanti dibandingkan
*/
val delta = graph.vertices.map { it to Double.MAX_VALUE }.toMap().toMutableMap()
delta[start] = 0.0
/* previous adalah variable untuk menampung path yang telah dikunjungi
* inisialiasasi awal semua isi menjadi null
*/
val previous: MutableMap<T, T?> = graph.vertices.map { it to null }.toMap().toMutableMap()
// Melakukan perulangan jika S != subset simpul, contoh [A, B] != [A, B, C, D]
while (S != graph.vertices) {
// v adalah simpul terdekat yang belum dikunjungi
val v: T = delta
.filter { !S.contains(it.key) }
.minByOrNull { it.value }!!
.key
graph.edges.getValue(v).minus(S).forEach { neighbor ->
val newPath = delta.getValue(v) + graph.weights.getValue(Pair(v, neighbor))
if (newPath < delta.getValue(neighbor)) {
delta[neighbor] = newPath
previous[neighbor] = v
}
}
S.add(v)
}
return previous.toMap()
}
// fungsi untuk menampilkan shortest path dari fungsi dijkstra yang mengembalikan nilai previous path
fun <T> shortestPath(shortestPathTree: Map<T, T?>, start: T, end: T): List<T> {
fun pathTo(start: T, end: T): List<T> {
if (shortestPathTree[end] == null) return listOf(end)
return listOf(pathTo(start, shortestPathTree[end]!!), listOf(end)).flatten()
}
return pathTo(start, end)
}
// Mengambil isian yang unik menjadikannya set, contoh [[A, B], [A, C]] menjadi [A, B, C]
fun <T> List<Pair<T, T>>.getUniqueValuesFromPairs(): Set<T> = this
.map { (a, b) -> listOf(a, b) }
.flatten()
.toSet()
// Mengambil isian yang unik untuk dikelompokan dengan data awalnya, contoh [[A, B], [A, C], [A, D]] menjadi [A=[B, C, D]]
fun <T> List<Pair<T, T>>.getUniqueValuesFromPairs(predicate: (T) -> Boolean): Set<T> = this
.map { (a, b) -> listOf(a, b) }
.flatten()
.filter(predicate)
.toSet()
data class Graph<T>(
val vertices: Set<T>,
val edges: Map<T, Set<T>>,
val weights: Map<Pair<T, T>, Double>
) {
constructor(weights: Map<Pair<T, T>, Double>): this(
vertices = weights.keys.toList().getUniqueValuesFromPairs(),
edges = weights.keys
.groupBy { it.first }
.mapValues { it.value.getUniqueValuesFromPairs { x -> x != it.key } }
.withDefault { emptySet() },
weights = weights
)
}
fun main() {
val weights = mapOf(
Pair("V1", "V2") to 36.2656,
Pair("V2", "V3") to 42.7383,
Pair("V2", "V30") to 37.5134,
Pair("V3", "V4") to 58.5482,
Pair("V3", "V5") to 38.1423,
Pair("V4", "V6") to 35.2272,
Pair("V4", "V8") to 19.1127,
Pair("V5", "V6") to 42.4622,
Pair("V5", "V9") to 42.2893,
Pair("V6", "V7") to 41.0782,
Pair("V6", "V14") to 20.3663,
Pair("V7", "V8") to 31.3121,
Pair("V9", "V10") to 19.8494,
Pair("V9", "V11") to 26.0924,
Pair("V10", "V11") to 32.8161,
Pair("V10", "V12") to 31.9120,
Pair("V11", "V10") to 32.8161,
Pair("V11", "V56") to 28.2103,
Pair("V12", "V56") to 24.8310,
Pair("V12", "V13") to 24.8310,
Pair("V14", "V13") to 19.3630,
Pair("V14", "V15") to 26.8924,
Pair("V13", "V16") to 28.0007,
Pair("V15", "V17") to 13.6294,
Pair("V15", "V16") to 38.7913,
Pair("V16", "V17") to 32.6332,
Pair("V56", "V57") to 59.1899,
Pair("V56", "V58") to 51.9781,
Pair("V57", "V58") to 51.9781,
Pair("V58", "V59") to 32.4985,
Pair("V59", "V60") to 21.2612,
Pair("V59", "V61") to 13.2203,
Pair("V61", "V19") to 72.8690,
Pair("V17", "V18") to 34.9624,
Pair("V17", "V61") to 31.8778,
Pair("V18", "V20") to 30.6276,
Pair("V18", "V25") to 34.4662,
Pair("V19", "V20") to 23.6507,
Pair("V19", "V21") to 36.9811,
Pair("V20", "V18") to 25.8434,
Pair("V20", "V23") to 28.3031,
Pair("V20", "V22") to 42.3748,
Pair("V21", "V22") to 62.4020,
Pair("V21", "V44") to 23.7233,
Pair("V22", "V20") to 42.3748,
Pair("V22", "V24") to 52.7302,
Pair("V22", "V46") to 19.6493,
Pair("V23", "V24") to 28.8189,
Pair("V23", "V26") to 42.1102,
Pair("V25", "V26") to 78.7324,
Pair("V25", "V28") to 25.4698,
Pair("V26", "V27") to 53.3484,
Pair("V26", "V25") to 78.7324,
Pair("V27", "V26") to 53.3484,
Pair("V27", "V28") to 53.1003,
Pair("V27", "V53") to 56.8477,
Pair("V28", "V29") to 45.5241,
Pair("V29", "V55") to 62.3534,
Pair("V29", "V54") to 29.6839,
Pair("V30", "V31") to 42.8076,
Pair("V30", "V33") to 27.5286,
Pair("V31", "V32") to 18.4661,
Pair("V31", "V33") to 41.8804,
Pair("V31", "V60") to 41.8804,
Pair("V32", "V37") to 16.2205,
Pair("V32", "V33") to 29.4262,
Pair("V33", "V34") to 34.5258,
Pair("V33", "V36") to 15.6944,
Pair("V34", "V35") to 48.1100,
Pair("V35", "V36") to 43.7854,
Pair("V36", "V43") to 8.2756,
Pair("V37", "V38") to 39.1518,
Pair("V37", "V40") to 21.3216,
Pair("V38", "V39") to 29.9508,
Pair("V39", "V40") to 36.1122,
Pair("V40", "V41") to 16.4172,
Pair("V41", "V42") to 26.9823,
Pair("V41", "V43") to 35.4692,
Pair("V42", "V21") to 28.7655,
Pair("V43", "V41") to 51.8552,
Pair("V43", "V44") to 27.2661,
Pair("V60", "V42") to 51.8552,
Pair("V44", "V21") to 27.2661,
Pair("V44", "V45") to 45.5789,
Pair("V45", "V46") to 50.2140,
Pair("V45", "V47") to 33.0338,
Pair("V46", "V22") to 21.4964,
Pair("V46", "V50") to 33.0617,
Pair("V46", "V47") to 61.1926,
Pair("V47", "V48") to 60.9859,
Pair("V48", "V50") to 21.2982,
Pair("V48", "V49") to 37.9029,
Pair("V49", "V51") to 12.5367,
Pair("V50", "V53") to 29.7003,
Pair("V53", "V27") to 51.0339,
Pair("V53", "V52") to 74.1635,
Pair("V52", "V54") to 24.0134,
Pair("V54", "V55") to 45.0589,
Pair("V54", "V29") to 31.0768,
)
val reverseWeights = weights.map { (key, value) ->
Pair(key.second, key.first) to value
}.toMap()
val mergeTheWeights = weights + reverseWeights
// variable dibawah ini adalah lokasi awal pengguna
val start = "V4"
// variable dibawah ini adalah lokasi evakuasi yang akan dituju
// V8
// V21
// V29
val end = "V21"
val shortestPathTree = dijkstra(Graph(mergeTheWeights), start)
println(shortestPath(shortestPathTree, start, end))
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment