Posted on Feb 17, 2020 • Edited on Jun 12, 2020

Finding Shortest Paths In Graphs (using Dijkstra's & BFS)

#computerscience #algorithms #datastructures #csharp

If you are unfamiliar with graphs a previous post of mine covers the basics of them.

Resources:

Here is a visual overview of weighted vs unweighted shortest paths (for brevity I have used a single graph, but unweighted shortest paths will typically apply to graphs that have no edge weights):

Finding the Shortest Path in Weighted Graphs:

One common way to find the shortest path in a weighted graph is using Dijkstra's Algorithm.
Dijkstra's algorithm finds the shortest path between two vertices in a graph. It can also be used to generate a Shortest Path Tree - which will be the shortest path to all vertices in the graph (from a given source vertex).
Dijkstra's takes into account the weight/cost of the edges in a graph, and returns the the path that has the least weight to it between a source and destination vertex. This can mean the path might actually involve traversing more vertices, but the sum of their edge weights will be lower than alternative paths. It will be the shortest path because the path has the lowest cost to it.
Dijkstra's typically uses a priority queue which is populated with vertices and a priority. The priority represents the cost/weight of getting to that vertex.
At the beginning, the priority of the source/starting vertex is 0 and all other vertices have a priority of infinity (typically represented by a very large number).
While the priority queue has vertices in it, each vertex in the queue will get dequeued. This means for each loop iteration, the vertex with the lowest priority (lowest cost/weight) will get processed.
For each vertex dequeued, Dijkstra's explores all of its adjacent vertices and the edges that connect the dequeued vertex with it's adjacent vertices.
If we have already visited one of the adjacent vertices before, it will be skipped. Otherwise, we will compare the priority of the adjacent vertex with the sum of the edge weight and the priority of the current vertex.
On the first iteration we process the source vertex, which has a priority of 0. All of it's adjacent vertices start with a priority of infinity. So for the first comparison, if source v has a cost of 0, adjacent u has a cost of infinity, and the edge connecting the two has a cost of 50: 0 + 50 < infinity (cost of getting to current v + edge(v, u) < cost of getting to u)
If the cost of getting to the current vertex + the edge cost of getting to an adjacent vertex is less than the previously computed cost (i.e. priority of the adjacent vertex in the queue) then we update the priority of the adjacent vertex in our queue to be the calculated cost/weight (sum of edge weight and priority of current vertex).
This process is often referred to as edge relaxation. First we check if the edge is tense: cost to v + cost of edge(v, u) < cost to u? (v is the current dequeued vertex, u is the adjacent vertex, and edge(u, v) is the edge connecting the two). If the edge is tense, then we relax it by decreasing the priority of u in our queue (setting it to cost to v + cost of edge(v, u)).
Here is a good explanation of edge relaxation. And here is another good explanation.
This means the order in the priority queue can change, and the updated adjacent vertex can move up or down in priority - affecting when it is processed.
After dequeuing all vertices from the priority queue and processing them in this way, we can keep track of a cost per vertex. This cost represents the lowest weight/distance to each vertex.
Similarly, we can keep track of parent vertices. Which will tell us what the parent of a vertex is (i.e given a vertex, we can tell what vertex came before it in the path).
Using these two collections (cost and parents), we can backtrack and detail the shortest path to take from source to destination. And we can tell how much that path costs in total and for each stop along the path (a stop being a vertex).
One way improve the speed of Dijkstra's algorithm is to make it rely on a different type of heap.
Priority queues are typically implemented with a binary heap, and the first versions of Dijkstra's also used these (min-heaps). Min binary heaps are O(log n) when inserting a new item or decreasing the priority of an item.
Priority queues can be implemented with a Fibonacci heap instead.
A Fibonacci heap, for the same operations (insert and decreasing priority), has amortized constant time (O(1)) for both.
As Dijkstra's makes fairly frequent use of these operations, using a priority queue backed by a Fibonacci heap (or just using the Fibonacci heap directly) helps to improve the run time complexity of the algorithm.
A previous post of mine has a more in depth overview of the Fibonacci heap and how it achieves it's performance benefits. I also previously wrote about Priority Queues.
Time complexity of Dijkstra's, for an adjacency list, with a min-heap is O((v + e) log v). Space is O(v). Where v is number of vertices and e is edges. With an adjacency matrix the time & space complexity is O(v^2).
Using a Fibonacci heap improves the complexity to O(e + (v log v)) because for each edge, we have a constant time operation (when decreasing priority).

Finding the Shortest Path in Unweighted Graphs:

For unweighted graphs, or graphs where the edges all have the same weight, finding the shortest path is slightly more straightforward.
We can use Breadth First Search on the graph and terminate it when we have reached our destination vertex.
Breadth first search traverses a graph in such a way, that given a source and destination vertex it will always reach the destination vertex by traversing the least number of edges.
That means the first time we encounter the destination vertex during a breadth first traversal of a graph, we know that the vertices we visited prior represent the shortest path to get there.

Both Dijkstra's algorithm and breadth first search work for both directed and undirected graphs. This means a single implementation of each can be used to find the shortest paths in directed or undirected graphs.

One limitation I encountered when implementing Dijkstra's is that C# does not contain a priority queue implementation in it's standard library. So for one implementation of Dijkstra's I relied on this priority queue implementation (via nuget). But I also implemented Dijkstra's in a less efficient way, using a list as a queue and sorting it on each loop iteration to maintain priority. There were other inefficiencies to the second implementation (without priority queue), and I have detailed the extra run time costs in the code's comments (where the penalties were incurred). Total complexity for this implementation without a priority queue is: O(v^2 log v * e(v)). This is because the sort is O(n log n) for each v and decreasing priority uses List.Find() which is O(n) for each e. There is also an O(n) cost for removing a vertex from the list - but this is not considered as part of the resulting Big O and superseded by the complexity of the sort (Big O only cares about the highest cost operations - but feel free to leave a comment if you think this logic is incorrect).

Below are implementations for finding shortest paths in weighted & unweighted graphs. There are implementations for both adjacency list & adjacency matrix graph representations (note that for adjacency matrix, instead of using a boolean matrix we use an integer matrix. Anything non 0 represents the weight of the edge. 0 means there is no edge):

As always, if you found any errors in this post please let me know!