Finding all possible paths from one node to anothe

问题:

I was trying to find all possible paths, but I am having hard time keeping track of the paths that I have visited. Here is the code so far:

public void FindAllPaths(Node startNode, Node endNode)
    {
        queue.Enqueue(startNode);

        while (queue.Count > 0)
        {
            var currentNode = queue.Dequeue();

            foreach (var edge in currentNode.Edges)
            {
                if (edge.Visisted)
                    continue;

                edge.Visisted = true;
                queue.Enqueue(edge.TargetNode);
            }
        }
    }

回答1:

You have to keep track of the paths visited for each route, not globally. For a breadth first approach each route needs a list of visited paths. For a depth first approach you can either keep a list of visited paths, or keep it global but unvisit the paths as you backtrack.

Getting the length of the path and the total weight will more or less do itself, once you keep track of the paths for each route.

With your current algorithm you would enqueue an item that has a node and a list of visited paths:

public void FindAllPaths(Node startNode, Node endNode) {
  queue.Enqueue(new QueueItem(startNode, new List<Edge>()));
  while (queue.Count > 0) {
    var currentItem = queue.Dequeue();
    foreach (var edge in currentItem.Node.Edges) {
      if (!currentItem.Visited.Contains(edge)) {
        List<Edge> visited = new List<Edge>(currentItem.Visited);
        visited.Add(edge);
        if (edge.TargetNode == endNode) {
          // visited.Count is the path length
          // visited.Sum(e => e.Weight) is the total weight
        } else {
          queue.Enqueue(new QueueItem(edge.TargetNode, visited));
        }
      }
    }
  }
}

The QueueItem class is just:

public class QueueItem {

  public Node Node { get; private set; }
  public List<Edge> Visited { get; private set; }

  public QueueItem(Node node, List<Edge> visited) {
    Node = node;
    Visited = visited;
  }

}

I set up the paths this way:

Node a = new Node("A");
Node b = new Node("B");
Node c = new Node("C");
Node d = new Node("D");
Node e = new Node("E");

a.Edges.Add(new Edge(5, b));
a.Edges.Add(new Edge(7, e));
a.Edges.Add(new Edge(5, d));
b.Edges.Add(new Edge(4, c));
c.Edges.Add(new Edge(2, e));
c.Edges.Add(new Edge(8, d));
d.Edges.Add(new Edge(8, c));
d.Edges.Add(new Edge(6, e));
e.Edges.Add(new Edge(3, b));

回答2:

As stated previously, maintaining a Visited property on each edge will not work because a given edge may be present in multiple distinct paths. For example, the D/E edge will be traversed for both the A->D->E path and the A->B->C->D->E path.

You need to maintain the current path for each node added to the queue:

IEnumerable<Path> FindAllPaths(Node from, Node to)
{
    Queue<Tuple<Node, List<Node>>> nodes = new Queue<Tuple<Node, List<Node>>>();
    nodes.Enqueue(new Tuple<Node, List<Node>>(from, new List<Node>()));
    List<Path> paths = new List<Path>();

    while(nodes.Any())
    {
        var current = nodes.Dequeue();
        Node currentNode = current.Item1;

        if (current.Item2.Contains(currentNode))
        {
            continue;
        }

        current.Item2.Add(currentNode);

        if (currentNode == to)
        {
            paths.Add(new Path(current.Item2));
            continue;
        }

        foreach(var edge in current.Item1.Edges)
        {
            nodes.Enqueue(new Tuple<Node, List<Node>>(edge.Target, new List<Node>(current.Item2)));
        }
    }

    return paths;
} 

回答3:

If you go A-B-C-E then C will be marked as visited, but since C is also part of the path A-D-C-E you won't be able to find the later. Therefore a depth-first approach seems more appropriate, as it allows you to work on one path at a time. After you are finished with a path, you can clear the Visited-flags and continue with another path. I'm trying to scetch a solution in pseudo code:

declare path as list of node;

procedure FindPath(node)
    for each edge in node.Edges
        if not edge.Visited then 
            edge.Visited = true
            path.Append(edge.TargetNode)
            if edge.TargetNode = goal then
                Print(path)
            else
                FindPath(edge.TargetNode)
            end
            path.Remove(edge.TargetNode)
            edge.Visited = false
        end
    end
end

Where goal is node E in your example. You would call FindPath with the start node

FindPath(A);