package kapitel_10

/**
 * Beispiel aus
 *
 * - Algorithmen und Datenstrukturen für Dummies
 *   - von Andreas Gogol-Döring und Thomas Letschert
 *   - Verlag Wiley-VCH; Oktober 2019
 *  - Kapitel 10, Verbindungen finden
 *
 * @author A. Gogol-Döring, Th. Letschert
 */

object AuD_10_03_Dijkstra_App extends App {

  /*
   * Dijkstras Algorithmus ist eine Optimierung des Algorithmus zum Auffinden aller kürzsten Pfade.
   */

  def neighbors(s: String, E: List[(String, String)]): List[String] =
    for((x, y) <- E
        if x == s) yield y

  def dijkstra(s: String,
               E: List[(String, String)],
               w: Map[(String, String), Int]): Map[String, (Int, List[String])] = {

    var S: List[String] = s :: Nil
    var T: List[String] = neighbors(s, E)
    var SP: Map[String, (Int, List[String])] = Map(s -> (0, List(s)))

    for (n <- neighbors(s, E)) {
      SP = SP + (n -> (w(s, n), List(s, n)))
    }

    while ( T.nonEmpty ) {
      // choose u in T with minimal SP
      val u = T.minBy( v => SP(v)._1)
      // move u from T to S
      S = u :: S
      T = T.filter( _ != u)
      for (n <- neighbors(u, E)) {
        if (T.contains(n)) { // node is known, update?
          val d: Int = SP(u)._1 + w((u, n))
          if (d < SP(n)._1) {
            SP = SP + (n -> (d, SP(u)._2 ++ List(n)))
          }
        } else if (!S.contains(n)) { // not in S not in T, new node
          SP = SP + (n -> (SP(u)._1 + w((u, n)), SP(u)._2 ++ List(n)))
          T = n :: T
        }
      }
    }
    SP
  }

  val V = List("a", "b", "c", "d", "e")

  val w = Map[(String, String), Int](
    ("d", "b") -> 2,
    ("b", "a") -> 3,
    ("b", "c") -> 4,
    ("e", "d") -> 4,
    ("d", "c") -> 5,
    ("c", "e") -> 6,
    ("a", "d") -> 7
  )

  val E = w.keySet.toList

  dijkstra("a", E, w).foreach {
    case (dest, (len, path)) => println(s"a -> $dest = $len, path = ${path.mkString(",")}")
  }

}