generic-shortest-path-dag.html

<!DOCTYPE html>
<html lang="en">
  <head>
    <meta http-equiv="Content-Type" content="text/html; charset=utf-8">
    <meta name="viewport" content="width=device-width, initial-scale=1">
    <meta name="description" content="Problems">
    <meta name="author" content="Chao Xu">
    <meta property="og:title" content="Generic Shortest Path for DAGs" />
    <meta property="og:type" content="article" />
    <meta property="og:site_name" content="Problems" />
    <meta property="article:tag" content="" />
    <title>Generic Shortest Path for DAGs</title>

    <link rel="stylesheet" href="https://cdn.jsdelivr.net/npm/katex@0.11.0/dist/katex.min.css" integrity="sha384-BdGj8xC2eZkQaxoQ8nSLefg4AV4/AwB3Fj+8SUSo7pnKP6Eoy18liIKTPn9oBYNG" crossorigin="anonymous">

    <!-- The loading of KaTeX is deferred to speed up page rendering -->
    <script defer src="https://cdn.jsdelivr.net/npm/katex@0.11.0/dist/katex.min.js" integrity="sha384-JiKN5O8x9Hhs/UE5cT5AAJqieYlOZbGT3CHws/y97o3ty4R7/O5poG9F3JoiOYw1" crossorigin="anonymous"></script>

    <!-- To automatically render math in text elements, include the auto-render extension: -->
    <!-- <script defer src="https://cdn.jsdelivr.net/npm/katex@0.11.0/dist/contrib/auto-render.min.js" integrity="sha384-kWPLUVMOks5AQFrykwIup5lo0m3iMkkHrD0uJ4H5cjeGihAutqP0yW0J6dpFiVkI" crossorigin="anonymous"
        onload="renderMathInElement(document.body);"></script> 
    -->
    <script defer>
      function render_katex_math(){
        const macros={
                      "\\C":"\\mathbb{C}",
                      "\\F":"\\mathbb{F}",
                      "\\e": "\\varepsilon",
                      "\\eps": "\\varepsilon",
                      "\\mex": "\\mathop{\\operatorname{mex}}",
                      "\\lcm": "\\mathop{\\operatorname{lcm}}",
                      "\\dist": "\\mathop{\\operatorname{dist}}",
                      "\\bigtriangleright": "{\\mathop{\\Large \\triangleright}}",
                      "\\bigtriangleleft": "{\\mathop{\\Large \\triangleleft}}",
                      '\\set':'\\left\\{ #1 \\right\\}',
                      '\\floor':'\\left\\lfloor #1 \\right\\rfloor',
                      '\\ceil':'\\left\\lceil #1 \\right\\rceil',
                      '\\abs':'\\left\\| #1 \\right\\|'
                      };
        const mathElements = document.getElementsByClassName("math");
        for (var i = 0; i < mathElements.length; i++) {
                  var texText = mathElements[i].firstChild;
                  if (mathElements[i].tagName == "SPAN") {
                   katex.render(texText.data, mathElements[i], 
                    { displayMode: mathElements[i].classList.contains("display"), throwOnError: false, macros:macros}
                  );
                }
        };
      };
      window.onload = render_katex_math;
    </script>

  <link rel="shortcut icon" type="image/x-icon" href="/favicon.ico"/>
  <link rel="stylesheet" href="/css/default.css" crossorigin="anonymous">
  <link rel="stylesheet" href="/css/blog.css" crossorigin="anonymous">
  </head>
  <body>
    <header class="hide-on-print">
        <div id="site-title">
            <a href="/">Problems</a>
        </div>
    </header>
    <!--<nav class="hide-on-print">
      <ul>
        <li><a href="/">Home</a></li>
      </ul>
    </nav>-->
    <main>
      <article>
        <h1 id="article-title">Generic Shortest Path for DAGs</h1>
        <br />
<div>
<h1 id="problem">Problem</h1>
<p>Let <span class="math inline">D=(V,A)</span> be a DAG with weight <span class="math inline">w:A\to S</span>, where <span class="math inline">(S,\oplus,\otimes,\bar{0},\bar{1})</span> is a semiring, <span class="math inline">s</span> be a given vertex. <span class="math inline">P(v)</span> be the set of all one way paths from <span class="math inline">s</span> to <span class="math inline">v</span>.</p>
<p>Find <span class="math display">
\delta(v) = \bigoplus_{\pi \in P(v)} \bigotimes_{a \in \pi} w(a)
</span> for each <span class="math inline">v</span>.</p>
<h1 id="algorithms">Algorithms</h1>
<p>Parameters: <span class="math inline">n=|V|</span>, <span class="math inline">m=|A|</span>, <span class="math inline">M</span> is the maximum time required to preform semiring operations.</p>
<h2 id="viterbi-algorithm">Viterbi Algorithm</h2>
<ul>
<li><span class="math inline">O(M(m+n))</span> time.</li>
</ul>
</div>
<div class="hide-on-print">
    <div class="info">Tags: .</div>
</div>
      </article>
    </main>
    <!--
    <footer class="hide-on-print">© 2010 - <time><script>document.write(new Date().getFullYear())</script></time> <a href="https://chaoxuprime.com" rel="author">Chao Xu</a>. Licensed under a <a rel="license" href="http://creativecommons.org/licenses/by/4.0/">Creative Commons Attribution 4.0 International License</a>.
    </footer>
    -->
  </body>
</html>