0
$\begingroup$

G{V, E} is directed, cyclic, weighted graph. What is the algorithm of finding all paths between any given two nodes?
Can you suggest any good reading?

Improve this question
$\endgroup$
4
  • 2
    $\begingroup$ In what sense do you want to find them? There could be exponentially many of them (even ignoring cycles). $\endgroup$
    – Yuval Filmus
    Oct 5, 2012 at 12:31
  • $\begingroup$ in order to know in how many ways it is possible to come to node u from node v $\endgroup$
    – torayeff
    Oct 5, 2012 at 12:39
  • 1
    $\begingroup$ There could even be infinitely many paths (you can co arbitrarily often through a cycle). See also here for simple paths. Besides, please flesh out your question with motivation and what you tried. $\endgroup$
    – Raphael ♦
    Oct 5, 2012 at 13:38
  • $\begingroup$ I don't think being weighed make any difference since you want to query all possible paths and not interested in the most economic ones. In addition, does G allow for self-loops, double edges? I think that DFS can do the job. $\endgroup$
    – user3077
    Oct 6, 2012 at 10:06

1 Answer 1

Reset to default
3
$\begingroup$

If the graph happens to be a DAG, then you can found the number of paths from any vertex to any other vertex using linear algebra. Let $A$ be the adjacency matrix of the graph. Compute $$ B = \sum_{k=0}^{n-1} A^k. $$ Then $B_{ij}$ is the number of paths (of length at most $n-1$) between vertex $i$ and vertex $j$. This also works for weighted graphs, in which case the weight of each path is the product of the weights on the edges.

It is easy to construct examples where there are exponentially many paths. For example, let the vertices be $x_0,\ldots,x_n,y_1,\ldots,y_n,z_1,\ldots,z_n$, and the edges be $(x_i,y_{i+1}),(x_i,z_{i+1}),(y_i,x_i),(z_i,x_i)$. The number of paths from $x_0$ to $x_n$ is $2^n$.

If the graph is not a DAG, then there can be infinitely many paths from a vertex to another, since any given cycle can be taken an unbounded number of times. In this case it makes sense to ask for the number of simple paths from one vertex to another. In the weighted version (with weights of polynomial length), we expect this to be difficult, since HAM-PATH can be solved this way.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.