CN108449268B - Point-to-point shortest path computing system in peer-to-peer network - Google Patents
Point-to-point shortest path computing system in peer-to-peer network Download PDFInfo
- Publication number
- CN108449268B CN108449268B CN201810215767.4A CN201810215767A CN108449268B CN 108449268 B CN108449268 B CN 108449268B CN 201810215767 A CN201810215767 A CN 201810215767A CN 108449268 B CN108449268 B CN 108449268B
- Authority
- CN
- China
- Prior art keywords
- path
- node
- point
- shortest path
- given
- Prior art date
- Legal status (The legal status is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the status listed.)
- Active
Links
- 238000004364 calculation method Methods 0.000 claims abstract description 53
- 238000004422 calculation algorithm Methods 0.000 claims abstract description 28
- 238000000034 method Methods 0.000 claims abstract description 28
- 239000000284 extract Substances 0.000 claims abstract description 10
- 230000008569 process Effects 0.000 claims description 21
- 238000011156 evaluation Methods 0.000 claims description 20
- 238000012545 processing Methods 0.000 claims description 11
- 238000010586 diagram Methods 0.000 description 12
- 238000004590 computer program Methods 0.000 description 6
- 230000006870 function Effects 0.000 description 6
- 238000004891 communication Methods 0.000 description 4
- 239000010410 layer Substances 0.000 description 4
- 238000012986 modification Methods 0.000 description 3
- 230000004048 modification Effects 0.000 description 3
- 101100352419 Pithecopus hypochondrialis psn1 gene Proteins 0.000 description 1
- 230000009286 beneficial effect Effects 0.000 description 1
- 238000005516 engineering process Methods 0.000 description 1
- 238000004519 manufacturing process Methods 0.000 description 1
- 230000006855 networking Effects 0.000 description 1
- 230000004044 response Effects 0.000 description 1
- 239000002356 single layer Substances 0.000 description 1
- 230000003068 static effect Effects 0.000 description 1
Images
Classifications
-
- H—ELECTRICITY
- H04—ELECTRIC COMMUNICATION TECHNIQUE
- H04L—TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION
- H04L67/00—Network arrangements or protocols for supporting network services or applications
- H04L67/01—Protocols
- H04L67/10—Protocols in which an application is distributed across nodes in the network
- H04L67/104—Peer-to-peer [P2P] networks
-
- H—ELECTRICITY
- H04—ELECTRIC COMMUNICATION TECHNIQUE
- H04L—TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION
- H04L45/00—Routing or path finding of packets in data switching networks
- H04L45/12—Shortest path evaluation
Landscapes
- Engineering & Computer Science (AREA)
- Computer Networks & Wireless Communication (AREA)
- Signal Processing (AREA)
- Data Exchanges In Wide-Area Networks (AREA)
Abstract
The invention discloses a point-to-point shortest path calculation system in a peer-to-peer network, which obtains starting point information and end point information of a shortest path between a given starting point S and a given end point E to be calculated in the peer-to-peer network through an information acquisition module; the path calculation module extracts n different nodes Mi which may pass between the given starting point S and the given end point E in the network link according to the starting point information and the end point information acquired by the information acquisition module; respectively calculating a first shortest path between the given starting point S and a node Mi and a second shortest path between the node Mi and the given end point E, thereby obtaining a shortest path between the given starting point S and the given end point E; the method has the advantages of simplifying the shortest path algorithm, avoiding the problem of overlarge calculation complexity caused by a calculation mode of acquiring the point-to-point shortest path by adopting a large number of complex algorithms, improving the calculation efficiency and saving the calculation resources and the calculation time.
Description
Technical Field
The invention relates to the technical field of internet, in particular to a point-to-point shortest path computing system in a peer-to-peer network.
Background
The problem of the shortest path between two points is a classic algorithm problem and also an important subproblem in many practical applications; for example, the method has wide application in the aspects of electronic navigation, city planning, computer network and communication, intelligent traffic systems, traffic tourism, geographic information systems, engineering technology and the like. In particular, for example, in a communication network, when one user communicates with another user, it is necessary to find the shortest communication path so as to minimize the communication delay and the consumption. However, in the prior art, most of the correlation schemes for calculating the shortest path between two points are complex, and a large amount of computing resources are consumed.
Disclosure of Invention
The invention provides a point-to-point shortest path computing system in a peer-to-peer network, which is used for simplifying a shortest path algorithm, improving the computing efficiency of the shortest path and saving computing resources.
The invention provides a point-to-point shortest path computing system in a peer-to-peer network, which comprises: the system comprises an information acquisition module and a path calculation module; wherein:
the information acquisition module is used for: acquiring starting point information and end point information of a given starting point S and a given end point E which need to calculate the shortest path in a peer-to-peer network;
the path computation module is configured to: extracting n different nodes Mi which may pass from the given starting point S to the given end point E in a network link according to the starting point information and the end point information acquired by the information acquisition module; wherein i is more than or equal to 1 and less than or equal to n;
and respectively calculating a first shortest path between the given starting point S and the node Mi and a second shortest path between the node Mi and the given end point E, and determining the shortest path between the given starting point S and the given end point E according to the first shortest path and the second shortest path.
Preferably, the path computation module extracts n different nodes Mi that may pass through from the given starting point S to the given end point E in the network link, including:
the path calculation module randomly acquires h primary selection paths from the given starting point S to the given end point E according to the starting point information and the end point information, respectively calculates evaluation values of the primary selection paths, and selects part of nodes from the nodes passed by the primary selection path with the highest evaluation value as n different nodes Mi which may pass from the given starting point S to the given end point E; in the initial selection path with the highest evaluation value, the farther the Mi is from the given starting point S, the larger i is;
wherein, calculating the evaluation value of the initial selection path comprises:
determining m different paths passing through in the middle of the current primary selection path in sequenceT is more than or equal to 1 and less than or equal to m, and determining the edge weight w between two adjacent nodes contained in the primary selection pathj，wj>J is more than or equal to 0 and less than or equal to m;
determining that the edge weight between two adjacent nodes contained in the primary selection path is smaller than a preset standard edge weight wsThe edge weight p of (a);
calculating an evaluation value S of the primary selection path:
Preferably, the path calculation module calculates n sets of paths from the given starting point S to the node Mi and paths from the node Mi to the given end point E at the same time, to obtain 2n segment path results;
and respectively finding out the shortest path from the given starting point S to the node Mi and from the node Mi to the given end point E from the 2n path results to obtain the shortest path from the given starting point S to the given end point E.
Preferably, the path computation module computes n groups of different paths by using a multi-core asynchronous parallel algorithm to obtain 2 n-segment path results.
Preferably, the path calculation module calculates n sets of paths between the given starting point S and the node Mi and paths between the node Mi and the given end point E, and extracts local optimal sub-paths between the given starting point S and the node Mi and between the node Mi and the given end point E for combination to obtain the shortest path between the given starting point S and the given end point E.
Preferably, the path calculation module finds path intersection points from the 2n segment path results, and if more than one path is identified between every two intersection points, calculates and obtains a shortest path between the two intersection points, and finally obtains a shortest path from the given starting point S to the given end point E.
Preferably, the path calculation module searches and acquires a shortest path between two intersection points by using an a-in-euclidean distance algorithm.
Preferably, if the path calculation module identifies that there is more than one path between each two intersection points, only the shortest path between the two intersection points is reserved, and other path information is deleted.
Preferably, if the path calculation module identifies that there is more than one path between two intersection points and there are other nodes between the two intersection points, the path calculation module calculates and acquires the shortest path between the two intersection points by using dijkstra's algorithm.
Preferably, the calculating a first shortest path between the given starting point S and the node Mi and a second shortest path between the node Mi and the given end point E, respectively, and determining a shortest path between the given starting point S and the given end point E according to the first shortest path and the second shortest path includes:
selecting the last node Mn in all nodes Mi, taking u as 0 as a starting point, setting the step length of u as 1, circularly judging whether a node Mn-u is provided with a first mark, determining a first shortest path Psn-u between the given starting point S and the node Mn-u when the node Mn-u does not have the first mark, adding the first mark to the node Mn-u, and judging whether a node Na through which the first shortest path Psn-u passes is one of the nodes Mi; when a node Na is one node Mb in a node Mi, adding a first flag to the node Mb, and taking a path from the given starting point S to the node Na in the first shortest path Psn-u as a first shortest path Psb from the given starting point S to the node Mb; then, adding one to u, and repeatedly executing the process of judging whether the Mn-u is provided with the first mark until u is equal to n-1;
when the node Mn-u is provided with a first mark, performing addition processing on u and continuously and circularly performing the process of judging whether the node Mn-u is provided with the first mark until u is equal to n-1;
selecting a first node M1 from all nodes Mi, circularly judging whether a node M1+ v is provided with a second mark or not by taking v as a starting point and the step length of v as 1, determining a second shortest path P1+ ve between the node M1+ v and the given terminal E when the node M1+ v has no second mark, adding a second mark to the node M1+ v, and judging whether a node Nc through which the second shortest path P1+ ve passes is one of the nodes Mi or not; when the node Nc is one node Md in the nodes Mi, adding a second label to the node Md, and taking a path between the node Nc and the given end point E in the second shortest path P1+ ve as a second shortest path Pde between the node Md and the given end point E; then, performing addition processing on v, and repeatedly performing the process of judging whether M1+ v is provided with the second mark until v is equal to n-1;
when the node M1+ v is set with the second flag, a process of adding one to v is performed and the above process of determining whether M1+ v is set with the second flag is continued in a loop until v is equal to n-1.
Preferably, in the process of calculating and acquiring a first shortest path between the given starting point S and the node Mi and a second shortest path between the node Mi and the given end point E, the path calculation module acquires a second short path closest to the shortest path, obtains a second short path between the given starting point S and the given end point E, which is composed of the second short paths, saves the second path, and takes the saved second short path between the given starting point S and the given end point E as a candidate backup path for: and when the shortest path between the given starting point S and the given end point E fails, enabling the candidate standby path.
Preferably, the path calculation module obtains n different nodes Mi that may pass between the given starting point S and the given end point E and node information corresponding to each node Mi, based on a topology structure of the peer-to-peer network.
The point-to-point shortest path calculation system in the peer-to-peer network can achieve the following beneficial effects:
acquiring starting point information and end point information of a shortest path between a given starting point S and a given end point E to be calculated in a peer-to-peer network through an information acquisition module; the path calculation module extracts n different nodes Mi which may pass between the given starting point S and the given end point E in the network link according to the starting point information and the end point information acquired by the information acquisition module; respectively calculating a first shortest path between the given starting point S and a node Mi and a second shortest path between the node Mi and the given end point E, thereby obtaining a shortest path between the given starting point S and the given end point E; the method has the advantages of simplifying the shortest path algorithm, avoiding the problem of overlarge calculation complexity caused by a calculation mode of acquiring the point-to-point shortest path by adopting a large number of complex algorithms, improving the calculation efficiency and saving the calculation resources and the calculation time.
Additional features and advantages of the invention will be set forth in the description which follows, and in part will be obvious from the description, or may be learned by practice of the invention. The objectives and other advantages of the invention will be realized and attained by the structure particularly pointed out in the written description and claims hereof as well as the appended drawings.
The technical solution of the present invention is further described below by means of the accompanying drawings and examples.
Drawings
The accompanying drawings, which are included to provide a further understanding of the invention and are incorporated in and constitute a part of this specification, illustrate embodiments of the invention and together with the description serve to explain the principles of the invention and not to limit the invention. In the drawings:
FIG. 1 is a functional block diagram of an embodiment of a point-to-point shortest path computation system in a peer-to-peer network according to the present invention;
fig. 2 is a schematic workflow diagram of an embodiment of a point-to-point shortest path calculation system in a peer-to-peer network according to the present invention.
Detailed Description
The preferred embodiments of the present invention will be described in conjunction with the accompanying drawings, and it will be understood that they are described herein for the purpose of illustration and explanation and not limitation.
The invention provides a point-to-point shortest path computing system in a peer-to-peer network, which is used for simplifying a shortest path algorithm, improving the computing efficiency of the shortest path and saving computing resources. In the Peer-to-Peer shortest path computing system (hereinafter referred to as "computing system") in the Peer-to-Peer network of the present invention, the described Peer-to-Peer network, i.e., P2P (Peer-to-Peer) network, which may also be referred to as "Peer-to-Peer computer network", is a distributed application architecture for distributing tasks and workloads among peers (peers), and is a networking or network form formed by Peer-to-Peer computing models in application layers. The academia refers to P2P collectively as a Peer-to-Peer network (Peer-to-Peer network) or Peer-to-Peer computing (Peer-to-Peer computing), which may be defined as: participants of the network share a portion of the hardware resources (processing power, storage power, network connectivity, printers, etc.) they own, which provide services and content over the network and which can be accessed directly by other Peer nodes (peers) without going through intermediate entities. The participants in this network are both providers (servers) and acquirers (clients) of resources, services and content. It can also be understood that: in a P2P network environment, multiple computers connected to each other are in a peer-to-peer relationship, each computer has the same functionality, without a master-slave relationship, and a computer can serve as both a server, setting shared resources for use by other computers in the network, and a workstation, and the overall network generally does not rely on a dedicated centralized server, nor does it have a dedicated workstation. Each computer in the network can both act as a requester of network services and provide resources, services and content in response to requests from other computers. Typically these resources and services include: sharing and exchange of information, computing resources (such as CPU computing power sharing), storage sharing (such as use of cache and disk space), network sharing, printer sharing, and the like.
As shown in fig. 1, fig. 1 is a functional module schematic diagram of an embodiment of a point-to-point shortest path calculation system in a peer-to-peer network according to the present invention, and the point-to-point shortest path calculation system in the peer-to-peer network according to the present invention includes: the information obtaining module 100 and the path calculating module 200, the information obtaining module 100 obtains start point information of a given start point S and end point information corresponding to a given end point E, and the path calculating module 200 calculates and obtains shortest path information between the given start point S and the given end point E according to node information corresponding to the given start point S and the given end point E respectively obtained by the information obtaining module 100, so as to obtain a shortest path between the given start point S and the given end point E.
Fig. 2 is a schematic workflow diagram of an embodiment of a point-to-point shortest path calculation system in a peer-to-peer network according to the present invention, and as shown in fig. 2, one of the workflows of the point-to-point shortest path calculation system in the peer-to-peer network according to the present invention may be implemented as steps S10-S30 described as follows:
step S10, the information obtaining module 100 obtains the starting point information and the end point information of the peer-to-peer network that need to calculate the shortest path between the given starting point S and the given end point E;
in this embodiment of the present invention, the information obtaining module 100 obtains a given starting point S and a given end point E in the peer-to-peer network, and obtains node information and positions of nodes in the network structure, which correspond to the given starting point S and the given end point E, respectively.
In a preferred embodiment of the present invention, the information obtaining module 100 obtains, based on a topology structure of the peer-to-peer network, node information corresponding to the given starting point S and the given ending point E, and a network hierarchy and a node position where the given starting point S and the given ending point E are located in the network topology structure.
Step S20, the path computation module 200 extracts n different nodes Mi that may pass through from the given starting point S to the given end point E in the network link according to the starting point information and the end point information acquired by the information acquisition module 100; wherein i is more than or equal to 1 and less than or equal to n;
in order to facilitate finding the shortest path between a given starting point S and a given end point E, the path computation module 200 extracts n different nodes Mi that may pass through from the given starting point S to the given end point E in the network link according to the starting point information and the end point information, for example, node information corresponding to the given starting point S and the given end point E, a hierarchy level and a location of the node in the peer-to-peer network; assuming that n is 3, a path from the given start point S to the given end point E may be S → M1 → M2 → M3 → E.
In a preferred embodiment of the present invention, the path calculating module 200 obtains n different nodes Mi that may pass between the given starting point S and the given end point E and node information corresponding to each node Mi based on a topology structure of the peer-to-peer network. Since the peer-to-peer network may be a single-layer network or a multi-layer network, it is more convenient and efficient to obtain the corresponding n different nodes Mi and the node information corresponding to the nodes Mi according to the topology structure of the peer-to-peer network with the topology structure being the multi-layer network. Wherein, the node information corresponding to the node Mi includes but is not limited to: node attributes and the network level and location of the node in the network topology.
Step S30 and the path calculation module 200 calculate a first shortest path between the given starting point S and the node Mi and a second shortest path between the node Mi and the given end point E, respectively, and determine the shortest path between the given starting point S and the given end point E according to the first shortest path and the second shortest path.
The path calculation module 200, when calculating the shortest path between a given starting point S to a given end point E, may convert it into: and searching a first shortest path between a given starting point S and the intermediate node Mi and a second shortest path between the intermediate node Mi and the given end point E, and combining the two shortest paths to obtain the shortest path between the given starting point S and the given end point E.
In a preferred embodiment of the present invention, the path computation module extracts n different nodes Mi that may pass through from a given starting point S to a given end point E in the network link, and specifically includes the following steps:
randomly acquiring h primary selection paths from a given starting point S to a given end point E according to the starting point information and the end point information, respectively calculating evaluation values of the primary selection paths, and selecting partial nodes from nodes passed by the primary selection path with the highest evaluation value as n different nodes Mi which may pass from the given starting point S to the given end point E; in the initial selection path with the highest evaluation value, the farther Mi is from the given starting point S, the larger i is.
Wherein, the step of calculating the evaluation value of the initial selection path comprises the steps of A1-A3:
step A1: determining m different nodes mt sequentially passing through the middle of the current primary selection path, t is more than or equal to 1 and less than or equal to m, and determining the edge weight w between two adjacent nodes contained in the primary selection pathj，wj>J is more than or equal to 0 and less than or equal to m.
In the embodiment of the present invention, the side right wjAnd the path is not negative, so that the minimum path is conveniently calculated by adopting Dijkstra algorithm in the follow-up process. Meanwhile, the larger the edge weight is, the higher the cost of passing through the edge is.
Step A2: determining that the edge weight between two adjacent nodes contained in the primary selection path is less than a preset standard edge weight wsThe edge weight p.
Step A3: calculating an evaluation value S of the primary route:
In the embodiment of the invention, the primary selection path with the highest evaluation value is determined according to the evaluation value of the path, and the primary selection path with the highest evaluation value is closest to the shortest path between S and E in all the primary selection paths; and then selecting part of nodes Mi from the initially selected paths with the highest evaluation value, so that the shortest path from S to E can be further optimized, and the finally determined shortest path is matched with the actual shortest path as much as possible.
In a preferred embodiment of the present invention, in order to improve the calculation efficiency, the path calculation module 200 simultaneously calculates n sets of paths from the given starting point S to the node Mi and the path from the node Mi to the given end point E, so as to obtain 2n segments of path results; and respectively finding out the shortest path from the given starting point S to the node Mi and from the node Mi to the given end point E from the 2n path results to obtain the shortest path from the given starting point S to the given end point E.
In a preferred embodiment of the present invention, if the computing system is a multi-core system, in order to fully utilize system resources and further improve computing efficiency, the path computing module 200 computes n groups of different paths by using a multi-core asynchronous parallel algorithm, and obtains 2n segment path results.
In a preferred embodiment of the present invention, the path calculating module 200 calculates n sets of paths between the given starting point S and the node Mi and between the node Mi and the given end point E, extracts local optimal sub-paths between the given starting point S and the node Mi and between the node Mi and the given end point E, and combines the local optimal sub-paths to obtain the shortest path between the given starting point S and the given end point E.
In a preferred embodiment of the present invention, the path calculating module 200 obtains the 2n segment path result by calculating n groups of paths from the given starting point S to the node Mi and n groups of paths from the node Mi to the given end point E; identifying whether a path intersection point exists in the obtained 2 n-segment path result; if the corresponding path intersection point exists in the 2 n-segment path result, finding out the existing path intersection point. The path calculation module 200 further identifies whether more than one path exists between every two intersection points among the intersection points; if more than one path is identified between every two intersection points, the shortest path between the two intersection points is calculated and acquired, and thus the shortest path from the given starting point S to the given end point E is finally acquired.
Further, in order to save the storage resources of the computing system, in a preferred embodiment of the present invention, if the path computation module 200 identifies that there is more than one path between each two intersection points, only the shortest path between the two intersection points is reserved, and other path information is deleted.
In a preferred embodiment of the present invention, if there is a corresponding path intersection point in the calculated 2 n-end path result, the path calculation module 200 searches and obtains a shortest path between two intersection points by using an a-x algorithm in euclidean distance. In the embodiment of the invention, the a-Star algorithm is a most effective direct search method for solving the shortest path in the static road network. In the embodiment of the present invention, since the shortest path between the given starting point S and the given end point E (S, E) is converted into two sub-problems, i.e., the first shortest path between the given starting point S and the node Mi (S, Mi) and the second shortest path between the node Mi and the given end point E (Mi, E), the sum of the search spaces of the two sub-problems (S, Mi) and (Mi, E) is usually smaller than that of the original problem (S, E), and the two sub-problems can be solved in parallel. Since it cannot be guaranteed that the points are always the points on the shortest path (S, E), the path obtained is an approximate solution even if the coefficient of the estimation function of the a-x algorithm is 1. If the coefficient is greater than 1, the a-algorithm can be executed more quickly, and therefore, in the embodiment of the present invention, the coefficient of the evaluation function of the a-algorithm is set to a value greater than 1, and the resulting large error of the result can be reduced by means of redundant calculation. For example, the path computation module 200 performs a traversal on each of the 2n paths, and checks whether other paths pass through the node during the traversal, and if so, the node is an intersection. Obviously, a given starting point S and a given end point E must be the intersection point. When the path calculation module 200 checks an intersection, there are two or more paths between the intersection and the previous intersection, and the lengths of the paths can be easily determined by using the search result of the a-x algorithm, the path calculation module 200 retains the shortest one of the paths, and finally, only one relatively optimized path remains between the given starting point S and the given end point E.
Further, in a preferred embodiment of the present invention, if the path calculation module 200 identifies more than one path between two intersection points and there are other nodes between the two intersection points, it calculates and obtains the shortest path between the two intersection points by using dijkstra's algorithm. The Dijkstra algorithm is a shortest path algorithm from one vertex to the rest of the vertices, and solves the problem of shortest paths in a directed graph. The Dijkstra algorithm is mainly characterized in that the Dijkstra algorithm expands outwards layer by taking a starting point as a center until the expansion reaches a terminal point.
In a preferred embodiment of the present invention, the step S30 calculates a first shortest path between the given starting point S and the node Mi and a second shortest path between the node Mi and the given end point E, respectively, and determines the shortest path between the given starting point S and the given end point E according to the first shortest path and the second shortest path, specifically including steps B1-B4:
step B1: selecting the last node Mn in all nodes Mi, taking u as 0 as a starting point, setting the step length of u as 1, circularly judging whether a node Mn-u is provided with a first mark, determining a first shortest path Psn-u between a given starting point S and the node Mn-u when the node Mn-u does not have the first mark, adding the first mark to the node Mn-u, and judging whether a node Na through which the first shortest path Psn-u passes is one node in the nodes Mi or not; when the node Na is one node Mb in the nodes Mi, adding a first mark to the node Mb, and taking a path between a given starting point S and the node Na in the first shortest path Psn-u as a first shortest path Psb between the given starting point S and the node Mb; and then adding one to u, and repeatedly executing the process of judging whether the Mn-u is provided with the first mark until u is equal to n-1.
Step B2: when the node Mn-u is provided with the first flag, the process of adding one to u is executed and the above process of determining whether Mn-u is provided with the first flag is continuously executed in a loop until u is n-1.
In the embodiment of the present invention, the steps B1-B2 are the steps of determining the first shortest path from the given starting point S to all nodes Mi. Starting from the last node Mn (i.e. u ═ 0), Mn must then have no first label, so the first shortest path Psn between S and Mn is determined directly. If the first shortest path Psn passes through the node Na, and Na is a node Mb in the Mi, that is, the node Na and the node Mb are the same node, the shortest path from S to Na is determined as a sub-path of the first shortest path Psn, that is, the sub-path of the first shortest path Psn is also the shortest path. Therefore, in this case, the path from S to Mb in the first shortest path Psn may be set as the shortest path from S to Mb, and the shortest path from S to Mb does not need to be calculated any more, thereby saving processing resources and further improving calculation efficiency.
At the same time, a first flag is used to indicate that the node Mi has computed the first shortest path. And after traversing all the nodes in the first shortest path Psn, adding one to u, namely judging the first shortest path Psn-1 corresponding to Mn-1, and repeatedly executing the steps until u is equal to n-1. If Mn-1 contains the first mark, the node Mn-1 is contained in the path Psn determined in the previous cycle process, repeated calculation is not needed, and therefore u is added by one, and the node Mn-2 is judged.
Step B3: selecting a first node M1 from all nodes Mi, circularly judging whether a node M1+ v is provided with a second mark or not by taking v as a starting point and the step length of v as 1, determining a second shortest path P1+ ve from the node M1+ v to a given terminal E when the node M1+ v has no second mark, adding a second mark to the node M1+ v, and judging whether a node Nc through which the second shortest path P1+ ve passes is one node from the nodes Mi or not; when the node Nc is one node Md in the nodes Mi, adding a second mark to the node Md, and taking a path between the node Nc in the second shortest path P1+ ve and the given end point E as a second shortest path Pde between the node Md and the given end point E; and then, performing addition processing on v, and repeatedly performing the process of judging whether the M1+ v is provided with the second mark until v is equal to n-1.
Step B4: when the node M1+ v is set with the second flag, the process of adding one to v is executed and the above process of determining whether the node M1+ v is set with the second flag is continued in a loop until v is equal to n-1.
The above steps B3-B4 are for determining the second shortest path between the nodes Mi to E, and the principle is similar to the above steps B1-B2, which are not repeated herein. Wherein the second flag is used to indicate that the node Mi has calculated the second shortest path from Mi to E. After the first shortest path and the second shortest path are determined, the two shortest paths are combined to obtain n paths from S to E, and the shortest path is selected from the n paths.
In a preferred embodiment of the present invention, in order to prevent the shortest path between the calculated fixed starting point S and the given end point E from failing, the path calculating module 200, in the process of calculating and acquiring the first shortest path between the given starting point S and the node Mi and the second shortest path between the node Mi and the given end point E, acquires the second short path closest to the shortest path, acquires the second short path between the given starting point S and the given end point E, and stores the second short path, and takes the stored second short path between the given starting point S and the given end point E as a candidate backup path for: and when the shortest path between the given starting point S and the given end point E fails, enabling the candidate standby path.
The invention discloses a point-to-point shortest path calculation system in a peer-to-peer network, which acquires starting point information and end point information of a shortest path between a given starting point S and a given end point E to be calculated in the peer-to-peer network through an information acquisition module; the path calculation module extracts n different nodes Mi which may pass between the given starting point S and the given end point E in the network link according to the starting point information and the end point information acquired by the information acquisition module; respectively calculating a first shortest path between the given starting point S and a node Mi and a second shortest path between the node Mi and the given end point E, thereby obtaining a shortest path between the given starting point S and the given end point E; the method has the advantages of simplifying the shortest path algorithm, avoiding the problem of overlarge calculation complexity caused by a calculation mode of acquiring the point-to-point shortest path by adopting a large number of complex algorithms, improving the calculation efficiency and saving the calculation resources and the calculation time.
As will be appreciated by one skilled in the art, embodiments of the present invention may be provided as a method, system, or computer program product. Accordingly, the present invention may take the form of an entirely hardware embodiment, an entirely software embodiment or an embodiment combining software and hardware aspects.
The present invention is described with reference to flowchart illustrations and/or block diagrams of methods, apparatus (systems), and computer program products according to embodiments of the invention. It will be understood that each flow and/or block of the flow diagrams and/or block diagrams, and combinations of flows and/or blocks in the flow diagrams and/or block diagrams, can be implemented by computer program instructions. These computer program instructions may be provided to a processor of a general purpose computer, special purpose computer, embedded processor, or other programmable data processing apparatus to produce a machine, such that the instructions, which execute via the processor of the computer or other programmable data processing apparatus, create means for implementing the functions specified in the flowchart flow or flows and/or block diagram block or blocks.
These computer program instructions may also be stored in a computer-readable memory that can direct a computer or other programmable data processing apparatus to function in a particular manner, such that the instructions stored in the computer-readable memory produce an article of manufacture including instruction means which implement the function specified in the flowchart flow or flows and/or block diagram block or blocks.
These computer program instructions may also be loaded onto a computer or other programmable data processing apparatus to cause a series of operational steps to be performed on the computer or other programmable apparatus to produce a computer implemented process such that the instructions which execute on the computer or other programmable apparatus provide steps for implementing the functions specified in the flowchart flow or flows and/or block diagram block or blocks.
It will be apparent to those skilled in the art that various changes and modifications may be made in the present invention without departing from the spirit and scope of the invention. Thus, if such modifications and variations of the present invention fall within the scope of the claims of the present invention and their equivalents, the present invention is also intended to include such modifications and variations.
Claims (9)
1. A point-to-point shortest path computation system in a peer-to-peer network, the point-to-point shortest path computation system comprising: the system comprises an information acquisition module and a path calculation module; wherein:
the information acquisition module is used for: acquiring starting point information and end point information of a given starting point S and a given end point E which need to calculate the shortest path in a peer-to-peer network;
the path computation module is configured to: extracting n different nodes Mi which may pass from the given starting point S to the given end point E in a network link according to the starting point information and the end point information acquired by the information acquisition module; wherein i is more than or equal to 1 and less than or equal to n;
respectively calculating a first shortest path between the given starting point S and a node Mi and a second shortest path between the node Mi and the given end point E, and determining the shortest path between the given starting point S and the given end point E according to the first shortest path and the second shortest path;
the path computation module extracts n different nodes Mi that may pass between the given start point S and the given end point E in the network link, including:
the path calculation module randomly acquires h primary selection paths from the given starting point S to the given end point E according to the starting point information and the end point information, respectively calculates evaluation values of the primary selection paths, and selects part of nodes from the nodes passed by the primary selection path with the highest evaluation value as n different nodes Mi which may pass from the given starting point S to the given end point E; in the initial selection path with the highest evaluation value, the farther the Mi is from the given starting point S, the larger i is;
wherein, calculating the evaluation value of the initial selection path comprises:
determining m different nodes Mt passing through the middle of the current primary selection path in sequence, wherein t is more than or equal to 1 and less than or equal to m, and determining the edge weight w between two adjacent nodes contained in the primary selection pathj，wj>J is more than or equal to 0 and less than or equal to m;
determining that the edge weight between two adjacent nodes contained in the primary selection path is smaller than a preset standard edge weight wsThe edge weight p of (a);
calculating an evaluation value S of the primary selection path:
2. The system for calculating shortest point-to-point paths in a peer-to-peer network according to claim 1, wherein the path calculating module simultaneously calculates n sets of paths from the given starting point S to the node Mi and from the node Mi to the given end point E to obtain 2n segments of path results;
and respectively finding out the shortest path from the given starting point S to the node Mi and from the node Mi to the given end point E from the 2n path results to obtain the shortest path from the given starting point S to the given end point E.
3. The peer-to-peer network point-to-point shortest path computation system of claim 2, wherein the path computation module computes n different sets of paths using a multi-core asynchronous parallel algorithm to obtain 2n segment path results.
4. The peer-to-peer network point-to-point shortest path computation system of claim 1, 2 or 3, wherein the path computation module finds path intersection points from the 2n segment path results, and if more than one path is identified between every two intersection points, computes and obtains the shortest path between the two intersection points, and finally obtains the shortest path from the given starting point S to the given end point E.
5. The peer-to-peer network point-to-point shortest path computation system of claim 4, wherein the path computation module searches for and obtains a shortest path between two intersection points using the a-in-euclidean distance algorithm.
6. The peer-to-peer network point-to-point shortest path computation system of claim 4, wherein if the path computation module identifies more than one path between each two intersection points, only the shortest path between the two intersection points is reserved, and other path information is deleted.
7. The peer-to-peer network point-to-point shortest path computation system of claim 4, wherein if the path computation module identifies more than one path between two intersections and there are other nodes between the two intersections, it computes and obtains the shortest path between the two intersections using dijkstra's algorithm.
8. The peer-to-peer network point-to-point shortest path computing system of claim 1, wherein said computing a first shortest path between said given starting point S to a node Mi and a second shortest path between said node Mi to said given end point E, respectively, determining a shortest path between said given starting point S to a given end point E based on said first shortest path and said second shortest path, comprises:
selecting the last node Mn in all nodes Mi, taking u =0 as a starting point, setting the step length of u as 1, circularly judging whether a node Mn-u is provided with a first mark, determining a first shortest path Psn-u between the given starting point S and the node Mn-u when the node Mn-u has no first mark, adding a first mark to the node Mn-u, and judging whether a node Na through which the first shortest path Psn-u passes is one node in the nodes Mi; when a node Na is one node Mb in a node Mi, adding a first flag to the node Mb, and taking a path from the given starting point S to the node Na in the first shortest path Psn-u as a first shortest path Psb from the given starting point S to the node Mb; then, adding one to u, and repeatedly executing the process of judging whether the Mn-u is provided with the first mark until u = n-1;
when the node Mn-u is provided with a first mark, performing addition processing on u and continuously and circularly performing the process of judging whether the node Mn-u is provided with the first mark until u = n-1;
selecting a first node M1 from all nodes Mi, taking v =0 as a starting point, setting the step length of v as 1, circularly judging whether a node M1+ v is provided with a second mark, determining a second shortest path P1+ ve between the node M1+ v and the given terminal E when the node M1+ v has no second mark, adding a second mark to the node M1+ v, and judging whether a node Nc through which the second shortest path P1+ ve passes is one node from the nodes Mi; when the node Nc is one node Md in the nodes Mi, adding a second label to the node Md, and taking a path between the node Nc and the given end point E in the second shortest path P1+ ve as a second shortest path Pde between the node Md and the given end point E; then, performing addition processing on v, and repeatedly performing the process of judging whether the M1+ v is provided with the second mark until v = n-1;
when the node M1+ v is provided with the second mark, the process of adding one to v is executed and the above process of judging whether the node M1+ v is provided with the second mark is continuously executed in a loop until v = n-1.
9. The peer-to-peer shortest path calculation system of claim 1, 2 or 3, wherein the path calculation module, in calculating and obtaining a first shortest path between the given starting point S to the node Mi and a second shortest path between the node Mi to the given end point E, obtains a second short path closest to the shortest paths, obtains a second short path between the given starting point S to a given end point E consisting of the second short paths, and saves the second short path, and takes the saved second short path between the given starting point S to a given end point E as a candidate backup path for: and when the shortest path between the given starting point S and the given end point E fails, enabling the candidate standby path.
Applications Claiming Priority (2)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| CN201810129321 | 2018-02-08 | ||
| CN201810129321X | 2018-02-08 |
Publications (2)
| Publication Number | Publication Date |
|---|---|
| CN108449268A CN108449268A (en) | 2018-08-24 |
| CN108449268B true CN108449268B (en) | 2020-09-01 |
Family
ID=63194805
Family Applications (1)
| Application Number | Title | Priority Date | Filing Date |
|---|---|---|---|
| CN201810215767.4A Active CN108449268B (en) | 2018-02-08 | 2018-03-15 | Point-to-point shortest path computing system in peer-to-peer network |
Country Status (1)
| Country | Link |
|---|---|
| CN (1) | CN108449268B (en) |
Families Citing this family (1)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| CN111552844B (en) * | 2020-04-24 | 2023-07-04 | 山东科技大学 | Distributed method for solving shortest path of large-scale multi-section graph |
Citations (4)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| CN102057637A (en) * | 2009-06-09 | 2011-05-11 | 思科技术公司 | Routing-based proximity for communication networks |
| WO2014178055A1 (en) * | 2013-05-01 | 2014-11-06 | G-Ils Transportation Ltd | A real time decision making method optimization route and pricing engine for freight transportation (cargo) |
| CN104933248A (en) * | 2015-06-16 | 2015-09-23 | 中国科学技术大学 | Road network approximate shortest path calculation method on multi-core platform |
| CN105740964A (en) * | 2014-12-08 | 2016-07-06 | 吉林大学 | Urban road network data organization and shortest path rapid calculation method |
Family Cites Families (1)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| US9697276B2 (en) * | 2014-12-29 | 2017-07-04 | International Business Machines Corporation | Large taxonomy categorization |
-
2018
- 2018-03-15 CN CN201810215767.4A patent/CN108449268B/en active Active
Patent Citations (4)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| CN102057637A (en) * | 2009-06-09 | 2011-05-11 | 思科技术公司 | Routing-based proximity for communication networks |
| WO2014178055A1 (en) * | 2013-05-01 | 2014-11-06 | G-Ils Transportation Ltd | A real time decision making method optimization route and pricing engine for freight transportation (cargo) |
| CN105740964A (en) * | 2014-12-08 | 2016-07-06 | 吉林大学 | Urban road network data organization and shortest path rapid calculation method |
| CN104933248A (en) * | 2015-06-16 | 2015-09-23 | 中国科学技术大学 | Road network approximate shortest path calculation method on multi-core platform |
Also Published As
| Publication number | Publication date |
|---|---|
| CN108449268A (en) | 2018-08-24 |
Similar Documents
| Publication | Publication Date | Title |
|---|---|---|
| CN111030802B (en) | Method, device and equipment for distributing calculation tasks of graph data and storage medium | |
| CN104504003B (en) | The searching method and device of diagram data | |
| CN105765576B (en) | Processing search queries using data structures | |
| CN110188097A (en) | The storage of intelligent contract, execution method and device and electronic equipment in block chain | |
| CN104917659B (en) | A kind of mapping method of virtual network based on virtual network connection performance | |
| CN111045827B (en) | Task scheduling method based on time effectiveness of resource sharing in cloud and fog environment | |
| US8682611B2 (en) | Distance metric estimating system, coordinate calculating node, distance metric estimating method, and program | |
| CN108449268B (en) | Point-to-point shortest path computing system in peer-to-peer network | |
| Zhang et al. | Virtual network mapping through locality-aware topological potential and influence node ranking | |
| TW201824819A (en) | Virtual machine migration method and device | |
| Tirado et al. | Affinity p2p: A self-organizing content-based locality-aware collaborative peer-to-peer network | |
| US10031777B2 (en) | Method and system for scheduling virtual machines in integrated virtual machine clusters | |
| CN115361332A (en) | Processing method and device for fault-tolerant routing, processor and electronic equipment | |
| JP2008269141A (en) | Overlay search device, overlay search system, overlay search method, and overlay search program | |
| CN115730663A (en) | Quantum computing task mapping method and quantum computer operating system | |
| WO2015055502A2 (en) | Method of partitioning storage in a distributed data storage system and corresponding device | |
| CN107547657A (en) | A kind of method, apparatus and storage medium numbered based on one point data in cloud storage system | |
| Nasir et al. | Fast trust computation in online social networks | |
| Li et al. | An improved A* algorithm applicable for campus navigation system | |
| US20060209717A1 (en) | Distributed storing of network position information for nodes | |
| Liu et al. | A cost-provable solution for reliable in-network computing-enabled services deployment | |
| WO2017028930A1 (en) | Methods and apparatus for running an analytics function | |
| Ho et al. | Data replication for distributed graph processing | |
| Kokuti et al. | Market-based approach for cooperation and coordination among multiple autonomous vehicles | |
| CN104933248A (en) | Road network approximate shortest path calculation method on multi-core platform |
Legal Events
| Date | Code | Title | Description |
|---|---|---|---|
| PB01 | Publication | ||
| PB01 | Publication | ||
| SE01 | Entry into force of request for substantive examination | ||
| SE01 | Entry into force of request for substantive examination | ||
| GR01 | Patent grant | ||
| GR01 | Patent grant |