-
Notifications
You must be signed in to change notification settings - Fork 1
/
Copy pathall-pairs-shortest-path.html
108 lines (104 loc) · 5.17 KB
/
all-pairs-shortest-path.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
96
97
98
99
100
101
102
103
104
105
106
107
108
<!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="All-Pair Shortest Path" />
<meta property="og:type" content="article" />
<meta property="og:site_name" content="Problems" />
<meta property="article:tag" content="" />
<title>All-Pair Shortest Path</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">All-Pair Shortest Path</h1>
<br />
<div>
<h1 id="problem">Problem</h1>
<h2 id="preprocess">Preprocess</h2>
<p>A graph <span class="math inline">G=(V,E)</span> and <span class="math inline">w:E\to \mathbb{R}</span>, a conservative weight function.</p>
<h2 id="queries">Queries</h2>
<ul>
<li><span class="math inline">d(s,t)</span> returns the distance between <span class="math inline">s,t\in V</span>.</li>
<li><span class="math inline">S(s,t)</span> returns the the shortest path between <span class="math inline">s,t\in V</span>.</li>
</ul>
<h1 id="algorithm">Algorithm</h1>
<p>Parameters: <span class="math inline">n=|V|, m=|E|</span></p>
<h2 id="floydwarshall-algorithm">Floyd–Warshall algorithm</h2>
<ul>
<li><span class="math inline">O(n^3)</span> preprocess time.</li>
<li><span class="math inline">O(n^2)</span> space.</li>
<li><span class="math inline">O(1)</span> <span class="math inline">d(s,t)</span> query time.</li>
<li><span class="math inline">O(d(s,t))</span> <span class="math inline">S(s,t)</span> query time.</li>
</ul>
<h2 id="johnsons-algorithm">Johnson’s algorithm</h2>
<ul>
<li><span class="math inline">O(n^2\log n +nm)</span> preprocess time.</li>
<li><span class="math inline">O(n^2)</span> space.</li>
<li><span class="math inline">O(1)</span> <span class="math inline">d(s,t)</span> query time.</li>
<li><span class="math inline">O(d(s,t))</span> <span class="math inline">S(s,t)</span> query 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>