Single-Source Shortest Path Problem

Getting Started

Running Tests

To run all tests:

dotnet test

To run tests for a specific project:

dotnet test tests/SSSPP.Graph.Tests/SSSPP.Graph.Tests.csproj

Running Benchmarks

To run the performance benchmarks:

dotnet run -c Release --project benchmarks/SSSPP.Graph.Benchmark/SSSPP.Graph.Benchmark.csproj

The benchmark results will be saved in the BenchmarkDotNet.Artifacts/results/ directory.

Note: Benchmarks must be run in Release mode (-c Release) for accurate performance measurements.

---

1. Graph Representation

1. Adjacency List

Description: Each vertex maintains a list of all adjacent (connected) vertices. Often implemented as an array (or map) of lists.

Advantages:

• Efficient for sparse graphs (few edges).
• Easy to iterate over neighbors of a vertex.
• Space-saving when the number of edges is much less than ( V^2 ).

Disadvantages:

• Checking if two vertices are connected can take O(deg(V)) time (not constant).
• Slightly more complex structure to implement.

Memory Complexity:

• O(V + E) where ( V ) is number of vertices and ( E ) is number of edges.

---

2. Adjacency Matrix

Description: A 2D array (matrix) of size ( V \times V ) where entry ([i][j]) is 1 (or weight) if there is an edge from vertex ( i ) to ( j ), otherwise 0.

Advantages:

• Constant-time O(1) edge lookup and update.
• Good for dense graphs (many edges).
• Easy representation for matrix-based algorithms (e.g., Floyd–Warshall).

Disadvantages:

• Consumes a lot of memory for sparse graphs.
• Iterating over all neighbors of a vertex takes O(V) time.

Memory Complexity:

• O(V²) regardless of the number of edges.

---

3. Edge List

Description: A list of all edges, each represented as a pair (or triplet for weighted graphs) ( (u, v [, w]) ).

Advantages:

• Simplest representation.
• Very memory efficient if only edge relationships matter.
• Convenient for algorithms like Kruskal’s (which need edge sorting).

Disadvantages:

• Finding neighbors or checking adjacency is O(E).
• Not efficient for traversal-based algorithms (e.g., BFS, DFS).

Memory Complexity:

• O(E).

---

Summary Table

Representation	Edge Lookup	Neighbor Iteration	Best For	Space Complexity
Adjacency List	O(deg(V))	O(deg(V))	Sparse graphs	O(V + E)
Adjacency Matrix	O(1)	O(V)	Dense graphs	O(V²)
Edge List	O(E)	O(E)	Simple storage	O(E)

---

2. Brute-Force Implementation

Both approaches defined in ShortestPath

3. Optimized Dijkstra’s Algorithm using Binary Heap

Standard libraries omit decreaseKey because:

1. Complex to implement efficiently - requires auxiliary data structures
2. The workaround is good enough - inserting duplicates performs well in practice
3. Simplicity over specialization - general-purpose design wins

Classical Dijkstra uses decreaseKey, but modern implementations use "lazy deletion" (duplicate insertions) instead.

Performance Reality

Scenario	DecreaseKey	Lazy Deletion
Sparse graphs	O((V+E) log V)	O((V+E) log E) ≈ O((V+E) log V)
Dense graphs	Better theory	Competitive practice
Cache locality	Worse	Better
Code simplicity	Complex	Simple
Real-world speed	Slower	Often faster

4. Alternative Data Structures

Bucket Queue Implementation (Dial's Algorithm)

As an alternative to the binary heap, I've implemented Dijkstra's algorithm using a Bucket Queue (also known as Dial's Algorithm).

Key Differences

Binary Heap (PriorityQueue):

• Time Complexity: O((V + E) log V)
• Space Complexity: O(V)
• Works with any numeric weights
• General-purpose solution

Bucket Queue:

• Time Complexity: O(V + E + W) where W is the maximum distance
• Space Complexity: O(V + W)
• Optimized for small integer weights
• Can achieve O(V + E) when W = O(V)