-
Notifications
You must be signed in to change notification settings - Fork 1
/
Copy pathgeneric-shortest-path-dag.html
95 lines (91 loc) · 4.74 KB
/
generic-shortest-path-dag.html
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
<!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/[email protected]/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/[email protected]/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/[email protected]/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>