4 years ago (2015-07-05)  11
post score 0 times, average 0.0
[Slideup] Catalog

## Dijkstra algorithm

### 1. Definition overview

The Dijkstra algorithm is a typical single-source shortest path algorithm that calculates the shortest path from one node to all other nodes.The main feature is to extend from the starting point to the outer layer until it reaches the end point.Dijkstra's algorithm is a very representative shortest path algorithm. It has been introduced as a basic content in many professional courses, such as data structure, graph theory, operations research and so on.Note that this algorithm requires that there are no negative edges in the graph. Problem Description: In the undirected graph G=(V,E), assuming that the length of each edge E[i] is w[i], find the shortest path from the vertex V0 to the remaining points.(single source shortest path)

### 2. Algorithm description

1) Algorithm idea: Let G = (V, E) be a weighted directed graph. Divide the vertex set V in the graph into two groups. The first group is the set of vertices for which the shortest path has been obtained (indicated by S, initially There is only one source point in S. After each shortest path is obtained, it will be added to the set S until all the vertices are added to S. The algorithm is complete. The second set is the set of vertices whose other undefined shortest paths are determined. (Indicated by U), add the vertices of the second group to S in ascending order of the length of the shortest path.In the joining process, the length of the shortest path from the source point v to the vertices in S is always not greater than the shortest path length from any source point v to any vertex in U.In addition, each vertex corresponds to a distance. The distance of the vertex in S is the shortest path length from v to this vertex, and the distance of the vertex in U is from v to this vertex. Only the vertices in S are intermediate vertices. The shortest path length. 2) Algorithm steps: a. Initially, S contains only the source point, ie S={v}, and the distance of v is 0.U contains other vertices besides v, that is: U={other vertices}. If v has edges with vertex u in U, then <u,v> has normal weight, if u is not an adjacency point of v, then The <u,v> weight is ∞. b. Select a vertex k with the smallest distance v from U, and add k to S (the selected distance is the shortest path length from v to k). c. Using k as the midpoint of new consideration, modify the distance of each vertex in U; ​​if the distance from source v to vertex u (passing vertex k) is shorter than the original distance (not passing vertex k), then modify the vertex u The distance value, the distance of the vertex k of the modified distance value plus the weight on the edge. d. Repeat steps b and c until all vertices are included in S. Perform the animation process as shown below ### 4. Algorithm example

First give an undirected graph Find the single-source shortest path starting from A using the Dijkstra algorithm ## Floyd algorithm

### 1. Definition overview

The Floyd-Warshall algorithm (Floyd-Warshall algorithm) is an algorithm that solves the shortest path between any two points, can correctly handle the shortest path problem of directed graphs or negative weights, and is also used to calculate the transitive closure of directed graphs. package.The time complexity of the Floyd-Warshall algorithm is O(N3) and the spatial complexity is O(N2).

### 2. Algorithm description

1) The idea of ​​the algorithm: The Floyd algorithm is a classic dynamic programming algorithm.To describe it in popular language, our goal first is to find the shortest path from point i to point j.From the point of view of dynamic planning, we need to re-interpret this goal. (This interpretation is the essence of the most creative of dynamic planning.) The shortest path from any node i to any node j is nothing more than 2 possibilities. 1 is directly from i to j, 2 is from i through several nodes k to j.Therefore, we assume that Dis(i,j) is the distance of the shortest path from node u to node v. For each node k, we check Dis(i,k) + Dis(k,j) < Dis(i,j) If it is true, if it is true, prove that the path from i to k to j is shorter than the path of i directly to j, we set Dis(i,j) = Dis(i,k) + Dis(k,j), For one thing, when we traverse all nodes k, the distance recorded in Dis(i,j) is the shortest path from i to j. 2). Algorithm Description: a. Start from any single-sided path.The distance between all two points is the weight of the edge. If there is no edge connection between the two points, the weight is infinite. b. For each pair of vertices u and v, see if there is a vertex w that makes the path from u to w to v shorter than the known path.If it is updated it. 3). Floyd algorithm process matrix calculation ---- Cross method method: two lines, starting from the upper left corner to the lower right corner as given by the matrix, where matrix A is the adjacency matrix, and the matrix Path records u The corresponding calculation method for the point that the shortest path between the two points must pass is as follows: The last A3 is the result

### 3 algorithm code to achieve

Algorithm time complexity: O(n3) ### 注册 TW