Gryphon
API
Generated with
Gryphon/com.phasmidsoftware.gryphon/com.phasmidsoftware.gryphon.traverse/AcyclicShortestPaths

AcyclicShortestPaths

com.phasmidsoftware.gryphon.traverse.AcyclicShortestPaths
object AcyclicShortestPaths

Computes shortest paths in a weighted DAG using topological relaxation.

The algorithm:

  1. Topologically sort the DAG.
  2. Relax all outgoing edges of each vertex in topological order.

Since edges are relaxed in topological order, every predecessor of a vertex has already been processed when we reach it — guaranteeing optimal substructure without a priority queue. This gives O(V+E) time and correctly handles negative edge weights (unlike Dijkstra).

The edge-weight type E requires only a Monoid (for the zero distance and addition) and an Ordering (for comparison) — a lighter constraint than Numeric, consistent with RelaxableVertex and WeightedUnionFind.

NOTE: the graph must be a DAG. If it contains a cycle, TopologicalSort.sort returns None and this method throws IllegalArgumentException.

Attributes

Graph
Supertypes
class Object
trait Matchable
class Any
Self type

Members list

Value members

Concrete methods

def shortestPaths[V, E : Monoid : Ordering](graph: DirectedGraph[V, E], start: V): VertexTraversalResult[V, DirectedEdge[V, E]]

Computes shortest paths from start to all reachable vertices in graph.

Computes shortest paths from start to all reachable vertices in graph.

Type parameters

E

the edge-weight type; must have Monoid (zero + combine) and Ordering.

V

the vertex type.

Value parameters

graph

the directed acyclic graph.

start

the source vertex.

Attributes

Returns

a VertexTraversalResult[V, DirectedEdge[V, E]] mapping each reachable vertex (except start) to its shortest-path incoming edge.

Throws
IllegalArgumentException

if the graph contains a cycle.

Generated with