Skip to main content
added 402 characters in body
Source Link
Zephyr
  • 993
  • 3
  • 16
  • 34

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;
}

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?

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;
}
Source Link
Zephyr
  • 993
  • 3
  • 16
  • 34

Shortest Path using DFS on weighted graphs

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?