Digraph Algorithm

The Dijkstra's Algorithm, also known as the Shortest Path First (SPF) Algorithm, is a graph traversal technique commonly used in computer science and network routing to find the shortest path between a starting node and all other nodes in a weighted graph. Invented by the Dutch computer scientist Edsger W. Dijkstra in 1956, the algorithm is highly efficient and widely applied in various fields such as telecommunications, transportation, and social networks to optimize route planning and resource allocation. It works by iteratively selecting the node with the least total cost from the starting node and updating the costs of its neighboring nodes based on the newly explored path. This process is repeated until all nodes have been visited or the shortest path to the target node has been determined. Dijkstra's Algorithm is a greedy algorithm, in the sense that it makes the best local choice at each step, believing that these choices will lead to the globally optimal solution. The algorithm begins by initializing a cost array, where the cost of reaching the starting node is set to zero, and the cost of reaching all other nodes is set to infinity. It then iteratively selects the node with the lowest cost that has not yet been visited and updates the costs of its neighbors. If the new path cost through the current node is less than the previously known cost to reach the neighbor, the cost is updated, and the current node is recorded as the optimal predecessor for that neighbor. Once all nodes have been visited or the target node's cost has been determined, the algorithm terminates. The shortest path can be reconstructed by traversing the recorded predecessors from the target node back to the starting node.
package org.gs.digraph

import org.gs.graph.BaseGraph

/** [[org.gs.digraph.EdgeWeightedDigraph]], [[org.gs.digraph.Topological]] use this to tell a
 *  [[org.gs.graph.Graph]] from a [[org.gs.digraph.Digraph]]
 */
trait DigraphMarker

/** Directed Graph
  *
  * @constructor creates a new Digraph with a number of vertices
  * @param v number of vertices
  * @see [[https://algs4.cs.princeton.edu/42directed/Digraph.java.html]]
  * @author Scala translation by Gary Struthers from Java by Robert Sedgewick and Kevin Wayne.
  */
class Digraph(v: Int) extends BaseGraph(v) with DigraphMarker {

  /** returns a reverse order copy */
  def reverse(): Digraph = {
    val r = new Digraph(v)
    for {
      newV <- 0 until v
      w <- adj(newV)
    } r.addEdge(w, newV)
    r
  }
}

LANGUAGE:

DARK MODE: