1 Theory
1.1 Relaxation
Dijkstra’s algorithm uses the technique of relaxation. For each vertex v ∈ V
in the graph G = (V, E), we maintain an attribute v.d which represents the
upper bound on the weight of a shortest path from source s to v, thus it is a
shortest-path estimate. Also for each vertex v we maintain a predecessor
v.π that is either another vertex or null.
A pseudocode implementation of the algorithm to initialise the shortest-path
estimates and predecessors is given below:
1 initialise_source(G, s)
2 for each vertex v in G.V
3 v.d = infinity
4 v.pi = null
5 s.d = 0
This initialises v.π = for all v ∈ V , s.d = 0, and v.d = inf for v ∈ V − s
Relaxing an edge (u, v) consists of testing if the shortest path to v found so
far can be improved by going through u. If so, v.d and v.π can be updated,
more specifically a decrease in the shortest-path estimate and subsequent up-
dates to v’s predecessor attribute.
A pseudocode implementation of the algorithm to perform one relaxation step
on an edge (u, v) is given as follows:
6 relax(u, v, w)
7 if v.d > u.d + w(u, v)
8 v.d = u.d + w(u, v)
9 v.pi = u
1.2 Dijkstra’s algorithm
Dijkstra’s algorithm solves the single-source shortest-paths problem on a weighted,
directed graph for the case that all edge weights are non-negative.
G = (V, E), w(u, v) ≥ 0 for each edge (u, v) ∈ E
A set S of vertices is maintained whose final shortest-path weights from the
source s have already been determined
The vertex u ∈ V − S is repeatedly selected with the shortest-path estimate,
adds u to S, and relaxes all edges leaving u
A pseudocode implementation is given below:
1
1.1 Relaxation
Dijkstra’s algorithm uses the technique of relaxation. For each vertex v ∈ V
in the graph G = (V, E), we maintain an attribute v.d which represents the
upper bound on the weight of a shortest path from source s to v, thus it is a
shortest-path estimate. Also for each vertex v we maintain a predecessor
v.π that is either another vertex or null.
A pseudocode implementation of the algorithm to initialise the shortest-path
estimates and predecessors is given below:
1 initialise_source(G, s)
2 for each vertex v in G.V
3 v.d = infinity
4 v.pi = null
5 s.d = 0
This initialises v.π = for all v ∈ V , s.d = 0, and v.d = inf for v ∈ V − s
Relaxing an edge (u, v) consists of testing if the shortest path to v found so
far can be improved by going through u. If so, v.d and v.π can be updated,
more specifically a decrease in the shortest-path estimate and subsequent up-
dates to v’s predecessor attribute.
A pseudocode implementation of the algorithm to perform one relaxation step
on an edge (u, v) is given as follows:
6 relax(u, v, w)
7 if v.d > u.d + w(u, v)
8 v.d = u.d + w(u, v)
9 v.pi = u
1.2 Dijkstra’s algorithm
Dijkstra’s algorithm solves the single-source shortest-paths problem on a weighted,
directed graph for the case that all edge weights are non-negative.
G = (V, E), w(u, v) ≥ 0 for each edge (u, v) ∈ E
A set S of vertices is maintained whose final shortest-path weights from the
source s have already been determined
The vertex u ∈ V − S is repeatedly selected with the shortest-path estimate,
adds u to S, and relaxes all edges leaving u
A pseudocode implementation is given below:
1
