In order to extend the representation of graphs to weighted graphs, we extend
adjacency lists to store not just the destination node of each arc, but also
its weight (e.g., a distance or a cost), which we will be considering a real
value:
using node = int; // nodes are represented by indices from 0
using weight = double; // weights are real numbers
using arc = pair<weight, node>; // an arc is represented by its weight and its destination node
using WAdjacencyList = vector<arc>; // the adjacency list of one node (set of arcs to successor nodes)
using WGraph = vector<WAdjacencyList>; // the complete adjacency list for all nodes in the graph
The reason to use the weight as the first element of the arc pair
is that it will determine the ordering of the pair, which will be useful
in many subsequent algorithms.
As an exemple, the following weighted graph
Layout:
can be defined as
```
Graph G = {
{{10, 1}, {8, 7}}, // 0
{{2.5, 5}}, // 1
{{1, 1}, {1, 3}}, // 2
{{4, 3}}, // 3
{{1, 5}}, // 4
{{-2, 2}}, // 5
{{1, 5}, {4, 1}}, // 6
{{1, 6}}, // 7
};
```
Observe that we do not add contraints on the order of the nodes in the
adjacency lists —even though this could make sense in some settings. However,
we do not allow repetitions (this would mean multiple arcs) nor self-loops.
In the following, $n$ denotes the number of nodes of a graph, and
$m$ denotes its number of arcs.
Furthermore, the `infinity` constant will be used to denote
the infinity value for weights, which is also quite handy in
many algorithms:
```
const weight infinity = numeric_limits::infinity();
```
The `infinity` value is legal for `double` variables and has all
the nice properties of the ∞ symbol.
As we did the lesson on graphs, we will use the `None` constant
to denote spectial integer values:
```
const int None = -1;
```
## Shortest paths with Dijkstra's algorithm
The following code implements Dijkstra's algorithm in order to compute the
shortest paths from one source node to all the nodes in a directed graph
with non-negative weights on the arcs.
The input of `dijkstra()` is a weighted graph `G` with non-negative weights on
the arcs, and a source node `s` from `G`. Its output are two vectors `d` and
`p`. For each node `u` in `G`, `d[u]` is the minimum distance from `s` to
`u` (or ∞ if `u` is not reachable from `s`) and `p[u]` is the parent node of
`u`, that is the node from which `u` should be reached in order to get the
minimum distance `d[u]`. We have that `p[u]` is `None` if `u` in unreachable
from `s` or when `u == s`.
During the execution of the algorithm we maintain the subset `S ⊆ V` of vertices
for which their minimum distance from `s` computed so far is the optimal one.
```
void dijkstra(const WGraph& G, node s, vector& d, vector& p) {
int n = G.size(); // number of nodes in the graph
d = vector(n, infinity); // for each node, its minimum distance from s
d[s] = 0;
p = vector(n, None); // for each node, its parent node
vector S(n, false); // subset of nodes with optimal distance
priority_queue, greater> pq;
pq.push({0, s});
while (not pq.empty()) {
node u = pq.top().second;
pq.pop();
if (not S[u]) {
S[u] = true;
for (Arc a : G[u]) {
weight c = a.first;
node v = a.second;
if (d[v] > d[u] + c) {
d[v] = d[u] + c;
p[v] = u;
pq.push({d[v], v});
} } } } }
```
The cost of Dijkstra's algorithm is $\O(n+m\log m)$ in the worst case.
TBD: Example
TBD: Decidir si `p` i `d` són paràmetres o es retornen amb una `pair`.
## Shortest paths with Bellman–Ford's algorithm
The following code implements Bellman–Ford's algorithm in order to compute the
shortest paths from one source node to all the nodes in a directed graph
with possible negative weights on the arcs but no negative cycles.
The input of `bellman_ford()` is a weighted graph `G` with no negative cycles,
and a source node `s` from `G`. Its output are two vectors `d` and
`p`. For each node `u` in `G`, `d[u]` is the minimum distance from `s` to
`u` (or ∞ if `u` is not reachable from `s`) and `p[u]` is the parent node of
`u`, that is the node from which `u` should be reached in order to get the
minimum distance `d[u]`. We have that `p[u]` is `-1` if `u` in unreachable
from `s` or when `u == s`.
The cost of Bellman–Ford's algorithm is $\O(nm)$ in the worst case.
```
void bellman_ford (const WGraph& G, node s, vector& d, vector& p) {
int n = G.size(); // number of nodes in the graph
d = vector(n, infinity); // for each node, its minimum distance from s
d[x] = 0;
p = vector(n, None); // for each node, its parent node
for (int i = 0; i < n - 1; ++i) {
for (node u = 0; u < n; ++u) {
for (arc a : G[u]) {
weight c = a.first;
node v = a.second;
if (d[v] > d[u] + c) {
d[v] = d[u] + c;
p[v] = u;
} } } } }
```
TBD: Example
TBD: Decidir si `p` i `d` són paràmetres o es retornen amb una `pair`.
## Minimum spanning tree with Prim's algorithm
The following code implements Prims's algorithm in order to compute a minimum
spanning tree of a connected undirected graph with edge weights.
TBD: Decidir què es retorna: el pes de l'arbre?, les arestes de l'arbre?, les
dues coses?. I, llavors, si són paràmetres o retornats.
The input of `prim()` is a connected undirected graph `G` with edge weights.
Its output is a minimum spanning tree of `G`, encoded in a
a vector `p` so that, for each node `u` in `G`, `p[u]` is the parent node of
`u` in the tree (and the tree root has parent `-1`).
The cost of Prim's algorithm is $\O(m\log m)$ in the worst case.
```
weight prim (const Graph& G) {
int n = G.size(); // number of nodes in the graph
weight sum = 0; // sum of the weights of the tree edges
vector S(n, false); // for each node, tells if it has been included in the tree
priority_queue, greater> pq;
pq.push({0, 0});
while (not pq.empty()) {
weight c = pq.top().first;
node u = pq.top().second;
pq.pop();
if (not S[u]) {
sum += c;
S[u] = true;
for (arc a : G[u]) {
node v = a.second;
if (not S[v]) {
pq.push(a);
} } } }
return sum;
}
```
TBD: Example
## Minimum spanning tree with Kruskal's algorithm
The following code implements Kruskal's algorithm in order to compute
the cost of a minimum
spanning tree of a connected undirected graph with edge weights.
TBD: Decidir què es retorna: el pes de l'arbre?, les arestes de l'arbre?, les
dues coses?. I, llavors, si són paràmetres o retornats.
The input of `kruskal()` is a connected undirected graph `G` with edge weights.
The implementation uses [Disjoint sets](/eda/disjoint-sets/index.html).
The cost of Kruskal's algorithm is $\O(m\log m)$ in the worst case.
```
weight kruskal (const Graph& G) {
int n = G.size();
// Sort all edges by their weight
using edge = pair>;
vector edges;
for (node u = 0; u < n; ++u) {
for (arc a : G[u]) {
edges.push_back({a.first, {u, a.second}});
} }
sort(edges.begin(), edges.end());
// Add each edge if it is not creating a cycle
DisjointSets p(n);
weight sum = 0;
for (edge e : edges) {
weight c = e.first;
node u = e.second.first;
node v = e.second.second;
if (p[u] != p[v]) {
p.merge(u, v);
sum += c;
} }
return sum;
}
```
TBD: Example
Lliçons.jutge.org
Jordi Petit
Universitat Politècnica de Catalunya, 2023
Prohibit copiar. Tots els drets reservats. No copy allowed. All rights reserved.
Lliçons.jutge.org