Skip to content

Instantly share code, notes, and snippets.

@nebuta
Created March 11, 2013 07:25
Show Gist options
  • Save nebuta/5132521 to your computer and use it in GitHub Desktop.
Save nebuta/5132521 to your computer and use it in GitHub Desktop.
Dijkstra's algorithm in Scala
/**
* Created with IntelliJ IDEA.
* User: hiroyuki
* Date: 3/10/13
* Time: 8:34 PM
* To change this template use File | Settings | File Templates.
*/
import scala.collection.mutable.Set
import scala.collection.mutable.ArrayBuffer
case class Edge(a: Int, b: Int, d: Int)
object Main {
val questions = (1 to 200).toArray
val answers = new ArrayBuffer[(Int,Int)]
val X: Array[Boolean] = Array.tabulate(201)(_ => false)
def main(args: Array[String]){
X(1)= true
val A = Array.tabulate(201)(_ => 0)
val E = readEdges()
for(_ <- 1 until 200){
val dist: ArrayBuffer[(Int,Int)] = new ArrayBuffer[(Int,Int)]
E.foreach(e => {
if(X(e.a) && !X(e.b)){ //If edge (e.a,e.b) crosses between X and V-X
dist += ((e.b, A(e.a) + e.d))
}else if(X(e.b) && !X(e.a)){ //If edge (e.b,e.a) crosses between X and V-X
// println(e)
dist += ((e.a,A(e.b) + e.d))
}
})
//println(dist.mkString)
val selected = dist.minBy(_._2)
X(selected._1) = true
A(selected._1) = selected._2
if(questions.contains(selected._1)){
answers += ((selected._1,A(selected._1)))
}
// println(X.filter((b:Boolean) => {b}).length)
}
answers.sortBy(_._1).foreach(t => {
printf("%d,",t._2)
})
}
def readEdges(): Array[Edge] = {
val s = scala.io.Source.fromFile("dijkstraData.txt")
val arr = new ArrayBuffer[Edge]
for(line <- s.getLines){
val token = line.split('\t')
val a = token.head.toInt
token.tail.map(str => {
val s = str.split(",")
val b = s(0).toInt
if(a < b){
arr += Edge(a,b,s(1).toInt)
}
})
}
arr.toArray
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment