http://code.activestate.com/recipes/tags/shortest/top/2013-10-02T12:52:23-07:00ActiveState Code Recipes2011-10-05T09:06:50-07:00Shao-chuan Wanghttp://code.activestate.com/recipes/users/4168519/http://code.activestate.com/recipes/577892-dijkstra-shortest-path-implementation/

<p style="color: grey"> Python recipe 577892 by <a href="/recipes/users/4168519/">Shao-chuan Wang</a> (<a href="/recipes/tags/dijkstra/">dijkstra</a>, <a href="/recipes/tags/optimization/">optimization</a>, <a href="/recipes/tags/shortest/">shortest</a>). </p> <p>This code snippet is the implementation of Dijkstra's algorithm.</p>

2013-10-02T12:52:23-07:00Rutger Saalminkhttp://code.activestate.com/recipes/users/4187940/http://code.activestate.com/recipes/578678-shortest-common-supersequence-algorithms/

<p style="color: grey"> Python recipe 578678 by <a href="/recipes/users/4187940/">Rutger Saalmink</a> (<a href="/recipes/tags/approximation/">approximation</a>, <a href="/recipes/tags/bound/">bound</a>, <a href="/recipes/tags/breadth_first_search/">breadth_first_search</a>, <a href="/recipes/tags/common/">common</a>, <a href="/recipes/tags/depth_first_search/">depth_first_search</a>, <a href="/recipes/tags/sequence/">sequence</a>, <a href="/recipes/tags/shortest/">shortest</a>, <a href="/recipes/tags/super/">super</a>). </p> <p>The Shortest Common Supersequence (SCS) problem is an NP-hard problem (<a href="https://en.wikipedia.org/wiki/Shortest_common_supersequence" rel="nofollow">https://en.wikipedia.org/wiki/Shortest_common_supersequence</a>), which occurs in problems originating from various domains, e.g. Bio Genetics. Given a set of strings, the common supersequence of minimal length is sought after. Below a set of algorithms is given, which I used in approximating and/or backtracking the optimal solution(s). </p>