<html><head><meta http-equiv="Content-Type" content="text/html charset=us-ascii"></head><body style="word-wrap: break-word; -webkit-nbsp-mode: space; -webkit-line-break: after-white-space;" class="">The origin of this is the problem <a href="https://leetcode.com/problems/cheapest-flights-within-k-stops/description/" class="">https://leetcode.com/problems/cheapest-flights-within-k-stops/description/</a><br class="">so yes it is a very simple structure with lots of assumptions that can be made.<br class="">Since it should be possible to write the code in 30 minutes I thought there might be a short-cut (Professor Layton solution :-)<br class="">I will do it the long way instead. Hopefully in just one day. Should be good for me anyway.<br class=""><br class="">bengt<br class=""><br class=""><div><blockquote type="cite" class=""><div class="">On 23 Apr 2018, at 15:56, Jesper Louis Andersen <<a href="mailto:jesper.louis.andersen@gmail.com" class="">jesper.louis.andersen@gmail.com</a>> wrote:</div><br class="Apple-interchange-newline"><div class=""><div dir="ltr" class="">On Sun, Apr 22, 2018 at 11:45 PM Vlad Dumitrescu <<a href="mailto:vladdu55@gmail.com" class="">vladdu55@gmail.com</a>> wrote:<br class=""><div class="gmail_quote"><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><div dir="ltr" class="">Hi Bengt,<div class=""><br class=""></div><div class="">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. </div><div class=""><br class=""></div></div></blockquote><div class=""><br class=""></div><div class="">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.<br class=""><br class=""></div><div class="">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.<br class=""><br class=""></div><div class="">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.<br class=""><br class=""></div></div></div>
</div></blockquote></div><br class=""></body></html>