0
$\begingroup$

I am sorry for the repetition of the question. I understand that this question has already been answered before by the community, but most answers tend to focus on unweighted graphs. I want to know Can DFS we used to find the shortest path for weighted graphs? I know that Dijkstra's algorithm is used to find the shortest path for weighted graphs. But, what I want to know is what is fundamentally different in using DFS for unweighted graphs compared to Dijkstra (which is BFS + priority queue/set) and why can't we create DFS + priority queue/set implementation for shortest path problem?

Ref link: Shortest Path using DFS on weighted graphs, Why can't DFS be used to find shortest paths in unweighted graphs?

Any help would be really appreciated. Thanks!

$\endgroup$
  • 1
    $\begingroup$ Every unweighted graph is also a weighted graph (just set all the weights equal to 1). Clearly, if DFS cannot find shortest paths in unweighted graphs it also cannot find shortest paths in weighted graphs. $\endgroup$ – Tom van der Zanden Sep 6 at 19:26
  • $\begingroup$ What would a "Dfs + priority queue" be? DFS is characterized by the use of a stack (I.e. making a choice from the last vertex chosen) otherwise, it's not a dfs $\endgroup$ – JimN Sep 6 at 21:55
  • $\begingroup$ I simply meant that when we put something in the stack or making a recursive call we do it as per some criteria or heuristic. $\endgroup$ – sarthak tripathi Oct 19 at 20:53
0
$\begingroup$

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 queue
  • item 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.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ (visiting the unseen vertices would seem the way of traversals. I'm confident I could code breadth first using recursive calls.)(I consider it pointless to specify a logarithm base in "Big-O notation".) $\endgroup$ – greybeard Sep 7 at 14:15
  • $\begingroup$ Welcome to COMPUTERSCIENCE @SE. $\endgroup$ – greybeard Sep 7 at 14:15
  • $\begingroup$ Thanks, @greybeard! I've updated the answer accordingly. $\endgroup$ – 0x0584 Sep 8 at 17:35
  • $\begingroup$ Got it thanks! @0x0584 $\endgroup$ – sarthak tripathi Nov 21 at 19:50

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.