Breadth First Directed Paths Algorithm

The Breadth First Directed Paths (BFDP) Algorithm is an efficient graph traversal technique used to find the shortest paths between two vertices in a directed graph. It is based on the Breadth-First Search (BFS) algorithm, which explores the graph in layers, starting from the source vertex and moving outwards. In each iteration, the BFDP algorithm visits all the vertices at the current level, and then moves on to the vertices at the next level. This ensures that the first time the destination vertex is encountered, the algorithm has found the shortest path. To implement the BFDP algorithm, a queue is used to store the vertices to be explored next. Initially, the source vertex is enqueued. Then, while the queue is not empty, the algorithm dequeues the next vertex, explores its unvisited neighbors, and enqueues them in the queue. During this process, for each visited vertex, the algorithm keeps track of the previous vertex in the shortest path leading to it. This information is later used to reconstruct the shortest path once the destination vertex is found. The BFDP algorithm is guaranteed to find the shortest path as long as the graph does not have cycles with negative weights.
package org.gs.digraph

import scala.annotation.tailrec
import scala.collection.mutable.Queue

/** Find shortest path from source vertex
  *
  * @constructor creates a new BreadthFirstDirectedPaths with a digraph and source vertex
  * @param g Digraph
  * @param s a single source vertex
  * @see [[https://algs4.cs.princeton.edu/42directed/BreadthFirstDirectedPaths.java.html]]
  * @author Scala translation by Gary Struthers from Java by Robert Sedgewick and Kevin Wayne.
  */
class BreadthFirstDirectedPaths(g: Digraph, s: Int) {
  private val marked = new Array[Boolean](g.numV)
  private val edgeTo = new Array[Int](g.numV)
  private val _distTo = Array.fill[Int](g.numV)(Int.MaxValue)

  private def bfs(s: Int) {
    val q = new Queue[Int]()
    marked(s) = true
    _distTo(s) = 0
    q.enqueue(s)

    @tailrec
    def loopQ(): Unit = {
      if (!q.isEmpty) {
        val v = q.dequeue
        g.adj(v) foreach(w => if (!marked(w)) {
            edgeTo(w) = v
            _distTo(w) = _distTo(v) + 1
            marked(w) = true
            q.enqueue(w)
          })
        loopQ()
      }
    }

    loopQ()
  }
  bfs(s)

  /** returns if there is a path from s to v */
  def hasPathTo(v: Int): Boolean = marked(v)

  /** returns number of edges in shortest path from s to v */
  def distTo(v: Int): Int = _distTo(v)

  /** returns the path from s to v */
  def pathTo(v: Int): List[Int] = {
    @tailrec
    def loop(x: Int, xs: List[Int]): List[Int] = if (_distTo(x) == 0) x :: xs else loop(edgeTo(x), x :: xs)

    loop(v, List[Int]())
  }
}

LANGUAGE:

DARK MODE: