DAGRelaxer

java.lang.Object

dsa.lab11.solutions.DAGRelaxer

public class DAGRelaxer extends Object

Constructor Summary

Constructors

Constructor

Description

DAGRelaxer()
Method Summary

Modifier and Type

Method

Description

static <Vertex> Map<Vertex,Path<Vertex,Double>>

relaxDAG(DirectedGraph<Vertex,Double> dag, Vertex source)

Find the shortest (weighted) paths to each of the vertices reachable from the given source vertex in the given directed acyclic graph (DAG).

Methods inherited from class java.lang.Object
clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Constructor Details
- DAGRelaxer
  
  public DAGRelaxer()
Method Details
- relaxDAG
  
  public static <Vertex> Map<Vertex,Path<Vertex,Double>> relaxDAG(DirectedGraph<Vertex,Double> dag, Vertex source)
  
  Find the shortest (weighted) paths to each of the vertices reachable from the given source vertex in the given directed acyclic graph (DAG).
  The weighted distance between two vertices is the sum of the path's edges' weights. Here we consider only weights that are doubles (e.g. 8.2).
  
  Type Parameters:
  
  Vertex - the vertex type
  
  Parameters:
  
  dag - the directed acyclic graph
  
  source - the source vertex
  
  Returns:
  
  the shortest (weighted) paths to each reachable vertex and their (weighted) distances