Shortest paths and spanning trees in graphs

Сентябрь 7, 2022

Главная
Алгебра
Shortest paths and spanning trees in graphs

Содержание

2. Shortest paths and spanning trees in graphs Lyzhin Ivan, 2015
3. Shortest path problem The problem of finding a path between two vertices such that the sum
4. Dijkstra algorithm There are two sets of vertices – visited and unvisited. For visited vertices we
5. Trivial implementation void dijkstra(int s) { vector mark(n, false); vector d(n, INF); d[s] = 0; for
6. Implementation with set void dijkstra(int s) { set > q; //(dist[u], u) vector dist(n, INF); dist[s]
7. Implementation with priority queue void dijkstra(int s) { priority_queue > q; //(dist[u], u) vector dist(n, INF);
8. Floyd–Warshall algorithm Initially, dist[u][u]=0 and for each edge (u, v): dist[u][v]=weight(u, v) On iteration k we
9. Implementation void floyd_warshall() { vector > dist(n, vector (n, INF)); for (int i = 0; i
10. Bellman–Ford algorithm |V|-1 iterations, on each we try relax distance with all edges. If we can
11. Implementation void bellman_ford(int s) { vector dist(n, INF); dist[s] = 0; for (int i = 0;
12. Minimal spanning tree A spanning tree T of an undirected graph G is a subgraph that
13. Prim’s algorithm Initialize a tree with a single vertex, chosen arbitrarily from the graph. Grow the
14. Implementation void prima() { set > q; //(dist[u], u) vector dist(n, INF); dist[0] = 0; q.insert(mp(0,
15. Kruskal’s algorithm Create a forest F (a set of trees), where each vertex in the graph
16. Trivial implementation void trivial_kruskal() { vector color(n); for (int i = 0; i color[i] = i;
17. Implementation with DSU void kruskal() { DSU dsu(n); sort(edges.begin(), edges.end()); for(auto e : edges) if(dsu.findSet(e.u)!=dsu.findSet(e.v)) {
18. Disjoint-set-union (DSU) Two main operations: Find(U) – return root of set, which contains U, complexity O(1)
19. Implementation struct DSU { vector p; DSU(int n) { p.resize(n); for (int i = 0; i
20. Path compression When we go up, we can remember root of set for each vertex in
21. Union by size int unionSets(int u, int v) { int pu = findSet(u); int pv =
22. Links https://en.wikipedia.org/wiki/Dijkstra%27s_algorithm https://en.wikipedia.org/wiki/Floyd–Warshall_algorithm https://en.wikipedia.org/wiki/Bellman–Ford_algorithm https://en.wikipedia.org/wiki/Kruskal%27s_algorithm https://en.wikipedia.org/wiki/Prim%27s_algorithm https://en.wikipedia.org/wiki/Disjoint-set_data_structure http://e-maxx.ru/algo/topological_sort
24. Скачать презентацию

Слайд 2

Shortest paths and spanning trees in graphs
Lyzhin Ivan, 2015

Слайд 3

Shortest path problem
The problem of finding a path between two vertices

such that the sum of the weights of edges in path is minimized.
Known algorithms:
Dijkstra
Floyd–Warshall
Bellman–Ford
and so on...

Слайд 4

Dijkstra algorithm
There are two sets of vertices – visited and unvisited.
For

visited vertices we know minimal distance from start. For unvisited vertices we know some distance which can be not minimal.
Initially, all vertices are unvisited and distance to each vertex is INF. Only distance to start node is equal 0.
On each step choose unvisited vertex with minimal distance. Now it’s visited vertex. And try to relax distance of neighbors.
Complexity: trivial implementation O(|V|^2+|E|)
implementation with set O(|E|log|V|+|V|log|V|)

Слайд 5

Trivial implementation
void dijkstra(int s)
{
vector mark(n, false);
vector d(n, INF);
d[s] = 0;
for (int

i = 0; i < n; ++i)
{
int u = -1;
for (int j = 0; j < n; ++j)
if (!mark[j] && (u == -1 || d[j] < d[u]))
u = j;
mark[u] = true;
for (v - сосед u)
d[v] = min(d[v], d[u] + weight(uv));
}
}

Слайд 6

Implementation with set
void dijkstra(int s)
{
set > q; //(dist[u], u)
vector dist(n,

INF);
dist[s] = 0;
q.insert(mp(0, s));
while(!q.empty())
{
int cur = q.begin()->second;
q.erase(q.begin());
for(auto e : g[cur])
if(dist[e.first] > dist[cur]+e.second)
{
q.erase(mp(dist[e.first], e.first));
dist[e.first] = dist[cur] + e.second;
q.insert(mp(dist[e.first], e.first));
}
}
}

Слайд 7

$Implementation with priority queue void dijkstra(int s) { priority_queue > q;$

Implementation with priority queue
void dijkstra(int s)
{
priority_queue > q; //(dist[u], u)
vector

dist(n, INF);
dist[s] = 0;
q.push(mp(0, s));
while(!q.empty())
{
int cur = q.top().second;
int cur_d = -q.top().first; q.pop();
if(cur_d > dist[cur]) continue;
for(auto e : g[cur])
if(dist[e.first] > dist[cur]+e.second)
{
dist[e.first] = dist[cur] + e.second;
q.push(mp(-dist[e.first], e.first));
}
}
}

Слайд 8

Floyd–Warshall algorithm
Initially, dist[u][u]=0 and for each edge (u, v): dist[u][v]=weight(u, v)
On

iteration k we let use vertex k as intermediate vertex and for each pair of vertices we try to relax distance.
dist[u][v] = min(dist[u][v], dist[u][k]+dist[k][v])
Complexity: O(|V|^3)

Слайд 9

$Implementation void floyd_warshall() { vector > dist(n, vector (n, INF)); for$

Implementation
void floyd_warshall()
{
vector > dist(n, vector(n, INF));
for (int i = 0; i

< n; ++i)
dist[i][i] = 0;
for (int i = 0; i < n; ++i)
for (auto e : g[i])
dist[i][e.first] = e.second;
for (int k = 0; k < n; ++k)
for (int i = 0; i < n; ++i)
for (int j = 0; j < n; ++j)
dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]);
}

Слайд 10

Bellman–Ford algorithm
|V|-1 iterations, on each we try relax distance with all

edges.
If we can relax distance on |V| iteration then negative cycle exists in graph
Why |V|-1 iterations? Because the longest way without cycles from one node to another one contains no more |V|-1 edges.
Complexity O(|V||E|)

Слайд 11

$Implementation void bellman_ford(int s) { vector dist(n, INF); dist[s] = 0;$

Implementation
void bellman_ford(int s)
{
vector dist(n, INF);
dist[s] = 0;
for (int i = 0;

i < n - 1; ++i)
for (auto e : edges)
dist[e.v] = min(dist[e.v], dist[e.u] + e.weight);
for (auto e : edges)
if (dist[e.v] > dist[e.u] + e.weight)
cout << "Negative cycle!" << endl;
}

Слайд 12

Minimal spanning tree
A spanning tree T of an undirected graph G

is a subgraph that includes all of the vertices of G that is a tree.
A minimal spanning tree is a spanning tree and sum of weights is minimized.

Слайд 13

Prim’s algorithm
Initialize a tree with a single vertex, chosen arbitrarily from

the graph.
Grow the tree by one edge: of the edges that connect the tree to vertices not yet in the tree, find the minimum-weight edge, transfer it to the tree and try to relax distance for neighbors.
Repeat step 2 (until all vertices are in the tree).
Complexity: trivial implementation O(|V|^2+|E|)
implementation with set O(|E|log|V|+|E|)

Слайд 14

Implementation
void prima()
{
set > q; //(dist[u], u)
vector dist(n, INF);
dist[0] = 0;
q.insert(mp(0,

0));
while (!q.empty())
{
int cur = q.begin()->second;
q.erase(q.begin());
for (auto e : g[cur])
if (dist[e.first] > e.second)
{
q.erase(mp(dist[e.first], e.first));
dist[e.first] = e.second;
q.insert(mp(dist[e.first], e.first));
}
}
}

Слайд 15

Kruskal’s algorithm
Create a forest F (a set of trees), where each

vertex in the graph is a separate tree
Create a set S containing all the edges in the graph
While S is nonempty and F is not yet spanning:
remove an edge with minimum weight from S
if the removed edge connects two different trees then add it to the forest F, combining two trees into a single tree
Complexity: trivial O(|V|^2+|E|log|E|)
with DSU O(|E|log|E|)

Слайд 16

$Trivial implementation void trivial_kruskal() { vector color(n); for (int i =$

Trivial implementation
void trivial_kruskal()
{
vector color(n);
for (int i = 0; i < n;

++i)
color[i] = i;
sort(edges.begin(), edges.end());
for(auto e : edges)
if(color[e.u]!=color[e.v])
{
add_to_spanning_tree(e);
int c1 = color[e.u];
int c2 = color[e.v];
for (int i = 0; i < n; ++i)
if (color[i] == c1)
color[i] = c2;
}
}

Слайд 17

Implementation with DSU
void kruskal()
{
DSU dsu(n);
sort(edges.begin(), edges.end());
for(auto e : edges)
if(dsu.findSet(e.u)!=dsu.findSet(e.v))
{
add_to_spanning_tree(e);
dsu.unionSets(e.u, e.v);
}
}

Слайд 18

Disjoint-set-union (DSU)
Two main operations:
Find(U) – return root of set, which contains

U, complexity O(1)
Union(U, V) – join sets, which contain U and V, complexity O(1)
After creating DSU:
After some operations:

Слайд 19

Implementation
struct DSU
{
vector p;
DSU(int n) {
p.resize(n);
for (int i = 0; i <

n; ++i)
p[i] = i;
}
int find(int u) {
return u == p[u] ? u : find(p[u]);
}
void merge(int u, int v) {
int pu = find(u);
int pv = find(v);
p[pv] = pu;
}
};

Слайд 20

Path compression
When we go up, we can remember root of set

for each vertex in path

int findSet(int u)
{
return u == p[u] ? u : p[u] = findSet(p[u]);
}

Слайд 21

Union by size
int unionSets(int u, int v)
{
int pu = findSet(u);
int pv

= findSet(v);
if (pu == pv) return;
if (sizes[pu] < sizes[pv])
swap(pu, pv);
p[pv] = pu;
sizes[pu] += sizes[pv];
}

DSU(int size)
{
p.resize(size);
sizes.resize(size, 1);
for (int i = 0; i < size; ++i)
p[i] = i;
}

Слайд 22

Links
https://en.wikipedia.org/wiki/Dijkstra%27s_algorithm
https://en.wikipedia.org/wiki/Floyd–Warshall_algorithm
https://en.wikipedia.org/wiki/Bellman–Ford_algorithm
https://en.wikipedia.org/wiki/Kruskal%27s_algorithm
https://en.wikipedia.org/wiki/Prim%27s_algorithm
https://en.wikipedia.org/wiki/Disjoint-set_data_structure
http://e-maxx.ru/algo/topological_sort

Shortest paths and spanning trees in graphs

Содержание

Shortest paths and spanning trees in graphsLyzhin Ivan, 2015

Shortest path problemThe problem of finding a path between two vertices

Dijkstra algorithmThere are two sets of vertices – visited and unvisited.For

Trivial implementationvoid dijkstra(int s){vector mark(n, false);vector d(n, INF);d[s] = 0;for (int

Implementation with setvoid dijkstra(int s){set > q; //(dist[u], u)vector dist(n,

Implementation with priority queuevoid dijkstra(int s){priority_queue > q; //(dist[u], u)vector

Floyd–Warshall algorithmInitially, dist[u][u]=0 and for each edge (u, v): dist[u][v]=weight(u, v)On

Implementationvoid floyd_warshall(){vector > dist(n, vector(n, INF));for (int i = 0; i

Bellman–Ford algorithm|V|-1 iterations, on each we try relax distance with all

Implementationvoid bellman_ford(int s){vector dist(n, INF);dist[s] = 0;for (int i = 0;

Minimal spanning treeA spanning tree T of an undirected graph G

Prim’s algorithmInitialize a tree with a single vertex, chosen arbitrarily from

Implementationvoid prima(){set > q; //(dist[u], u)vector dist(n, INF);dist[0] = 0;q.insert(mp(0,

Kruskal’s algorithmCreate a forest F (a set of trees), where each

Trivial implementationvoid trivial_kruskal(){vector color(n);for (int i = 0; i < n;

Implementation with DSUvoid kruskal(){DSU dsu(n);sort(edges.begin(), edges.end());for(auto e : edges)if(dsu.findSet(e.u)!=dsu.findSet(e.v)){add_to_spanning_tree(e);dsu.unionSets(e.u, e.v);}}

Disjoint-set-union (DSU)Two main operations:Find(U) – return root of set, which contains

Implementationstruct DSU{vector p;DSU(int n) {p.resize(n);for (int i = 0; i <

Path compressionWhen we go up, we can remember root of set

Union by sizeint unionSets(int u, int v){int pu = findSet(u);int pv

Похожие презентации