Что такое findslide.org?

FindSlide.org - это сайт презентаций, докладов, шаблонов в формате PowerPoint.


Для правообладателей

Обратная связь

Email: Нажмите что бы посмотреть 

Яндекс.Метрика

Презентация на тему Shortest paths and spanning trees in graphs

Содержание

Shortest paths and spanning trees in graphsLyzhin Ivan, 2015
Shortest paths and spanning trees in graphsLyzhin Ivan, 2015 Shortest path problemThe problem of finding a path between two vertices such Dijkstra algorithmThere are two sets of vertices – visited and unvisited.For visited Trivial implementationvoid dijkstra(int s){vector mark(n, false);vector d(n, INF);d[s] = 0;for (int i Implementation with setvoid dijkstra(int s){set q; //(dist[u], u)vector dist(n, INF);dist[s] = 0;q.insert(mp(0, Implementation with priority queuevoid dijkstra(int s){priority_queue q; //(dist[u], u)vector dist(n, INF);dist[s] = Floyd–Warshall algorithmInitially, dist[u][u]=0 and for each edge (u, v): dist[u][v]=weight(u, v)On iteration Implementationvoid floyd_warshall(){vector dist(n, vector(n, INF));for (int i = 0; i < n; Bellman–Ford algorithm|V|-1 iterations, on each we try relax distance with all edges.If Implementationvoid bellman_ford(int s){vector dist(n, INF);dist[s] = 0;for (int i = 0; i Minimal spanning treeA spanning tree T of an undirected graph G is Prim’s algorithmInitialize a tree with a single vertex, chosen arbitrarily from the Implementationvoid prima(){set q; //(dist[u], u)vector dist(n, INF);dist[0] = 0;q.insert(mp(0, 0));while (!q.empty()){int cur Kruskal’s algorithmCreate a forest F (a set of trees), where each vertex Trivial implementationvoid trivial_kruskal(){vector color(n);for (int i = 0; i < n; ++i)	color[i] 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 U, Implementationstruct DSU{vector p;DSU(int n) {p.resize(n);for (int i = 0; i < n; Path compressionWhen we go up, we can remember root of set for Union by sizeint unionSets(int u, int v){int pu = findSet(u);int pv = Linkshttps://en.wikipedia.org/wiki/Dijkstra%27s_algorithmhttps://en.wikipedia.org/wiki/Floyd–Warshall_algorithmhttps://en.wikipedia.org/wiki/Bellman–Ford_algorithmhttps://en.wikipedia.org/wiki/Kruskal%27s_algorithmhttps://en.wikipedia.org/wiki/Prim%27s_algorithmhttps://en.wikipedia.org/wiki/Disjoint-set_data_structurehttp://e-maxx.ru/algo/topological_sort Home taskhttp://ipc.susu.ac.ru/210-2.html?problem=1903http://ipc.susu.ac.ru/210-2.html?problem=186http://acm.timus.ru/problem.aspx?space=1&num=1982http://acm.timus.ru/problem.aspx?space=1&num=1119http://acm.timus.ru/problem.aspx?space=1&num=1210http://acm.timus.ru/problem.aspx?space=1&num=1272
Слайды презентации

Слайд 2 Shortest paths and spanning trees in graphs
Lyzhin Ivan,

Shortest paths and spanning trees in graphsLyzhin Ivan, 2015

2015


Слайд 3 Shortest path problem
The problem of finding a path

Shortest path problemThe problem of finding a path between two vertices

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 –

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

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]

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

= 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;

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

//(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

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

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,

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

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 (int i

Implementationvoid floyd_warshall(){vector dist(n, vector(n, INF));for (int i = 0; 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

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

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;
for (int

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

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

Minimal spanning treeA spanning tree T of an undirected graph G

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,

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

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,

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

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

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

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 = 0;

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

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 :

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);}}

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

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

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 =

Implementationstruct DSU{vector p;DSU(int n) {p.resize(n);for (int i = 0; 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

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

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

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

= 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



Linkshttps://en.wikipedia.org/wiki/Dijkstra%27s_algorithmhttps://en.wikipedia.org/wiki/Floyd–Warshall_algorithmhttps://en.wikipedia.org/wiki/Bellman–Ford_algorithmhttps://en.wikipedia.org/wiki/Kruskal%27s_algorithmhttps://en.wikipedia.org/wiki/Prim%27s_algorithmhttps://en.wikipedia.org/wiki/Disjoint-set_data_structurehttp://e-maxx.ru/algo/topological_sort

  • Имя файла: shortest-paths-and-spanning-trees-in-graphs.pptx
  • Количество просмотров: 124
  • Количество скачиваний: 0