CODEWITHSUNDEEP
algorithmgraphdirected-graph
Dan Dinu
Dan Dinu

Reputation: 33398

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

Upvotes: 1

Views: 746

Answers (2)

User
User

Reputation: 1

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

Upvotes: 0

CodesInChaos
CodesInChaos

Reputation: 108810

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.

Upvotes: 1

Related Questions