Re: all paths between 2 nodes

From: Jim Nastos (nastos_at_cs.ualberta.ca)
Date: 04/10/04 

Date: Sat, 10 Apr 2004 01:56:30 -0600

On 9 Apr 2004, Glenn C. Rhoads wrote:

> Now I fully understand what you mean but I have to point
> out that this is not an improvement. When finding the
> number of paths to B, the version I described does one
> addition at each of the nodes A, D, E, and F; your version
> waits until you get to B and then does all the additions.

  But every time you "update" B, you will have to update
any values that also depend on B (i.e. any other values
that B points to and that you've already written a label
for.)

> Also, I was tacitly assuming the most usual graph
> representation, namely an adjacency list of outgoing
> edges for each node. Under this representation, you
> can't efficiently perform the algorithm as you described
> it.

  Actually, one could easily implement this algorithm.
  The usual adjacency list can find a topsort in O(m+n)
time and then using that vertex ordering, one never needs to
find all in-edges because one can just add to the outedges
exactly once per edge provided the nodes are processed in the
order provided by the topsort.

J

Relevant Pages

  • Re: all paths between 2 nodes
    ... namely an adjacency list of outgoing ... Under this representation, you ... one could easily implement this algorithm. ... > The usual adjacency list can find a topsort in O ...
    (comp.theory)
  • Re: No Set Contains Every Computable Natural (was Church-Turing compared to Zuse-Fredkin thesis)
    ... Russell is right about Turing saying this, ... You might not want to call this an algorithm which has ... decimal representation of x digit by digit. ...
    (comp.theory)
  • rapidly converging rational sqrt
    ... I do not know if this algorithm is new, ... We designate the tail of this continued fraction using ... representation has the form: ... If the evaluation of the first n terms produced ...
    (sci.math.research)
  • Re: printf "%.100f" the value 2 ^ (-127)
    ... > I was trying to imagine an algorithm that, for at least one finite FP ... > representation, would output an infinite series of digits. ... This range contains an infinite number of rational values. ... or as a periodic decimal fraction (e.g. ...
    (microsoft.public.vc.language)
  • Re: Modelling an OO data structure
    ... strike me as especially O-O representations. ... The choice of algorithm affects the representation. ... extending the programming language into the problem domain (a ...
    (comp.object)
Loading