Floyd– Warshall algorithm презентация

Floyd–Warshall algorithm
 Floyd–Warshall algorithm is an algorithm for finding shortest pathsPrior to the first iteration of the outer loop, labeled k = 0 above,1. Prove that of six people, you can choose either three4. Visit all the cells of the chessboard 8х8 by theSelection sort is an in-place comparison sort. The algorithm finds theRadix sort is an algorithm that sorts numbers by processing individual



Слайды и текст этой презентации
Слайд 1
Описание слайда:
Floyd–Warshall algorithm Floyd–Warshall algorithm is an algorithm for finding shortest paths in a weighted graph with positive or negative edge weights (but with no negative cycles/ Pseudocode for this basic version follows: 1 let dist be a |V| × |V| array of minimum distances initialized to ∞ (infinity) 2 for each edge (u,v) 3 dist[u][v] ← w(u,v) // the weight of the edge (u,v) 4 for each vertex v 5 dist[v][v] ← 0 6 for k from 1 to |V| 7 for i from 1 to |V| 8 for j from 1 to |V| 9 if dist[i][j] > dist[i][k] + dist[k][j] 10 dist[i][j] ← dist[i][k] + dist[k][j] 11 end if


Слайд 2
Описание слайда:

Слайд 3
Описание слайда:
Prior to the first iteration of the outer loop, labeled k = 0 above, the only known paths correspond to the single edges in the graph. Prior to the first iteration of the outer loop, labeled k = 0 above, the only known paths correspond to the single edges in the graph. At k = 1, paths that go through the vertex 1 are found: in particular, the path [2,1,3] is found, replacing the path [2,3] which has fewer edges but is longer (in terms of weight). At k = 2, paths going through the vertices {1,2} are found. The red and blue boxes show how the path [4,2,1,3] is assembled from the two known paths [4,2] and [2,1,3] encountered in previous iterations, with 2 in the intersection. The path [4,2,3] is not considered, because [2,1,3] is the shortest path encountered so far from 2 to 3. At k = 3, paths going through the vertices {1,2,3} are found. Finally, at k = 4, all shortest paths are found.

Слайд 4
Описание слайда:

Слайд 5
Описание слайда:

Слайд 6
Описание слайда:

Слайд 7
Описание слайда:

Слайд 8
Описание слайда:

Слайд 9
Описание слайда:

Слайд 10
Описание слайда:

Слайд 11
Описание слайда:

Слайд 12
Описание слайда:
1. Prove that of six people, you can choose either three pairwise acquaintances, or three pairwise unfamiliar ones. 1. Prove that of six people, you can choose either three pairwise acquaintances, or three pairwise unfamiliar ones. 2. In the graph in each vertex includes three edges. Prove that there is at least one cycle in the graph. 3. On the plane, 100 circles are given, constituting a connected (i.e., non-disintegrating) figure. Prove that this figure can be drawn without taking the pencil from the paper and not drawing the same line twice. Example of figure, that we can’t draw under this condition:

Слайд 13
Описание слайда:
4. Visit all the cells of the chessboard 8х8 by the chess knight , having visited each one once. 4. Visit all the cells of the chessboard 8х8 by the chess knight , having visited each one once. 5. What is the greatest number of chess queens that can be placed on an 8x8 board, so that no two are on the same horizontal, vertical or diagonal? 6. In the company of 2n + 1 people for any n people there is a different person from them who is familiar with each of them. Prove that in this company there is a person who knows everyone. 7. Among the participants of the conference, everyone has at least one friend. Prove that the participants can be distributed in two rooms so that each participant has a friend in the other room.

Слайд 14
Описание слайда:

Слайд 15
Описание слайда:

Слайд 16
Описание слайда:
Selection sort is an in-place comparison sort. The algorithm finds the minimum value, swaps it with the value in the first position, and repeats these steps for the remainder of the list. Selection sort is noted for its simplicity, and also has performance advantages over more complicated algorithms in certain situations. Selection sort is an in-place comparison sort. The algorithm finds the minimum value, swaps it with the value in the first position, and repeats these steps for the remainder of the list. Selection sort is noted for its simplicity, and also has performance advantages over more complicated algorithms in certain situations.

Слайд 17
Описание слайда:

Слайд 18
Описание слайда:
Radix sort is an algorithm that sorts numbers by processing individual digits. n numbers consisting of k digits each are sorted in O(n · k) time. Radix sort can process digits of each number either starting from the least significant digit or starting from the most significant digit. The algorithm first sorts the list by the least significant digit while preserving their relative order using a stable sort. Then it sorts them by the next digit, and so on from the least significant to the most significant, ending up with a sorted list. Radix sort is an algorithm that sorts numbers by processing individual digits. n numbers consisting of k digits each are sorted in O(n · k) time. Radix sort can process digits of each number either starting from the least significant digit or starting from the most significant digit. The algorithm first sorts the list by the least significant digit while preserving their relative order using a stable sort. Then it sorts them by the next digit, and so on from the least significant to the most significant, ending up with a sorted list.

Слайд 19
Описание слайда:

Слайд 20
Описание слайда:

Слайд 21
Описание слайда:

Слайд 22
Описание слайда:


Скачать презентацию на тему Floyd– Warshall algorithm можно ниже:

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