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

Категория: Устройства и комплектующие
Нажмите для полного просмотра!
Shortest paths and spanning trees in graphs, слайд №1Shortest paths and spanning trees in graphs, слайд №2Shortest paths and spanning trees in graphs, слайд №3Shortest paths and spanning trees in graphs, слайд №4Shortest paths and spanning trees in graphs, слайд №5Shortest paths and spanning trees in graphs, слайд №6Shortest paths and spanning trees in graphs, слайд №7Shortest paths and spanning trees in graphs, слайд №8Shortest paths and spanning trees in graphs, слайд №9Shortest paths and spanning trees in graphs, слайд №10Shortest paths and spanning trees in graphs, слайд №11Shortest paths and spanning trees in graphs, слайд №12Shortest paths and spanning trees in graphs, слайд №13Shortest paths and spanning trees in graphs, слайд №14Shortest paths and spanning trees in graphs, слайд №15Shortest paths and spanning trees in graphs, слайд №16Shortest paths and spanning trees in graphs, слайд №17Shortest paths and spanning trees in graphs, слайд №18Shortest paths and spanning trees in graphs, слайд №19Shortest paths and spanning trees in graphs, слайд №20Shortest paths and spanning trees in graphs, слайд №21Shortest paths and spanning trees in graphs, слайд №22Shortest paths and spanning trees in graphs, слайд №23
Скачать
Вы можете ознакомиться и скачать презентацию на тему Shortest paths and spanning trees in graphs. Доклад-сообщение содержит 23 слайдов. Презентации для любого класса можно скачать бесплатно. Если материал и наш сайт презентаций Mypresentation Вам понравились – поделитесь им с друзьями с помощью социальных кнопок и добавьте в закладки в своем браузере.

Слайды и текст этой презентации

Слайд 1


Shortest paths and spanning trees in graphs, слайд №1
Описание слайда:

Слайд 2


Shortest paths and spanning trees in graphs Lyzhin Ivan, 2015
Описание слайда:
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...
Описание слайда:
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|)
Описание слайда:
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
Описание слайда:
Trivial implementation

Слайд 6


Implementation with set
Описание слайда:
Implementation with set

Слайд 7


Implementation with priority queue
Описание слайда:
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)
Описание слайда:
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
Описание слайда:
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|)
Описание слайда:
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
Описание слайда:
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.
Описание слайда:
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|)
Описание слайда:
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
Описание слайда:
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|)
Описание слайда:
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
Описание слайда:
Trivial implementation

Слайд 17


Implementation with DSU
Описание слайда:
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:
Описание слайда:
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
Описание слайда:
Implementation

Слайд 20


Path compression When we go up, we can remember root of set for each vertex in path
Описание слайда:
Path compression When we go up, we can remember root of set for each vertex in path

Слайд 21


Union by size
Описание слайда:
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
Описание слайда:
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
Описание слайда:
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

Скачать

Похожие презентации
Mypresentation.ru
Загрузить презентацию