0
$\begingroup$

I read that shortest path using DFS is not possible on a weighted graph. I pretty much understood the reason of why we can't apply on DFS for shortest path using this example:- enter image description here

Here if we follow greedy approach then DFS can take path A-B-C and we will not get shortest path from A-C with traditional DFS algorithm.

I think that we can modify DFS slightly in this way to get shortest path.In this example, after the DFS goes through A-B-C and comes back again to A, we can check all adjacent nodes and if the distance from A to any of the adjacent node is less than the distance which was assigned previously(i.e 2<4) then we visit the node again even if the node is visited again before and continue the DFS from this node (like visiting C again). If we do this way, ofcourse the complexity will be bad but I don't think that its impossible to get shortest path using DFS. Is this the right approach?

Initially we have cost array initialized to infinity except for source vertex which is initialized to 0. dist(u,v) denotes edge weight from vertex u to vertex v.

function spath(vertex u)
{
  for each(vertex v adjacent to u)
   {
      if(cost[u] + dist(u,v) < cost[v])
       {
          cost[v]=cost[u]+dist(u,v);
          parent[v]=u;
          spath(v);
       }
   }
  return;
}
$\endgroup$
  • 1
    $\begingroup$ Now that you have pseudocode, you can try proving that it works. The next step would be estimating its running time. $\endgroup$ – Yuval Filmus Sep 3 '17 at 15:22
  • $\begingroup$ I know that its run time is pretty bad. I just want to know if this pseudo code will work or not. According to me it should work. $\endgroup$ – Zephyr Sep 3 '17 at 15:24
  • 1
    $\begingroup$ Have you tried proving that it works? That's how we know if things are true or not in math. $\endgroup$ – Yuval Filmus Sep 3 '17 at 15:53
  • $\begingroup$ I am not that good at rigorous proofs, so I tried disproving it but I am not able to find an example . Can you please give me an example where the above pseudo code fails ? $\endgroup$ – Zephyr Sep 3 '17 at 15:58
  • $\begingroup$ Just a pointer, but maybe you'd like to know more about repeated relaxation and Bellman-Ford. $\endgroup$ – BearAqua Jun 13 at 14:55

Your Answer

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

Browse other questions tagged or ask your own question.