Djustra algorithm learning notes
Djster algorithm is used to solve the shortest path problem. Specifically, it is to solve a directional map (or no figure, no way to have a special case of the map is a point to the shortest path of the remaining points, Since it is solving the shortest path problem, the edges of the drawings described herein have weight. For example, we can use this algorithm to calculate a shortest path in a complex network to another node. The network does not only refers to the Internet, or it can be a traffic network or anything else. Measure, or it is time, money or other concept.
Algorithm narrative:
One Figure G is expressed as a collection of points and edges, assuming that the point set of Figure G is I, the set is E, then g = {i, e}, requires one point O to I in addition to O points except for O points The shortest path of the point, first divide the i, divide all the nodes other than O other other than O A surround set P, and call O as origin, we make a collection of points S, it is used to store node x, x Some of the nodes, the shortest distance of O to X (O- ... -X) has been obtained for the algorithm, and naturally S is an empty collection before the algorithm begins.
There is also a payable concept, how many sides in E, we usually feel that the number of edges is variable, but in fact, we can see the variables in E, we assume Num (i) is The number of I mids, then the number Num (E) of the e) is the square of Num (i), because when the algorithm is implemented, we believe that the points that are connected to each other have become the weight is gigantic. According to the above description, it is known that the original O can "reach" each point X in P in P., only the distance is too "distant", this distance is conceptual infinity.
Description of the algorithm below:
Algorithm purpose: solve the shortest path of the original point O to any peripheral x.
Algorithm step:
1) Locate the minimum of each point in the P to P, and then find O-X minimum;
2) Find the first point S0 to the shortest distance of all points in the set P, after finding the smallest S0-PX0, then we find the shortest distance of all points in the second point S1 set P in the S1, after searching S1- The PX1 is the smallest, so until we found the shortest distance SN-PXM of all points in the final element SN to P in the collection S, where we need to find O-S0-PX0, O-S1-PX1 ... O-SN- The shortest O-Si-PXJ in PXM;
3) Compare the two paths of O-X, O-Si-Pxj, if the former cuts X from P, incorporated into S, if the latter is smaller, remove the PXJ from P, incorporate to S In the middle, it is assumed to be included in this point y, record the minimum of O-Y, and then calculate usage;
4) This step we want to determine if P is empty, if P is ended, if there is an element in P, repeating the upper three steps.
The algorithm will execute when P is empty set, p is empty set represents s = I- {o}; in the above description process, the shortest distance of the elements in O to S has been approved, to this The time S has all the elements except O. Other Point Set I, so the distance from either O to the map has been obtained.
So why the shortest distance is O-X or O-Si-PXJ, not the form of o-pxi-pxj, because if there is such a path, then O-PXi must be less than O-PXi-PXJ, that is Saying O-PXI is the real shortest path, not O-PXI-PXJ, and what does O-PXi mean not to be the same as O-X? This is when I graduated, I suddenly remembered that when I was studying Djuth, I was very sentimental, so I wrote this study notes. I will take this to make up for the university that I have no efforts to learn, and then there is no intention It was found that some people reprinted this article, not ashamed, and they finished.
