Edge Weighted Graph Algorithm
The Edge Weighted Graph Algorithm is a computational technique used to analyze and solve problems in graphs where edges have assigned weights, representing various quantities such as distances, costs, or capacities. These algorithms are widely used in various applications, including network design, transportation, and logistics, where the goal is often to optimize a specific objective function. The key concept behind the Edge Weighted Graph Algorithm is to model the relationships between nodes in a graph by associating weights with the edges connecting them. This allows for the identification of shortest paths, minimum spanning trees, and other optimal solutions based on the edge weights.
There are several well-known edge-weighted graph algorithms, such as Dijkstra's shortest path algorithm, Kruskal's minimum spanning tree algorithm, and the Floyd-Warshall all-pairs shortest path algorithm. These algorithms often involve iterative processes where the edge weights are used to calculate and update the solutions. For example, Dijkstra's algorithm starts with a source node and iteratively updates the shortest path distances from the source to all other nodes in the graph by considering the edge weights between the nodes. Similarly, Kruskal's algorithm incrementally constructs a minimum spanning tree by selecting and adding the edges with the smallest weights that do not form a cycle. In all these edge-weighted graph algorithms, the edge weights play a crucial role in determining the final solution, allowing for more accurate and efficient analysis of the problem at hand.
package org.gs.graph
import scala.collection.mutable.ListBuffer
/** Graph where edges have real values as weights.
*
* @constructor creates a new EdgeWeightedGraph with vertex count
* @param v number of vertices
* @see [[https://algs4.cs.princeton.edu/43mst/EdgeWeightedGraph.java.html]]
* @author Scala translation by Gary Struthers from Java by Robert Sedgewick and Kevin Wayne.
*/
class EdgeWeightedGraph(v: Int) extends BaseEdgeWeightedGraph[Edge](v) {
/** @constructor makes a deep copy of g */
def this(g: EdgeWeightedGraph) = {
this(g.numV)
buildADJ(g)
}
/** @param ed add Edge to graph */
def addEdge(ed: Edge): Unit = {
val either = ed.either
val other = ed.other(either)
require(rangeGuard(either) && rangeGuard(other), s"verticies either:$either w:$other not in 0..$v ")
_adj(either) = ed :: _adj(either)
_adj(other) = ed :: _adj(other)
e += 1
}
/** returns edges in graph */
def edges(): List[Edge] = {
val list = ListBuffer[Edge]()
def addEdgesAndSelfLoops(v: Int) {
var selfLoops = 0
def addEdges(edg: Edge) = {
if(edg.other(v) > v) list prepend (edg) else if (edg.other(v) == v) {
if (selfLoops % 2 == 0) list prepend (edg)
selfLoops += 1
}
}
adj(v) foreach (ed => addEdges(ed))
}
for(vV <- 0 until v) addEdgesAndSelfLoops(vV)
list.toList
}
}
