Finding the number of paths between two nodes

Page 1 of 1

2 Replies - 959 Views - Last Post: 08 May 2015 - 08:52 PM

#1 PsylentKnight

Reputation: 0
• Posts: 16
• Joined: 04-March 15

Finding the number of paths between two nodes

Posted 05 May 2015 - 08:43 PM

Is it possible to find the number of paths between two nodes in a directed graph using an adjacency matrix? I know how to find all said paths of a given length by using matrix exponentiation, but I don't know how to find all the paths. The professor didn't note it in the assignment but I assume she meant all simple paths because this is a cyclic graph, so there's a potentially infinite number of paths.

I'm thinking I should use matrix exponentiation to find the number of paths of lengths 1 to n-1, where n is the number of nodes in the graph. Then add the number of paths for each length together. Would this work?

Is This A Good Question/Topic? 0

Replies To: Finding the number of paths between two nodes

#2 macosxnerd101

• Games, Graphs, and Auctions

Reputation: 12399
• Posts: 45,538
• Joined: 27-December 08

Re: Finding the number of paths between two nodes

Posted 05 May 2015 - 09:24 PM

A matrix will allow you to count walks, not paths. Walks allow for repeated vertices; and thus, cycles. To find paths, I would apply a BFS or DFS algorithm.

Also, I will move this to our Computer Science forum. If you don't have a Java-specific question, but a more theoretical one, the CS forum is the best place to post these questions.

I'd also be skeptical if you could find paths of length n-1 easily. The HAMILTONIAN PATH problem (paths of length n) is NP-Complete. I'm betting there is a reduction from HAMILTONIAN PATH to PATH(n-1) (does there exist a path of length n-2).

Reputation: 0
• Posts: 1
• Joined: 08-May 15

Re: Finding the number of paths between two nodes

Posted 08 May 2015 - 08:52 PM

I'm really new to computer science, only in my freshman year of computer science classes.
I recently did a project using Djikstra's, but that won't help you because you're looking for a number of paths.
Your problem seems to be a combinations problem, where the number of paths should multiply at each level, creating an increase in path possibilities similar to [n!]. To ensure that you do not have an infinite number of paths, we have to assume that you don't allow the re-traversal of an edge.
I would tentatively suggest (as I haven't tried this myself) that you create a program that does something similar to the following:
1.)call a function to check all adjacent (non-visited) nodes to your starting node.
2.)if none of those are your goal node, then each of those are possible paths for a path (for now). Add m to the possible paths number (where m is the number of adjacent edges).
3.) Mark the node you came from as visited, as well as those edges.
4.) recursively call the function to check each of these adjacent node's adjacent nodes. This will then add the number of branching possibilities from each of those.
5.) Stop if you reach the goal node

This will begin to get very large.
Also, because you are using an adjacency matrix, this will be implemented slightly differently where you need to check the combinations using an O(1) isAdjacent() function on each other node in the graph in order to know which edges are adjacent.