Edge Weighted Digraph Algorithm
The Edge Weighted Digraph Algorithm is an essential technique used in graph theory for finding the shortest paths in a directed graph with weighted edges. This algorithm, often referred to as Dijkstra's algorithm, is widely employed in various applications such as network routing, traffic engineering, social network analysis, and transportation planning. The fundamental idea behind this algorithm is to iteratively explore the vertices of the graph in a greedy manner, updating the shortest path distances based on the edge weights and using a priority queue to determine the next vertex to explore. By maintaining a set of tentative distances for each vertex, the algorithm efficiently identifies the shortest path from a given source vertex to all other vertices in the graph.
To implement the Edge Weighted Digraph Algorithm, one starts by initializing the distance of the source vertex to zero and all other vertices to infinity. A priority queue is then used to store the vertices and their tentative distances, with the source vertex being the first to be explored. Upon exploring a vertex, the algorithm updates the tentative distances of its adjacent vertices if the sum of the current vertex's distance and the edge weight connecting them is less than their existing tentative distance. This process is repeated for all vertices in the priority queue until it becomes empty, at which point the shortest paths have been determined. The efficiency of this algorithm relies on its ability to quickly identify the next vertex to explore, which is facilitated by the use of a priority queue. The time complexity of the Edge Weighted Digraph Algorithm is O(|V|^2) for a dense graph, but can be reduced to O(|V|log|V|) with the help of an efficient priority queue implementation like Fibonacci heaps.
package org.gs.digraph
import org.gs.graph.BaseEdgeWeightedGraph
import scala.collection.mutable.ListBuffer
/** Digraph with edges having direction and weight
*
* @constructor creates a new EdgeWeightedDigraph with a vertex count
* @param v number of vertices
* @see [[https://algs4.cs.princeton.edu/44sp/EdgeWeightedDigraph.java.html]]
* @author Scala translation by Gary Struthers from Java by Robert Sedgewick and Kevin Wayne.
*/
class EdgeWeightedDigraph(v: Int) extends BaseEdgeWeightedGraph[DirectedEdge](v) with DigraphMarker {
/** @constructor creates a deep copy of an EdgeWeightedDigraph */
def this(g: EdgeWeightedDigraph) = {
this(g.numV)
buildADJ(g)
}
/** add directed edge to digraph */
def addEdge(ed: DirectedEdge): Unit = {
val v = ed.from
_adj(v) = ed :: _adj(v)
e += 1//e + 1
}
/** returns all edges in digraph */
def edges(): List[DirectedEdge] = {
val list = for {
vV <- 0 until v
e <- adj(vV)
} yield e
list.toList
}
/** returns number of directed edges from vertex */
def outdegree(v: Int): Int = {
require(rangeGuard(v), s"verticies v:$v not in 0..$v ")
adj(v).size
}
}
