how to find the number of roads from node A to node B in a directed graph?

I'm given a graph which can have more than one arch between 2 nodes.

Example :

4 nodes 1->2 2->3 3->4 3->4 1->4

Which is the开发者_开发问答 optim way to find the number of the roads from node A to node B ?

The answer for the example is 3 : 1->2->3->4 ; 1->2->3->4 and 1->4

Limit for nodes and archs are 1 000 000

I'm only thinking at a brute force algorithm.

Any other ideas? Edit:

graph is acyclic

---

If the graph is cyclic then the result is +infinity, since you can run in a cycle as often as you like.

One idea that might work on an acyclic directed graph:

• Order all nodes in a way so that for any two connected nodes the parent node comes always before the child node
• Assign 0 to all nodes
• Assign 1 to the start node
• Iterate over the nodes in that order starting with the start node and do
  • If the node is the end node you're done
  • Foreach connection starting on this node(i.e. it is the parent) do
    • Add the value of the current node to the child node
• The number assigned to the end node is your desired result

Ordering in the nodes isn't trivial though. But I'm sure you can find an algorithm for that, since it's a common problem when using DAGs.

---

There is no optimal way. This Problem is a NP Complete problem. http://en.wikipedia.org/wiki/Feedback_vertex_set

You can only find good solutions