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
DFS(v):
v.fresh = false
for all the neighbors e of v:
if e.fresh:
DFS(e)
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
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 queue:
void add(item) to add an item to the instance queueitem get() to return and remove the current top priority from the instance queue.
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.
Using Arrays
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.
Using Heaps
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 add() and 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 add() and 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.
