illegitimis / sedgewickwayne.algorithms Goto Github PK

Graphs
MST (Kruskal)

• lazy prim mst
• eager prim mst
• review docs

Port existing code to net60, net50, netstandard21, netstandard20.
Also net471 and net48.
Migrate csproj to the new package reference format.
The current version of the package is net471.
Skip net472 and support 4.71 and 4.8.
See Supported target frameworks

BoruvkaMST
4.3 Minimum Spanning Trees
4 graphs
Chazelle?

4.4 Shortest Paths
DirectedEdge.java
EdgeWeightedDigraph.java implements the API using the adjacency-lists representation.
DijkstraSP.java is an efficient implementation of Dijkstra's algorithm. It uses IndexMinPQ.java for the priority queue.
CPM.java is an implementation of the critical path method.
The algorithm for Acyclic edge-weighted digraphs combines vertex relaxation with topological sorting.
AcyclicSP.java is an implementation of this approach.
It relies on this version of Topological.java, extended to support edge-weighted digraphs.
Queue-based Bellman-Ford algorithm.
BellmanFordSP.java implements this approach by maintaining two additional data structures:
A queue of vertices to be relaxed, A vertex-index boolean array that indicates which vertices are on the queue, to avoid duplicates.