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?

$\endgroup$
  • 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 '12 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 '12 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 '12 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 '12 at 10:06
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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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