Shortest path with a base line Dijkstra implementation #44
Description
Within our graph framework tinygraph we want to support single-source shortest path queries.
We already made some progress on the foundations for that
- Adds depth-first search and breadth-first search #40 explores graph searches depth-first and breadth-first searches
- Adds a binary min-heap to be used as a priority queue in graph searches #43 adds a min-heap we can use as priority queue
The next logical step is to implement a Dijkstra based graph search. This ticket captures ideas and the design space.
Binary Hin-Heap vs DecreaseKey
In textbook Dijkstra when relaxing edges there is a need for an operation often times called "decreaseKey". This operation decreases the priority of an item that is already in the heap. Our binary min-heap does not natively support this operation efficiently.
Two options
- We make our binary min-heap addressable, by additionally storing the positions of items in the heap, or
- Instead of using the decreaseKey operation, we always add a new item to the heap. Then when we pop an item from the heap, we first need to check if we have visited it already and in this case discard it. This way of implementing Dijkstra is often called "lazy delete".
Graph Preconditions
For Dijkstra to work, we'll need to make sure our graph conforms to a few preconditions
- We have non-negative weights
- No zero-weight loops / self-loops
- Parallel edges with different weights: pick the minimum weight
We need to take this into account when designing the API and see what we should check internally and what we can assert and make the user's responsibility. For example parallel edges should work as is without problems I believe.
API Design
There are decisions we need to take in the design space of our single-source shortest path search implemented with Dijkstra's algorithm.
- Do we support an API allowing for (s, t)-distance queries?
- Do we support an API allowing for s-to-all distance queries?
- Do we always want to return the shortest path consisting of an array of vertices or just the total distance?
- Do we want to follow the dfs/bfs searchers and provide a search context users can step through?
Maybe the easiest way to get started would be providing a very simple (s, t) shortest-path API always returning the total distance and the path of vertices and make sure we call it something like tinygraph_dijkstra_simple(graph, s, t). And in the future if we want to extend this we can always add more complex APIs. What could make sense is still building around a ctx struct that caches memory for the heap, the visited bitmask, and the reconstructed path.