0

I have a directed graph, with source and target. every edge is weighted on weight of 1. The nodes have no weight. I need to find an efficient way(I write on C#, but I don't think it is relevant), to find ALL the paths from the source to target, that the weight of the path(or the number of edges , which is the same with those details) be less or equal to a certain value, let's call it K.

A possible way I thought is to run Dijkstra on every value from 1 to K, but since K can be very big it won't be efficient. I have been looking on some answers, but also there was a very similar question to mine, I didn't find this answer as helpfully.

(Find all simple path from node A to node B in direct weighted graph with the sum of weighs less a certain value?)

Alon H
  • 33
  • 9
  • There can be an exponential number of paths, so "finding" "ALL" of them cannot be called "efficient". If you explain why you think you want to do this, maybe we can offer an efficient way to accomplish your real goal. – Matt Timmermans Oct 30 '19 at 03:26
  • Eventually I am getting circle of logic gates between 2 registers, and I need to return all the paths from one register to another that are equal or minus than some K. – Alon H Oct 30 '19 at 06:30

1 Answers1

0

You can simply run a DFS from the source to the target to analyze all paths. If you have to find number of paths you stop when you reach depth K returning 0 and when you reach the target returning 1 and if you need to describe the paths as well you can build a tree while exploring with the DFS. Complexity will be O(E) where E is the number of edges

Here a mixture of python and pseudo code:

def DFS(node, depth, target, visited, graph, max_depth):
  visited.add(node)
  if depth >= max_depth:
    return Null
  elif node == target:
    return new_tree_node(node)
  else:
    sub_trees = list()
    for connected_node in graph[node]:
      if connected_node not in visited:
        sub_tree = DFS(connected_node, depth+1, target, visited, graph, max_depth)
        if sub_tree != Null:
          sub_trees.append(sub_tree)

    if length(sub_trees) > 0:
      tree_node = new_tree_node(node)
      for sub_tree in sub_trees:
         tree_node.add_child(sub_tree)
      return tree_node
    else:
      return Null

tree = DFS(source, 0, target, set(), graph, K)

PS: this solution could easily be adapted to weighted graph as well

Marco Zamboni
  • 224
  • 1
  • 9
  • @beaker the solution is already adapted to the requirements. He said that every edge has a weight of 1 and he consider the weight as the number of edges. Then can you please tell me which paths are not covered? – Marco Zamboni Oct 29 '19 at 14:35
  • You're right, I misread the edge weights. My bad. Paths containing cycles would not be found (I don't know if that's a requirement), aside from the fact that this code does not find the actual paths, only the counts. I'm also unsure of your complexity analysis. It seems to me that there could be *O(N)* paths, each containing *O(N)* edges. – beaker Oct 29 '19 at 16:58
  • The complexity I believe should be good enough. I need to think how I would return the path it self, I believe that there are directories of graph algorithms which I can use to do so. – Alon H Oct 29 '19 at 20:32
  • @beaker by definition a path doesn't contain cycles (we would speaking about walks instead) then about the analysis of DFS time complexity you can easily find resources on the internet. In a couple of words is O(E) because every edge is checked at most one time – Marco Zamboni Oct 29 '19 at 21:29
  • @AlonH for having the paths my approach would be to create a tree in this way: when the target is reached create a node and return it, when you surpass K create a Null node and return it, in the other cases if any recursive call has returned a non-Null node create a node, attach all the nodes returned from the children and return it otherwise return a Null node. Tomorrow (in central Europe timezone) I'll update the answer. At first I didn't want to write the code because it would introduce a lot of boilerplate language-depended. Just be sure to accept the answer if it resolve your question ;) – Marco Zamboni Oct 29 '19 at 21:40
  • @marco Zamboni Thanks a lot, of course I will accept it :) – Alon H Oct 30 '19 at 10:49
  • @marco Zamboni I see you updated the code. it take me few days or may be little mpre to check it since I got some other tasks to do. Once I will return to it, I will say to you wether it works and accept your answer. from what I see it looks great, thanks a lot. – Alon H Oct 30 '19 at 18:26