Last active
November 11, 2021 22:14
-
-
Save pun-ky/67ee26c848eac6b173fba5187ff755d6 to your computer and use it in GitHub Desktop.
Dijkstra - Finding Shortest Path
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| /* | |
| https://www.youtube.com/watch?v=EFg3u_E6eHU | |
| Found path: | |
| A -> C -> E -> B | |
| Graph: | |
| [A(0), B(6), C(3), D(7), E(4), F(2), G(7)] | |
| */ | |
| fun main() { | |
| val a = Node("A") | |
| val b = Node("B") | |
| val c = Node("C") | |
| val d = Node("D") | |
| val e = Node("E") | |
| val f = Node("F") | |
| val g = Node("G") | |
| a.adjacent(c, 3) | |
| a.adjacent(f, 2) | |
| b.adjacent(g, 2) | |
| b.adjacent(f, 6) | |
| b.adjacent(e, 2) | |
| b.adjacent(d, 1) | |
| c.adjacent(a, 3) | |
| c.adjacent(f, 2) | |
| c.adjacent(e, 1) | |
| c.adjacent(d, 4) | |
| d.adjacent(c, 4) | |
| d.adjacent(b, 1) | |
| e.adjacent(c, 1) | |
| e.adjacent(f, 3) | |
| e.adjacent(b, 2) | |
| f.adjacent(a, 2) | |
| f.adjacent(c, 2) | |
| f.adjacent(e, 3) | |
| f.adjacent(b, 6) | |
| f.adjacent(g, 5) | |
| g.adjacent(f, 5) | |
| g.adjacent(b, 2) | |
| val graph = Graph(listOf(a, b, c, d, e, f, g)) | |
| println("Found path:") | |
| println(graph.findShortestPath(a, b).map { it.name }.joinToString(" -> ")) | |
| println("Graph:") | |
| println(graph) | |
| } | |
| class Node(val name: String) { | |
| val adjacents = mutableListOf<AdjacentNode>() | |
| var pathDistance: Int = 0 | |
| var previous: Node? = null | |
| fun adjacent(node: Node, distance: Int) { | |
| adjacents.add(AdjacentNode(node, distance)) | |
| } | |
| override fun toString() = "$name($pathDistance)" | |
| } | |
| class AdjacentNode(val node: Node, val distance: Int) { | |
| override fun toString() = "->${node.name}=$distance" | |
| } | |
| class Graph(val nodes: List<Node>) { | |
| // find node with minimal distance from source | |
| // review unvisited neightbour nodes and update distances | |
| fun findShortestPath(source: Node, target: Node): List<Node> { | |
| nodes.forEach { it.pathDistance = Int.MAX_VALUE } | |
| source.pathDistance = 0 | |
| val unvisited = nodes.toMutableList() | |
| while (unvisited.isNotEmpty()) { | |
| val current = unvisited.minByOrNull { it.pathDistance } ?: unvisited.first() | |
| unvisited.remove(current) | |
| current.adjacents.forEach { adjacent -> | |
| val newDistance = current.pathDistance + adjacent.distance | |
| if (newDistance < adjacent.node.pathDistance) { | |
| adjacent.node.pathDistance = newDistance | |
| adjacent.node.previous = current | |
| } | |
| } | |
| if (current == target) { | |
| break | |
| } | |
| } | |
| var p: Node? = target | |
| val result = mutableListOf<Node>() | |
| while (p != null) { | |
| result.add(0, p) | |
| p = p.previous | |
| } | |
| return result | |
| } | |
| override fun toString() = nodes.toString() | |
| } |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment