Презентация Shortest paths and spanning trees in graphs онлайн
На нашем сайте вы можете скачать и просмотреть онлайн доклад-презентацию на тему Shortest paths and spanning trees in graphs абсолютно бесплатно. Урок-презентация на эту тему содержит всего 23 слайда. Все материалы созданы в программе PowerPoint и имеют формат ppt или же pptx. Материалы и темы для презентаций взяты из открытых источников и загружены их авторами, за качество и достоверность информации в них администрация сайта не отвечает, все права принадлежат их создателям. Если вы нашли то, что искали, отблагодарите авторов - поделитесь ссылкой в социальных сетях, а наш сайт добавьте в закладки.
Оцените презентацию от 1 до 5 баллов!
- Тип файла:ppt / pptx (powerpoint)
- Всего слайдов:23 слайда
- Для класса:1,2,3,4,5,6,7,8,9,10,11
- Размер файла:438.11 kB
- Просмотров:57
- Скачиваний:0
- Автор:неизвестен
Слайды и текст к этой презентации:
№1 слайд
Содержание слайда:
№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
№6 слайд
Содержание слайда: Implementation with set
№7 слайд
Содержание слайда: Implementation with priority queue
№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
№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
№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
№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
№17 слайд
Содержание слайда: Implementation with DSU
№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
№20 слайд
Содержание слайда: Path compression
When we go up, we can remember root of set for each vertex in path
№21 слайд
Содержание слайда: Union by size
№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
№23 слайд
Содержание слайда: Home task
http://ipc.susu.ac.ru/210-2.html?problem=1903
http://ipc.susu.ac.ru/210-2.html?problem=186
http://acm.timus.ru/problem.aspx?space=1&num=1982
http://acm.timus.ru/problem.aspx?space=1&num=1119
http://acm.timus.ru/problem.aspx?space=1&num=1210
http://acm.timus.ru/problem.aspx?space=1&num=1272
Скачать все slide презентации Shortest paths and spanning trees in graphs одним архивом:
