-
Notifications
You must be signed in to change notification settings - Fork 0
/
sp.html
192 lines (165 loc) · 15 KB
/
sp.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
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
<!DOCTYPE html>
<html>
<head>
<meta charset="utf-8" />
<meta name="viewport" content="width=device-width, initial-scale=1.0" /><meta name="generator" content="Docutils 0.17.1: http://docutils.sourceforge.net/" />
<title>最短路径之 Dijkstra 和 Yen 算法 — Feng's blog 1.0 documentation</title>
<link rel="stylesheet" type="text/css" href="_static/pygments.css" />
<link rel="stylesheet" type="text/css" href="_static/alabaster.css" />
<script data-url_root="./" id="documentation_options" src="_static/documentation_options.js"></script>
<script src="_static/jquery.js"></script>
<script src="_static/underscore.js"></script>
<script src="_static/doctools.js"></script>
<script async="async" src="https://cdn.jsdelivr.net/npm/mathjax@3/es5/tex-mml-chtml.js"></script>
<script>window.MathJax = {"options": {"processHtmlClass": "tex2jax_process|mathjax_process|math|output_area"}}</script>
<script src="_static/custom.js"></script>
<link rel="index" title="Index" href="genindex.html" />
<link rel="search" title="Search" href="search.html" />
<link rel="next" title="有符号类型、负数与类型转换" href="signed-type-and-type-conversion.html" />
<link rel="prev" title="Feng’s blog" href="index.html" />
<link rel="stylesheet" href="_static/custom.css" type="text/css" />
<meta name="viewport" content="width=device-width, initial-scale=0.9, maximum-scale=0.9" />
</head><body>
<div class="document">
<div class="documentwrapper">
<div class="bodywrapper">
<div class="body" role="main">
<section id="zui-duan-lu-jing-zhi-dijkstra-he-yen-suan-fa">
<h1>最短路径之 Dijkstra 和 Yen 算法<a class="headerlink" href="#zui-duan-lu-jing-zhi-dijkstra-he-yen-suan-fa" title="Permalink to this headline">¶</a></h1>
<section id="dijkstra-suan-fa">
<h2>Dijkstra 算法<a class="headerlink" href="#dijkstra-suan-fa" title="Permalink to this headline">¶</a></h2>
<p>Dijkstra 算法是计算最短路径的经典算法。设需要计算的图为 <span class="math notranslate nohighlight">\(G\)</span> ，起点 <span class="math notranslate nohighlight">\(s\)</span> ，终点 <span class="math notranslate nohighlight">\(d\)</span> 。伪算法描述：</p>
<div class="highlight-python notranslate"><div class="highlight"><pre><span></span><span class="k">def</span> <span class="nf">Dijkstra</span><span class="p">(</span><span class="n">G</span><span class="p">,</span> <span class="n">s</span><span class="p">,</span> <span class="n">d</span><span class="p">):</span>
<span class="c1"># dist[i] 保存从起点到顶点 i 当前计算出的最短距离，默认初始化为 ♾️</span>
<span class="c1"># prev[i] 保存到顶点 i 当前最短路径的上一跳节点</span>
<span class="k">for</span> <span class="n">v</span> <span class="ow">in</span> <span class="n">G</span><span class="o">.</span><span class="n">vertices</span><span class="p">:</span>
<span class="n">dist</span><span class="p">[</span><span class="n">v</span><span class="p">]</span> <span class="o">=</span> <span class="n">inf</span>
<span class="n">prev</span><span class="p">[</span><span class="n">v</span><span class="p">]</span> <span class="o">=</span> <span class="n">undefined</span>
<span class="n">Q</span><span class="o">.</span><span class="n">append</span><span class="p">(</span><span class="n">v</span><span class="p">)</span>
<span class="c1"># 起点到起点的距离为 0</span>
<span class="n">dist</span><span class="p">[</span><span class="n">s</span><span class="p">]</span> <span class="o">=</span> <span class="mi">0</span>
<span class="k">while</span> <span class="nb">len</span><span class="p">(</span><span class="n">Q</span><span class="p">)</span> <span class="o">></span> <span class="mi">0</span><span class="p">:</span>
<span class="c1"># 取当前集合 Q 里距离起点 s 最近的一个顶点</span>
<span class="n">u</span> <span class="o">=</span> <span class="n">vertex</span> <span class="ow">in</span> <span class="n">Q</span> <span class="k">with</span> <span class="nb">min</span> <span class="n">dist</span><span class="p">[</span><span class="n">u</span><span class="p">]</span>
<span class="c1"># 从集合 Q 中删除顶点 u</span>
<span class="n">remove</span> <span class="n">u</span> <span class="kn">from</span> <span class="nn">Q</span>
<span class="c1"># 计算完成，退出</span>
<span class="k">if</span> <span class="n">u</span> <span class="o">==</span> <span class="n">d</span><span class="p">:</span>
<span class="k">break</span>
<span class="c1"># 遍历顶点 u 所有的相邻节点 v，如果 s->u 的距离加上 u->v 的距离小于</span>
<span class="c1"># 当前 s->v 的最短距离，更新</span>
<span class="k">for</span> <span class="n">each</span> <span class="n">neighbor</span> <span class="n">v</span> <span class="n">of</span> <span class="n">u</span><span class="p">:</span>
<span class="k">if</span> <span class="n">v</span> <span class="ow">in</span> <span class="n">Q</span><span class="p">:</span>
<span class="n">alt</span> <span class="o">=</span> <span class="n">dist</span><span class="p">[</span><span class="n">u</span><span class="p">]</span> <span class="o">+</span> <span class="n">Graph</span><span class="o">.</span><span class="n">edges</span><span class="p">(</span><span class="n">u</span><span class="p">,</span> <span class="n">v</span><span class="p">)</span>
<span class="k">if</span> <span class="n">alt</span> <span class="o"><</span> <span class="n">dist</span><span class="p">[</span><span class="n">v</span><span class="p">]:</span>
<span class="n">dist</span><span class="p">[</span><span class="n">v</span><span class="p">]</span> <span class="o">=</span> <span class="n">alt</span>
<span class="n">prev</span><span class="p">[</span><span class="n">v</span><span class="p">]</span> <span class="o">=</span> <span class="n">u</span>
<span class="c1"># 反向遍历得到最短路径</span>
<span class="n">p</span> <span class="o">=</span> <span class="p">[</span><span class="n">d</span><span class="p">]</span>
<span class="k">while</span> <span class="n">prev</span><span class="p">[</span><span class="n">d</span><span class="p">]</span> <span class="o">!=</span> <span class="n">undefined</span><span class="p">:</span>
<span class="n">p</span><span class="o">.</span><span class="n">insert</span><span class="p">(</span><span class="mi">0</span><span class="p">,</span> <span class="n">prev</span><span class="p">[</span><span class="n">d</span><span class="p">])</span>
<span class="n">d</span> <span class="o">=</span> <span class="n">prev</span><span class="p">[</span><span class="n">d</span><span class="p">]</span>
<span class="k">return</span> <span class="n">dist</span><span class="p">[</span><span class="n">d</span><span class="p">],</span> <span class="n">p</span>
</pre></div>
</div>
<p>Dijkstra 算法的主要思想是广度优先搜索，每次选择距离起点最近的顶点扩展，逐步往外直到得到所有节点（或者目标节点）的最短路径。其时间复杂度为 <span class="math notranslate nohighlight">\(O(n^2)\)</span> 。</p>
<p>以下图为例，计算起点 <span class="math notranslate nohighlight">\(C\)</span>，终点 <span class="math notranslate nohighlight">\(H\)</span> 的最短路径：</p>
<img alt="_images/sp-1.png" src="_images/sp-1.png" />
<ul class="simple">
<li><p>第一轮迭代，计算可以得到 <span class="math notranslate nohighlight">\(C-D\)</span> 距离 3， <span class="math notranslate nohighlight">\(C-E\)</span> 距离 2。</p></li>
<li><p>第二轮，扩展 <span class="math notranslate nohighlight">\(E\)</span> 点，更新得 <span class="math notranslate nohighlight">\(C-D\)</span> 距离 3， <span class="math notranslate nohighlight">\(C-E-F\)</span> 距离 4， <span class="math notranslate nohighlight">\(C-E-G\)</span> 距离 5。</p></li>
<li><p>第三轮，扩展 <span class="math notranslate nohighlight">\(D\)</span> 点，更新得 <span class="math notranslate nohighlight">\(C-D-F\)</span> 距离 7， <span class="math notranslate nohighlight">\(C-E-F\)</span> 距离 4， <span class="math notranslate nohighlight">\(C-E-G\)</span> 距离 5。</p></li>
<li><p>第四轮，扩展 <span class="math notranslate nohighlight">\(F\)</span> 点，更新得 <span class="math notranslate nohighlight">\(C-D-F-H\)</span> 距离 8，<span class="math notranslate nohighlight">\(C-E-F-G\)</span> 距离 6， <span class="math notranslate nohighlight">\(C-E-F-H\)</span> 距离 5， <span class="math notranslate nohighlight">\(C-E-G\)</span> 距离为 5。</p></li>
<li><p>第五轮，扩展 <span class="math notranslate nohighlight">\(H\)</span> 点，计算结束，得到 <span class="math notranslate nohighlight">\(C-E-F-H\)</span> 为最短路径。</p></li>
</ul>
</section>
<section id="yen-suan-fa">
<h2>Yen 算法<a class="headerlink" href="#yen-suan-fa" title="Permalink to this headline">¶</a></h2>
<p>Yen 算法是 Dijkstra 算法的扩展，Dijkstra 只能计算得到一条最短路径，Yen 算法可以计算出 TOP K 条最短路径。这个在很多场景下会很有用，比如 Google 在 B4 论文中提到其广域网就用到 Yen 算法来计算多条路由，然后按照线路的带宽和应用的优先级来给不同的应用分配不同的路由。</p>
<p>给定图 <span class="math notranslate nohighlight">\(G\)</span>，起点 <span class="math notranslate nohighlight">\(s\)</span>， 终点 <span class="math notranslate nohighlight">\(d\)</span>，想要的获得的最短路径条数 <span class="math notranslate nohighlight">\(k\)</span>。Yen 算法的基本流程如下：</p>
<ol class="arabic">
<li><p>首先，调用 Dijkstra 算法获得最短路径 <span class="math notranslate nohighlight">\(P[0]\)</span> 。</p></li>
<li><p>求 <span class="math notranslate nohighlight">\(P[i+1]\)</span> 时，将 <span class="math notranslate nohighlight">\(P[i]\)</span> 路径上除了终点 <span class="math notranslate nohighlight">\(d\)</span> 之外的其他点依次作为一个偏离节点（Spur Node）。</p>
<p>对每一个偏离节点，设 <span class="math notranslate nohighlight">\(P[i]\)</span> 路径中起点到偏离点的路径为 <span class="math notranslate nohighlight">\(rootPath\)</span>，遍历所有已经计算出的最短路径，如果某条路径中包含 <span class="math notranslate nohighlight">\(rootPath\)</span>，将这个路径中 <span class="math notranslate nohighlight">\(rootPath\)</span> 接下去的那一条边从图中删除。调用 Dijkstra 算法重新计算这个偏离点到终点的最短路径，设为 <span class="math notranslate nohighlight">\(spurPath\)</span>，<span class="math notranslate nohighlight">\(rootPath + spurPath\)</span> 作为 <span class="math notranslate nohighlight">\(P[i]\)</span> 的一个候选路径。</p>
<p>所有偏离节点计算得到的候选路径中取最短的一条作为 <span class="math notranslate nohighlight">\(P[i+1]\)</span> 。</p>
</li>
<li><p>重复 2 直到所有的 k 条路径计算完成。</p></li>
</ol>
<p>还是以上文 Dijkstra 算法中的图为例，来手算下 Yen 算法。</p>
<ol class="arabic">
<li><p>首先通过 Dijkstra 算法获得最短路径 <span class="math notranslate nohighlight">\(P[0] = C-E-F-H\)</span> 。</p></li>
<li><p>计算 <span class="math notranslate nohighlight">\(P[1]\)</span></p>
<ul class="simple">
<li><p>以 <span class="math notranslate nohighlight">\(C\)</span> 为偏离点，删除 <span class="math notranslate nohighlight">\(C-E\)</span> 边，重新计算得最短路径 <span class="math notranslate nohighlight">\(C-D-F-H\)</span> 。</p></li>
<li><p>以 <span class="math notranslate nohighlight">\(E\)</span> 为偏离点，删除 <span class="math notranslate nohighlight">\(E-F\)</span> 边，重新计算得最短路径 <span class="math notranslate nohighlight">\(C-E-G-H\)</span> 。</p></li>
<li><p>以 <span class="math notranslate nohighlight">\(F\)</span> 为偏离点，删除 <span class="math notranslate nohighlight">\(F-H\)</span> 边，重新计算得最短路径 <span class="math notranslate nohighlight">\(C-E-F-G-H\)</span> 。</p></li>
</ul>
<p>取三条候选里最短的，得 <span class="math notranslate nohighlight">\(P[1] = C-E-G-H\)</span>。</p>
<img alt="_images/sp-2.png" src="_images/sp-2.png" />
</li>
<li><p>继续计算可得 <span class="math notranslate nohighlight">\(P[2] = C-D-F-H\)</span> 。</p></li>
</ol>
<p>References:</p>
<ul class="simple">
<li><p><a class="reference external" href="https://zhuanlan.zhihu.com/p/336140079">https://zhuanlan.zhihu.com/p/336140079</a></p></li>
<li><p><a class="reference external" href="https://en.wikipedia.org/wiki/Dijkstra%27s_algorithm">https://en.wikipedia.org/wiki/Dijkstra%27s_algorithm</a></p></li>
<li><p><a class="reference external" href="https://en.wikipedia.org/wiki/Yen%27s_algorithm">https://en.wikipedia.org/wiki/Yen%27s_algorithm</a></p></li>
</ul>
</section>
</section>
</div>
</div>
</div>
<div class="sphinxsidebar" role="navigation" aria-label="main navigation">
<div class="sphinxsidebarwrapper">
<h3><a href="index.html">Table of Contents</a></h3>
<ul>
<li><a class="reference internal" href="#">最短路径之 Dijkstra 和 Yen 算法</a><ul>
<li><a class="reference internal" href="#dijkstra-suan-fa">Dijkstra 算法</a></li>
<li><a class="reference internal" href="#yen-suan-fa">Yen 算法</a></li>
</ul>
</li>
</ul>
<div role="note" aria-label="source link">
<h3>This Page</h3>
<ul class="this-page-menu">
<li><a href="_sources/sp.rst.txt"
rel="nofollow">Show Source</a></li>
</ul>
</div>
<div id="searchbox" style="display: none" role="search">
<h3 id="searchlabel">Quick search</h3>
<div class="searchformwrapper">
<form class="search" action="https://cn.bing.com/search" method="get">
<input type="text" name="q" aria-labelledby="searchlabel" autocomplete="off" autocorrect="off" autocapitalize="off" spellcheck="false"/>
<input type="submit" value="Go" />
</form>
</div>
</div>
<script>
$('#searchbox').show(0);
document.getElementsByClassName('search')[0].addEventListener('submit', function(event) {
event.preventDefault();
var form = event.target;
var input = form.querySelector('input[name="q"]');
var value = input.value;
var q = 'ensearch=1&q=site%3Achanfung032.github.io++' + value;
var url = form.action + '?' + q;
window.location.href = url;
});
</script>
</div>
</div>
<div class="clearer"></div>
</div>
<div class="footer">
©2017, chanfung032.
|
Powered by <a href="http://sphinx-doc.org/">Sphinx 4.1.2</a>
& <a href="https://github.com/bitprophet/alabaster">Alabaster 0.7.12</a>
|
<a href="_sources/sp.rst.txt"
rel="nofollow">Page source</a>
</div>
</body>
</html>