Simple Single source to all connected nodes (DijkSolver)

Purpose

Given a graph G, a unique source node s, find the shortest path to all reachable nodes.

Algorithm

This solver keeps a heap of arcs reaching from the "finalized label" nodes across the frontier of unlabeled and non-finalized nodes. Each iteration, the minimum cost non-permanently labeled node is permanently labeled, and the outbound arcs are added into the frontier heap.

Potential Improvements:

  • Check for negative costs in the arcs.
  • Implement a method which suffers less from negative costs.
  • Allow for non-integer costs and labels.

    Layered shortest path solver (LayerSPSolver)

    Purpose

    Given a graph G, a unique source node s, and markers on the arcs indicating "active" or "inactive", find the shortest path to all reachable nodes using only "active" arcs.

    Algorithm

    This behaves exactly like the Dijksolver, except that it ignores "inactive" arcs.

    Potential Improvements:

  • Check for negative costs in the arcs.
  • Implement a method which suffers less from negative costs.
  • Allow for non-integer costs and labels.