Acyclic S P Algorithm

The Acyclic Shortest Path (S P) Algorithm is a widely used graph algorithm that is designed to find the shortest path between a source node and all other nodes in a directed, acyclic graph (DAG). A directed graph is one in which edges have a direction, meaning that they can only be traversed in the direction they point. An acyclic graph is one that has no cycles or loops, which ensures that the algorithm will eventually terminate. The Acyclic S P Algorithm is particularly useful in solving various real-world problems, such as scheduling tasks with specific precedence constraints, network routing, and project management applications. The Acyclic S P Algorithm operates by performing a topological sort on the input graph, which orders the nodes in such a way that every edge is directed from an earlier node to a later node. This order ensures that the algorithm will visit each node only once, reducing the time complexity of the algorithm to a linear function of the number of nodes and edges in the graph. Once the topological order is established, the algorithm initializes the distance values for each node, setting the source node's distance to zero and all other nodes' distances to infinity. It then iterates through the nodes in topological order, relaxing each of their edges by updating the distance values of their neighboring nodes if a shorter path is found. Upon completion, the algorithm returns the shortest path distances from the source node to all other nodes in the graph, making it an efficient and effective solution for finding the shortest paths in directed, acyclic graphs.
package org.gs.digraph

import scala.annotation.tailrec
import scala.collection.mutable.ListBuffer

/** Solves for shortest path from a source where edge weights can be positive, negative, or zero
  *
  * Uses [[org.gs.digraph.Topological]] order
  *
  * @constructor creates a new AcyclicSP with a digraph and source vertex
  * @param g acyclic digraph, edges have direction and weight
  * @param s source vertex
  * @see [[https://algs4.cs.princeton.edu/44sp/AcyclicSP.java.html]]
  * @author Scala translation by Gary Struthers from Java by Robert Sedgewick and Kevin Wayne.
  */
class AcyclicSP(g: EdgeWeightedDigraph, s: Int) {
  private val _distTo = Array.fill[Double](g.numV)(Double.PositiveInfinity)
  _distTo(s) = 0.0
  private val edgeTo = Array.fill[Option[DirectedEdge]](g.numV)(None)
  private val topological = new Topological(g)

  topological.order match {
    case None => throw new IllegalArgumentException(s"EdgeWeightedDigraph:$g is not acyclic")
    case Some(x) => for {
      v <- x
      e <- g.adj(v)
    } relax(e)
  }

  private def relax(e: DirectedEdge): Unit = {
    val v = e.from
    val w = e.to
    if (_distTo(w) > _distTo(v) + e.weight) {
      _distTo(w) = _distTo(v) + e.weight
      edgeTo(w) = Some(e)
    }
  }

  /** returns length of shortest path from source to v */
  def distTo(v: Int): Double = _distTo(v)

  /** returns if there is a path from source to v */
  def hasPathTo(v: Int): Boolean = _distTo(v) < Double.PositiveInfinity

  /** returns path from source to v if it exists */
  def pathTo(v: Int): Option[Seq[DirectedEdge]] = {
    if (!hasPathTo(v)) None else {
      val path = new ListBuffer[DirectedEdge]()

      @tailrec
      def loop(e: DirectedEdge) {
        e +=: path
        edgeTo(e.from) match {
          case None =>
          case Some(x) => loop(x)
        }
      }

      edgeTo(v) match {
        case None =>
        case Some(x) => loop(x)
      }
      Some(path.toSeq)
    }
  }
}

LANGUAGE:

DARK MODE: