You signed in with another tab or window. Reload to refresh your session.You signed out in another tab or window. Reload to refresh your session.You switched accounts on another tab or window. Reload to refresh your session.Dismiss alert
Copy file name to clipboardExpand all lines: src/graph/dijkstra.md
+40-45Lines changed: 40 additions & 45 deletions
Display the source diff
Display the rich diff
Original file line number
Diff line number
Diff line change
@@ -1,33 +1,32 @@
1
1
<!--?title Dijkstra Algorithm -->
2
2
3
3
# Dijkstra Algorithm
4
-
### Finding Shortest Paths from Given Vertex to all Other Vertices
5
4
6
-
You are given a directed or undirected weighted graph with $n$ vertices and $m$ edges. The weights of all edges are non-negative. You are also given a starting vertex $s$. Find the lengths of the shortest paths from vertex $s$ to all other vertices, and output the shortest paths themselves.
5
+
You are given a directed or undirected weighted graph with $n$ vertices and $m$ edges. The weights of all edges are non-negative. You are also given a starting vertex $s$. This article discusses finding the lengths of the shortest paths from a starting vertex $s$ to all other vertices, and output the shortest paths themselves.
7
6
8
-
This problem is also called "single-source shortest paths problem".
7
+
This problem is also called **single-source shortest paths problem**.
9
8
10
9
## Algorithm
11
10
12
11
Here is an algorithm described by the Dutch computer scientist Edsger W. Dijkstra in 1959.
13
12
14
-
Let's create an array $d[]$ where for each vertex $v$ we store the current length of the shortest path from $s$ to $v$ $d[v]$. Initially $d[s] = 0$, and for all other vertices this length equals infinity. In a computer implementation a sufficiently large number (which is guaranteed to be greater than any possible path length) is chosen as infinity:
13
+
Let's create an array $d[]$ where for each vertex $v$ we store the current length of the shortest path from $s$ to $v$ in $d[v]$.
14
+
Initially $d[s] = 0$, and for all other vertices this length equals infinity.
15
+
In the implementation a sufficiently large number (which is guaranteed to be greater than any possible path length) is chosen as infinity.
15
16
16
-
$$d[v] = \infty, v \ne s$$
17
+
$$d[v] = \infty,~ v \ne s$$
17
18
18
-
In addition, we maintain a boolean array $u[]$ which stores for each vertex $v$ whether it's marked. Initially all vertices are unmarked:
19
+
In addition, we maintain a Boolean array $u[]$ which stores for each vertex $v$ whether it's marked. Initially all vertices are unmarked:
19
20
20
21
$$u[v] = {\rm false}$$
21
22
22
23
The Dijkstra's algorithm runs for $n$ iterations. At each iteration a vertex $v$ is chosen as unmarked vertex which has the least value $d[v]$:
23
24
24
-
$$d[v] = \min_{p: u[p]={\rm false}} d[p]$$
25
-
26
25
Evidently, in the first iteration the starting vertex $s$ will be selected.
27
26
28
-
Thus selected vertex $v$ is marked. Next, from vertex $v$ **relaxations** are performed: all edges of the form $(v,to)$ are considered, and for each vertex $to$ the algorithm tries to improve the value $d[to]$. If the length of the current edge equals $len$, the code for relaxation is:
27
+
The selected vertex $v$ is marked. Next, from vertex $v$ **relaxations** are performed: all edges of the form $(v,\text{to})$ are considered, and for each vertex $\text{to}$ the algorithm tries to improve the value $d[\text{to}]$. If the length of the current edge equals $len$, the code for relaxation is:
After all such edges are considered, the current iteration ends. Finally, after $n$ iterations, all vertices will be marked, and the algorithm terminates. We claim that the found values $d[v]$ are the lengths of shortest paths from $s$ to all vertices $v$.
33
32
@@ -39,9 +38,9 @@ Usually one needs to know not only the lengths of shortest paths but also the sh
39
38
40
39
$$P = (s, \ldots, p[p[p[v]]], p[p[v]], p[v], v)$$
41
40
42
-
Building this array of predecessors is very simple: for each successful relaxation, i.e. when for some selected vertex $v$, there is an improvement in the distance to some vertex $to$, we update the predecessor vertex for $to$ with vertex $v$:
41
+
Building this array of predecessors is very simple: for each successful relaxation, i.e. when for some selected vertex $v$, there is an improvement in the distance to some vertex $\text{to}$, we update the predecessor vertex for $\text{to}$ with vertex $v$:
43
42
44
-
$$p[to] = v$$
43
+
$$p[\text{to}] = v$$
45
44
46
45
## Proof
47
46
@@ -71,7 +70,7 @@ Q.E.D.
71
70
72
71
## Implementation
73
72
74
-
Dijkstra's algorithm performs $n$ iterations. On each iteration it selects an unmarked vertex $v$ with the lowest value $d[v]$, marks it and checks all the edges $(v, to)$ attempting to improve the value $d[to]$.
73
+
Dijkstra's algorithm performs $n$ iterations. On each iteration it selects an unmarked vertex $v$ with the lowest value $d[v]$, marks it and checks all the edges $(v, \text{to})$ attempting to improve the value $d[\text{to}]$.
75
74
76
75
The running time of the algorithm consists of:
77
76
@@ -82,40 +81,31 @@ For the simplest implementation of these operations on each iteration vertex sea
Here the graph $g$ is stored as adjacency list: for each vertex $v$ $g[v]$ contains the list of edges going from this vertex, i.e. the list of `pair<int,int>` where the first element in the pair is the vertex at the other end of the edge, and the second element is the edge weight.
119
+
Here the graph $\text{adj}$ is stored as adjacency list: for each vertex $v$ $\text{adj}[v]$ contains the list of edges going from this vertex, i.e. the list of `pair<int,int>` where the first element in the pair is the vertex at the other end of the edge, and the second element is the edge weight.
130
120
131
-
First of all, the code initializes arrays: distances $d[]$, labels $u[]$ and predecessors $p[]$. Then it performs $n$ iterations. At each iteration the vertex $v$ is selected which has the smallest distance $d[v]$ among all the unmarked vertices. If the distance to selected vertex $v$ is equal to infinity, the algorithm stops. Otherwise the vertex is marked, and all the edges going out from this vertex are checked. If relaxation along the edge is possible (i.e. distance $d[to]$ can be improved), the distance $d[to]$ and predecessor $p[to]$ are updated.
121
+
The function takes the starting vertex $s$ and two vectors that will be used as return values.
122
+
123
+
First of all, the code initializes arrays: distances $d[]$, labels $u[]$ and predecessors $p[]$. Then it performs $n$ iterations. At each iteration the vertex $v$ is selected which has the smallest distance $d[v]$ among all the unmarked vertices. If the distance to selected vertex $v$ is equal to infinity, the algorithm stops. Otherwise the vertex is marked, and all the edges going out from this vertex are checked. If relaxation along the edge is possible (i.e. distance $d[\text{to}]$ can be improved), the distance $d[\text{to}]$ and predecessor $p[\text{to}]$ are updated.
132
124
133
125
After performing all the iterations array $d[]$ stores the lengths of the shortest paths to all vertices, and array $p[]$ stores the predecessors of all vertices (except starting vertex $s$). The path to any vertex $t$ can be restored in the following way:
134
126
135
-
```cpp
136
-
vector<int> path;
127
+
```cpp dijkstra_restore_path
128
+
vector<int> restore_path(int s, int t, vector<int> const& p) {
0 commit comments