CODEWITHSUNDEEP
pythonalgorithmnodesgraph-theoryedges
polarbits
polarbits

Reputation: 197

Find a path in a directed graph with a given length, allowing for loops and negative lengths

I have a directed graph with a maximum of 7 nodes. Every node is connected to every other node (not including itself of course) with a directed edge, and edges can have either positive or negative weights. My objective is to find a path from one given node to another, such that the path has a specific length. However, there's a catch. Not only can I make use of loops, if I reach the end node, the path doesn't have to immediately end. This means that I can have a simple path leading to the end node, and then have a loop out of the end node leading back into itself that ultimately. At the same time, I have to maximize the number of unique nodes visited by this path, so that if there are multiple paths of the desired length, I get the one with the most nodes in it.

Besides the problem with loops, I'm having trouble rephrasing this in terms of other simpler problems, like maybe Shortest Path, or Traveling Salesman. I'm not sure how to start tackling this problem. I had an idea of finding all simple paths and all loops, and recursively take combinations of each, but this brings up problems of loops within loops. Is there a more efficient approach to this problem?

Btw, I'm writing this in python.

EDIT: Another thing I forgot to mention that pairs of directed edges between nodes need not necessarily have the same weight. So A -> B might have weight -1, but B -> A might have weight 9.

EDIT 2: As requested, here's the input and output: I'm given the graph, the starting and exit nodes, and the desired length, and I return the path of desired length with the most visited nodes.

Upvotes: 0

Views: 853

Answers (1)

Shine
Shine

Reputation: 588

Sounds like a combinations problem. Since you don't have a fixed end state.

Let's list what we know.

  • Every node is connected to every other node, though it is directed. This is a complete digraph. Link: https://en.wikipedia.org/wiki/Complete_graph.
  • You can cut off the algorithm when it exceeds the desired distance.
  • Be careful of an infinite loop though; possible if the negative weights are able to equal the positive ones.

In this example, I'd use recursion with a maximum depth that is based on the total number of nodes. While I won't do your homework I'll attempt a pseudo-code start. 

def recursion(depth, graph, path, previous_node, score, results):
    // 1A. Return if max depth exceeded
    // 1B. Return if score exceeded 
    // 1C. Return if score match AND append path to results

    // 2. iterate and recurse through graph:
    for node in graph:
        path.append(node.name)
        score += node.weight
        recursion(depth, graph, path, node, score, results)

    return results

# The results should contain all the possible paths with the given score.

This is where I'd start. Good luck.

Upvotes: 0

Related Questions