forked from mburst/dijkstras-algorithm
-
Notifications
You must be signed in to change notification settings - Fork 0
/
Dijkstras.scala
75 lines (65 loc) · 2.32 KB
/
Dijkstras.scala
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
import scala.collection.mutable
object Main extends App {
val graphs = new SimpleGraph[String](
Map(
"A" -> Map("B" -> 7, "C" -> 8),
"B" -> Map("A" -> 7, "F" -> 2),
"C" -> Map("A" -> 8, "G" -> 4, "F" -> 6),
"D" -> Map("F" -> 8),
"E" -> Map("H" -> 1),
"F" -> Map("B" -> 2, "C" -> 6, "D" -> 8, "G" -> 9, "H" -> 1),
"G" -> Map("C" -> 4, "F" -> 9),
"H" -> Map("E" -> 1, "F" -> 3)
)
)
graphs.getShortestPath("A","E")
}
case class SimpleGraph[N](succs: Map[N, Map[N, Int]]) {
def apply(n: N) = succs.getOrElse(n, Map.empty)
def initDistance(point:N) = {
this.succs.foldLeft(Map.empty:Map[N, (Int, Seq[N])]) {
(result, vertex) =>
if (vertex._1 == point) {
result ++ Map(point -> (0,Seq(point)))
} else {
result ++ Map(vertex._1 -> (Int.MaxValue, Seq(point)))
}
}
}
def shortestPath(n:N)(selected:Set[N])(currentDistance:Map[N, (Int, Seq[N])]) = {
currentDistance.keys.filterNot(selected.contains(_)).foldLeft(n:N) {
(result, point) =>
currentDistance(point)._1 match {
case x if result == n => point
case y if (currentDistance(result)._1 > y) => point
case _ => result
}
}
}
def updateGraph(n:N)(f:N)(distance:Map[N, (Int, Seq[N])]):Map[N, (Int, Seq[N])] = {
val hereDistance = distance(f)
this.succs(f).foldLeft(distance:Map[N, (Int, Seq[N])]) {
(result, vertex) =>
val nodeDistance = hereDistance._1 match {
case Int.MaxValue => vertex._2
case _ => hereDistance._1 + vertex._2
}
if (distance(vertex._1)._1 > nodeDistance) {
result ++ Map(vertex._1 -> (nodeDistance, hereDistance._2 :+ vertex._1))
} else {
result
}
}
}
def getShortestPath(start: N, finish: N) = {
var nextNode:N = start;
var currentDistance:Map[N, (Int, Seq[N])] = initDistance(start);
var unreachedVertexSet:Set[N] = succs.keySet.filterNot(_ == start)
while (!unreachedVertexSet.isEmpty) {
currentDistance = updateGraph(start)(nextNode)(currentDistance)
nextNode = shortestPath(start)(succs.keySet.filterNot(unreachedVertexSet.contains(_)))(currentDistance)
unreachedVertexSet = unreachedVertexSet.-(nextNode)
}
println(currentDistance(finish)._2.reverse.toSeq)
}
}