[erlang-questions] Wanted: A method to find all paths from V1 to V2 using digraph module

[Jesper Louis Andersen]

That problem is just Floyd-Warshall for O(n^3) runtime. If you accept O(n^3
* lg n) then there is a brilliant algorithm based on successive matrix
multiplication (power ranking) in a matrix multiplication in which the +/2
operation is min/2. and the */2 operation is +/2. See for instance the code
in Paulson's ML for the working programmer, Chapter 7:
http://www.cl.cam.ac.uk/~lp15/MLbook/programs/sample7.sml Look for
MatrixZSP, ZSP and PathZSP in that code listing.



On Mon, Apr 23, 2018 at 4:36 PM bengt <cean.ebengt@REDACTED> wrote:

> The origin of this is the problem
> https://leetcode.com/problems/cheapest-flights-within-k-stops/description/
> so yes it is a very simple structure with lots of assumptions that can be
> made.
> Since it should be possible to write the code in 30 minutes I thought
> there might be a short-cut (Professor Layton solution :-)
> I will do it the long way instead. Hopefully in just one day. Should be
> good for me anyway.
>
>
> bengt
>
>
> On 23 Apr 2018, at 15:56, Jesper Louis Andersen <
> jesper.louis.andersen@REDACTED> wrote:
>
> On Sun, Apr 22, 2018 at 11:45 PM Vlad Dumitrescu <vladdu55@REDACTED>
> wrote:
>
>> Hi Bengt,
>>
>> The solution is to do a search starting from one of the vertices and keep
>> track of the found paths (saving a stack of already traversed vertices and
>> watching out for cycles), but in the worst case it is an O(n!) algorithm.
>> Even in non-pathological cases, it is easy to get an untractable number of
>> solutions as the complexity is exponential.
>>
>>
> The obvious algorithm is a breadth-first-search keeping track of the
> possible paths in each vertex. But if the number of edges are high, then
> this has to visit all the edges.
>
> It might be possible, given assumptions about cycles, to use a variant of
> (Floyd-)Warshall's algorithm. Build an "ascendancy matrix", but rather than
> processing boolean bits in each matrix cell, track the (number of) paths.
> If you can pull this off, then we are closer to something like O(n^3),
> though there are obvious flaws given cycles. So it may be you would need to
> analyze the incoming data and make sure the graph has a certain structure.
>
> Is the graph directed or undirected? Are all the paths simple (i.e., they
> are not allowed to cycle?). I'd also look into graph cuts where you can
> divide the graph into two halves, one containing S and one containing T. It
> could be the solution count can be based on that number.
>
>
> _______________________________________________
> erlang-questions mailing list
> erlang-questions@REDACTED
> http://erlang.org/mailman/listinfo/erlang-questions
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://erlang.org/pipermail/erlang-questions/attachments/20180423/dc317d2e/attachment.htm>