TL;DR Depth First Search
I believe that Depth First search traverses the graph by recursively visiting the unseen vertices of the current vertex until they're exhausted.
for all vertices fresh = true
v.fresh = false
for all the neighbors e of v:
Now, weight on the other hand, is a restriction imposed on edges. Hence, the usage of Breadth First Search becomes handy. Because we traverse the graph based on layers or levels, where we're checking all the edges at a certain vertex.
Dijkstra's algorithm is pretty much tricky. You seen, the original paper does specify how prioritize to vertices based on the sum of the weight for each reached vertex.
But more importantly, it does not specify how to fulfill such a task. Indeed, the whole time complexity is dependent on the complexity of how we're prioritizing the vertices.
Prioritizing the vertices
Consider an abstract data type
PriorityQueue, where it supports the following operations for an instance
void add(item) to add an item to the instance
item get() to return and remove the current top priority from the instance
Many data structures provide these elementary operations. But the bottleneck of the algorithm is to update the vertex's priority in case it was reached from a less weighted edge.
Consider an operation
update(item,value) that reset the priority of the
item to a certain
value. There are many ways to extend
PriorityQueue but all of them have different complexities.
Arrays are finite contiguous chunks of memory, so we have
- $O(1)$ to
add() any item at the end, $O(n)$, otherwise since it involves swapping.
- $O(n)$ to
get() the current priority because we traverse the whole array.
- $O(n)$ to
update() any item for the same reason.
Heaps are arrays that have a binary tree property, called the heap invariant which states the following
Every node is less than it's children (in the case of a MinHeap)
This provides $O(\log_2 n)$ to both
get() an item. But it costs $O(n)$ to
update() any item's priority (since there is no order imposed on the children).
Using Binary Search Trees (Balanced)
It has the same costs as the heap does for both to
get() an item. But instead of $O(n)$ to
update(), we have $O(\log_2 n)$. Since searching throughout the whole tree is logarethmic due to the following properties
Every node is greater than its left
Every node is less than or equals its right
Using Fibonacci heaps
Fibonacci heaps are an advanced data structure that is a forest of MinHeap trees.