1

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

Dan Dinu
  • 32,492
  • 24
  • 78
  • 114
  • 1
    Isn't this what you're looking for? http://stackoverflow.com/questions/58306 – detunized May 28 '11 at 09:49
  • @detunized I think that other question wants to enumerate all of the roads, and this one only wants to count it. Counting can be done much faster than enumerating, because there can be exponentially many roads. – CodesInChaos May 28 '11 at 10:05

2 Answers2

1

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.

CodesInChaos
  • 106,488
  • 23
  • 218
  • 262
0

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

User
  • 1