Thread: All paths between two nodes

  1. #1
    Registered User
    Join Date
    Nov 2012
    Posts
    1

    All paths between two nodes

    Hi everyone, I’m trying to solve problem in which I have to calculate the number of paths from one node to all of other nodes in the directed graph and I have a predetermined length of paths. The problem can be solved by simple recursive function, but the size of the input data precludes this option. Connections between two nodes which appear at the input, can appear more then once and we treat them as a different connections.

    Code:
    N, M, K (1<=N<=40, 1<=M<=100000, 1<K=10^1000), where n is number of nodes, m is number of connections and k is length of paths.
    Example:
    Code:
    Input:
    4 6 2
    1 2
    2 1
    1 1
    1 2
    2 4
    1 3
    Output:
    3
    2
    1
    2
    
    Explanation:
    All possible paths with 2 hops are: (1,1,1), (1,2,1), (1,2,1), (1,1,2), (1,1,2), (1,1,3), (1,2,4), (1,2,4).
    The fact is that the number of vertices is very small relative to the number of connections, so in the graph will be many hundreds of cycles. I wonder if somehow can use this fact.
    Please, help me.

  2. #2
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,318
    What have you tried?
    My homepage
    Advice: Take only as directed - If symptoms persist, please see your debugger

    Linus Torvalds: "But it clearly is the only right way. The fact that everybody else does it some other way only means that they are wrong"

  3. #3
    and the hat of int overfl Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    39,660
    How about some research into graph theory to see what has already been studied.
    Graph theory - Wikipedia, the free encyclopedia

    And cross-posted
    If you dance barefoot on the broken glass of undefined behaviour, you've got to expect the occasional cut.
    If at first you don't succeed, try writing your phone number on the exam paper.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. All paths between two nodes
    By DeanWinchester in forum C Programming
    Replies: 1
    Last Post: 12-29-2011, 01:17 PM
  2. Relative Paths
    By Shingetsu Kurai in forum C++ Programming
    Replies: 5
    Last Post: 08-06-2011, 08:07 PM
  3. Exec and paths
    By Imanuel in forum C Programming
    Replies: 4
    Last Post: 07-31-2010, 03:00 PM
  4. Compiler Paths...
    By Cobra in forum C++ Programming
    Replies: 5
    Last Post: 09-26-2006, 04:04 AM
  5. Fixing paths
    By aker_y3k in forum C++ Programming
    Replies: 3
    Last Post: 10-05-2002, 10:32 AM