-
Notifications
You must be signed in to change notification settings - Fork 54
/
SingleSourceShortestPaths.html
207 lines (183 loc) · 6.69 KB
/
SingleSourceShortestPaths.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
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
<html>
<!-- THIS FILE WAS GENERATED BY A SCRIPT: DO NOT EDIT IT! -->
<head>
<link href="style.css" rel="stylesheet" type="text/css"/>
<title>
Design and Analyis of Algorithms: Single Source Shortest Paths
</title>
</head>
<body>
<div id="header">
<div id="logo">
<img src="graphics/Julia.png">
</div>
<div id="user-tools">
<a href="index.html">Home</a>
<a href="about.html">About</a>
<a href="feedback.html">Feedback</a>
</div>
</div>
<h1>
Design and Analyis of Algorithms: Single Source Shortest Paths
</h1>
<div style="text-align:center">
<p>
<img src="">
</p>
</div>
<details>
<summary class="sum1">
24.0 Introduction
</summary >
<details>
<summary class="sum2">
Cycles
</summary>
<p>
A shortest path (if it exists)
can always be achieved cycle free:
</p>
<ul>
<li>
If there is a negative-weight cycle, no answer is
possible.
</li>
<li>
If there is a positive-weight cycle, it can be
eliminated to produce a shorter path.
</li>
<li>
A zero-weight cycle can be eliminated to produce
a path of the same cost.
</li>
</ul>
</details>
<details>
<summary class="sum2">
Relaxation
</summary>
<p>
Why the funny name for a move that "tightens up"
the distance to v?
<br />
It is historical, coming from "relaxing" the triangle
constraint on the distance between <i>u</i> and
<i>v</i>.
</p>
<p>
<code>
<pre>
Relax(u, v, w)
if v.d > u.d + w(u, v)
v.d = u.d + w(u, v)
v.pred = u
</pre>
</code>
</p>
</details>
</details>
<details>
<summary class="sum1">
24.1 Bellman-Ford algorithm
</summary>
<details>
<summary class="sum2">
Bellman-Ford videos
</summary>
<figure>
<iframe width="560" height="315" src="https://www.youtube.com/embed/obWXjtg0L64" frameborder="0" allowfullscreen>
</iframe>
<figcaption>
Bellman-Ford in 5 minutes
</figcaption>
</figure>
<figure>
<iframe width="560" height="315" src="https://www.youtube.com/embed/rPsCRxTDwnQ" frameborder="0" allowfullscreen>
</iframe>
<figcaption>
Bellman-Ford with a negative weight cycle
</figcaption>
</figure>
</details>
</details>
<details>
<summary class="sum1">
24.3 Dijkstra's Algorithm
</summary >
<p>
Discovered by Edsger Dijkstra.
</p>
<figure>
<img
src="https://upload.wikimedia.org/wikipedia/commons/5/57/Dijkstra_Animation.gif">
<figcaption>
Dijkstra's algorithm running
</figcaption>
</figure>
<p>
<code>
<pre>
1 function Dijkstra(Graph, source):
2
3 create vertex set Q
4
5 for each vertex v in Graph: // Initialization
6 dist[v] = INFINITY // Unknown distance from source to v
7 prev[v] = UNDEFINED // Previous node in optimal path from source
8 add v to Q // All nodes initially in Q (unvisited nodes)
9
10 dist[source] = 0 // Distance from source to source
11
12 while Q is not empty:
13 u = vertex in Q with min dist[u] // Node with the least distance
14 // will be selected first
15 remove u from Q
16
17 for each neighbor v of u: // where v is still in Q.
18 alt = dist[u] + length(u, v)
19 if alt < dist[v]: // A shorter path to v has been found
20 dist[v] = alt
21 prev[v] = u
22
23 return dist[], prev[]
</pre>
</code>
</p>
</details>
<details>
<summary class="sum1">
Source Code
</summary>
<p>
<a
href="https://github.com/gcallah/algorithms/blob/master/Python/">
Python
</a>
<br>
</p>
</details>
<details>
<summary class="sum1">
For Further Study
</summary>
<ul>
<li>
<a
href="https://www.cs.usfca.edu/~galles/visualization/Dijkstra.html">
Shortest path visualizer
</a>
</li>
</ul>
</details>
</body>
<script>
(function(i,s,o,g,r,a,m){i['GoogleAnalyticsObject']=r;i[r]=i[r]||function(){
(i[r].q=i[r].q||[]).push(arguments)},i[r].l=1*new Date();a=s.createElement(o),
m=s.getElementsByTagName(o)[0];a.async=1;a.src=g;m.parentNode.insertBefore(a,m)
})(window,document,'script','https://www.google-analytics.com/analytics.js','ga');
ga('create', 'UA-97026578-2', 'auto');
ga('send', 'pageview');
</script>
</html>