This paper presents an efficient parallel algorithm for the shortest path problem in planar layered digraphs that runs in O(log^3n) time with n processors. The algorithms uses a divide and conquer approach and is base...This paper presents an efficient parallel algorithm for the shortest path problem in planar layered digraphs that runs in O(log^3n) time with n processors. The algorithms uses a divide and conquer approach and is based on the novel idea of a one-way separator, which has the property that any directed path can be crossed only once.展开更多
In most network analysis tools the computation of the shortest paths between all pairs of nodes is a fundamental step to the discovery of other properties. Among other properties is the computation of closeness centra...In most network analysis tools the computation of the shortest paths between all pairs of nodes is a fundamental step to the discovery of other properties. Among other properties is the computation of closeness centrality, a measure of the nodes that shows how central a vertex is on a given network. In this paper, the authors present a method to compute the All Pairs Shortest Paths on graphs that present two characteristics： abundance of nodes with degree value one, and existence of articulation points along the graph. These characteristics are present in many real life networks especially in networks that show a power law degree distribution as is the case of biological networks. The authors＇ method compacts the single nodes to their source, and then by using the network articulation points it disconnects the network and computes the shortest paths in the biconnected components. At the final step the authors proposed methods merges the results to provide the whole network shortest paths. The authors＇ method achieves remarkable speedup compared to state of the art methods to compute the shortest paths, as much as 7 fold speed up in artificial graphs and 3.25 fold speed up in real application graphs. The authors＇ performance improvement is unlike previous research as it does not involve elaborated setups since the authors algorithm can process significant instances on a popular workstation.展开更多
This study is trying to address the critical need for efficient routing in Mobile Ad Hoc Networks(MANETs)from dynamic topologies that pose great challenges because of the mobility of nodes.Themain objective was to del...This study is trying to address the critical need for efficient routing in Mobile Ad Hoc Networks(MANETs)from dynamic topologies that pose great challenges because of the mobility of nodes.Themain objective was to delve into and refine the application of the Dijkstra’s algorithm in this context,a method conventionally esteemed for its efficiency in static networks.Thus,this paper has carried out a comparative theoretical analysis with the Bellman-Ford algorithm,considering adaptation to the dynamic network conditions that are typical for MANETs.This paper has shown through detailed algorithmic analysis that Dijkstra’s algorithm,when adapted for dynamic updates,yields a very workable solution to the problem of real-time routing in MANETs.The results indicate that with these changes,Dijkstra’s algorithm performs much better computationally and 30%better in routing optimization than Bellman-Ford when working with configurations of sparse networks.The theoretical framework adapted,with the adaptation of the Dijkstra’s algorithm for dynamically changing network topologies,is novel in this work and quite different from any traditional application.The adaptation should offer more efficient routing and less computational overhead,most apt in the limited resource environment of MANETs.Thus,from these findings,one may derive a conclusion that the proposed version of Dijkstra’s algorithm is the best and most feasible choice of the routing protocol for MANETs given all pertinent key performance and resource consumption indicators and further that the proposed method offers a marked improvement over traditional methods.This paper,therefore,operationalizes the theoretical model into practical scenarios and also further research with empirical simulations to understand more about its operational effectiveness.展开更多
The study on how to identify influential spreaders in complex networks is becoming increasingly significant.Previous studies demonstrate that considering the shortest path length can improve the accuracy of identifica...The study on how to identify influential spreaders in complex networks is becoming increasingly significant.Previous studies demonstrate that considering the shortest path length can improve the accuracy of identification,but which ignore the influence of the number of shortest paths.In many cases,even though the shortest path length of two nodes is rather larger,their interaction influence is also significant if the number of shortest paths between them is considerable.Inspired by this fact,the authors propose an improved centrality index(ICC)based on well-known closeness centrality and a semi-local iterative algorithm(semi-IA)to study the impact of the number of shortest paths on the identification of the influential spreaders.By comparing with several traditional centrality indices,such as degree centrality,k-shell decomposition,betweenness centrality and eigenvector centrality,the experimental results on real networks indicate that the ICC index and semi-IA have a better performance,regardless of the identification capability or the resolution.展开更多
To effectively solve the single-source shortest path(SSSP)problem for massive road networks in geographical information systems,a new synchronization method is proposed in the implementations of parallel SSSP algorith...To effectively solve the single-source shortest path(SSSP)problem for massive road networks in geographical information systems,a new synchronization method is proposed in the implementations of parallel SSSP algorithm.It applies spinlock by inline assembly language for the sake of small overheads of controlling the interaction of multiple threads.The performance of our method is compared with widely used Pthreads application programming interfaces and the powerful sequential solution given by DIMACS.The experimental platform is a shared address space workstation with two processors(i.e.eight cores)at a clock speed of 3 GHz.Problem instances for experiments contain a directed road networks of the USA with more than 23 million vertices and 57 million edges,and its 11 subnetworks of variant sizes.This method answers the SSSP of the USA road network in 1231 ms,while Pthreads costs 1808 ms and DIMACS sequential solution takes 4856 ms.It achieves a speedup of 3.95,which is 47%faster than Pthreads with the speedup of 2.69.When the size of instance is larger,our method achieves a better performance.展开更多
This paper discusses the problem of finding a shortest path from a fixed origin s to a specified node t in a network with arcs represented as typical triangular fuzzy numbers (TFN). Because of the characterist...This paper discusses the problem of finding a shortest path from a fixed origin s to a specified node t in a network with arcs represented as typical triangular fuzzy numbers (TFN). Because of the characteristic of TFNs, the length of any path p from s to t , which equals the extended sum of all arcs belonging to p , is also TFN. Therefore, the fuzzy shortest path problem (FSPP) becomes to select the smallest among all those TFNs corresponding to different paths from s to t (specifically, the smallest TFN represents the shortest path). Based on Adamo's method for ranking fuzzy number, the pessimistic method and its extensions - optimistic method and λ combination method, are presented, and the FSPP is finally converted into the crisp shortest path problems.展开更多
Purpose:To contribute to the study of networks and graphs.Design/methodology/approach:We apply standard mathematical thinking.Findings:We show that the distance distribution in an undirected network Lorenz majorizes t...Purpose:To contribute to the study of networks and graphs.Design/methodology/approach:We apply standard mathematical thinking.Findings:We show that the distance distribution in an undirected network Lorenz majorizes the one of a chain.As a consequence,the average and median distances in any such network are smaller than or equal to those of a chain.Research limitations:We restricted our investigations to undirected,unweighted networks.Practical implications:We are convinced that these results are useful in the study of small worlds and the so-called six degrees of separation property.Originality/value:To the best of our knowledge our research contains new network results,especially those related to frequencies of distances.展开更多
Unlike the shortest path problem that has only one optimal solution and can be solved in polynomial time, the muhi-objective shortest path problem （ MSPP ） has a set of pareto optimal solutions and cannot be solved ...Unlike the shortest path problem that has only one optimal solution and can be solved in polynomial time, the muhi-objective shortest path problem （ MSPP ） has a set of pareto optimal solutions and cannot be solved in polynomial time. The present algorithms focused mainly on how to obtain a precisely pareto optimal solution for MSPP resulting in a long time to obtain multiple pareto optimal solutions with them. In order to obtain a set of satisfied solutions for MSPP in reasonable time to meet the demand of a decision maker, a genetic algo- rithm MSPP-GA is presented to solve the MSPP with typically competing objectives, cost and time, in this pa- per. The encoding of the solution and the operators such as crossover, mutation and selection are developed. The algorithm introduced pareto domination tournament and sharing based selection operator, which can not only directly search the pareto optimal frontier but also maintain the diversity of populations in the process of evolutionary computation. Experimental results show that MSPP-GA can obtain most efficient solutions distributed all along the pareto frontier in less time than an exact algorithm. The algorithm proposed in this paper provides a new and effective method of how to obtain the set of pareto optimal solutions for other multiple objective optimization problems in a short time.展开更多
In order to form an algorithm for distribution network routing,an automatic routing method of distribution network planning was proposed based on the shortest path.The problem of automatic routing was divided into two...In order to form an algorithm for distribution network routing,an automatic routing method of distribution network planning was proposed based on the shortest path.The problem of automatic routing was divided into two steps in the method:the first step was that the shortest paths along streets between substation and load points were found by the basic ant colony algorithm to form a preliminary radial distribution network,and the second step was that the result of the shortest path was used to initialize pheromone concentration and pheromone updating rules to generate globally optimal distribution network.Cases studies show that the proposed method is effective and can meet the planning requirements.It is verified that the proposed method has better solution and utility than planning method based on the ant colony algorithm.展开更多
Rational planning of agricultural product transport route from initial node to destination node can effectively reduce the cost price of agricultural products,and the calculation of shortest path between any two point...Rational planning of agricultural product transport route from initial node to destination node can effectively reduce the cost price of agricultural products,and the calculation of shortest path between any two points also affects people’s daily travel.Taking Heze Railway Station to Heze College for example,with remote sensing image data as the base map,we conduct vectorization and topological analysis on roads in the target area.With Dijkstra as theoretical basis of shortest path algorithm,we use ArcG IS network analysis method to build road network,and calculate the planning program of the shortest distance path,the shortest path by driving and the shortest path by walking.展开更多
In this figure, it finds a vertex to another vertex k shortest path algorithm. Provided there are n vertices and edges in the diagram. If the path loops, the time complexity of the algorithm is allowed O（w ＋ n log 2...In this figure, it finds a vertex to another vertex k shortest path algorithm. Provided there are n vertices and edges in the diagram. If the path loops, the time complexity of the algorithm is allowed O（w ＋ n log 2 n ＋ kw log 2 k）. If the request path does not contain the loop, the time complexity of the algorithm O（kn（w ＋ n log2 n）＋ kw log2 k）. The algorithm utilizes a simple extension of the Dijkstra algorithm determined the end of the length of the shortest path to the other vertices, and then, based on these data, branch and bound method to identify the required path. Experimental results show that the actual running time has relations with the structure of FIG.展开更多
Finding the shortest path （SP） in a large-scale network analysis between any two nodes is a tough but very significant task. The SP can help us to analyze the information spreading performance and research the laten...Finding the shortest path （SP） in a large-scale network analysis between any two nodes is a tough but very significant task. The SP can help us to analyze the information spreading performance and research the latent relationship in the weighted social network, and so on. As the size of the social network increases, the traditional SP algorithms have poor performance and there is not a suitable algorithm for weighted social network. Some features of the network analysis are beneficial to solve this problem, and community structure ignored by the traditional methods is one of the most important features. In this paper, we propose a shortest path algorithm based on community detection （SPCD） by integrating community detection algorithm with traditional search methods. SPCD constructs a community graph by using community structure to narrow the searching scope. The algorithm presented improves the time efficiency and maintains the accuracy scale of the SR Experimental results on five real-world networks demonstrate the effectiveness of the proposed methods for the SP problem.展开更多
The shortcomings of traditional methods to find the shortest path are revealed, and a strategy of finding the self- organizing shortest path based on thermal flux diffusion on complex networks is presented. In our met...The shortcomings of traditional methods to find the shortest path are revealed, and a strategy of finding the self- organizing shortest path based on thermal flux diffusion on complex networks is presented. In our method, the shortest paths between the source node and the other nodes are found to be self-organized by comparing node temperatures. The computation complexity of the method scales linearly with the number of edges on underlying networks. The effects of the method on several networks, including a regular network proposed by Ravasz and Barabasi which is called the RB network, a real network, a random network proposed by Ravasz and Barabasi which is called the ER network and a scale-free network, are also demonstrated. Analytic and simulation results show that the method has a higher accuracy and lower computational complexity than the conventional methods.展开更多
A shortest path routing algorithm based on transient chaotic neural network is proposed in this paper. Gam-pared with previous models adopting Hopfield neural network, this algorithm has a higher ability to overcome t...A shortest path routing algorithm based on transient chaotic neural network is proposed in this paper. Gam-pared with previous models adopting Hopfield neural network, this algorithm has a higher ability to overcome the local minimum, and achieves a better performance. By introducing a special post-processing technique for the output matrixes, our algorithm can obtain an optimal solution with a high probability even for the paths that need more hops in large-size networks.展开更多
The time-optimal trajectory planning is proposed under kinematic and dynamic constraints for a 2-DOF wheeled robot. In order to make full use of the motor’s capacity, we calculate the maximum torque and the minimum t...The time-optimal trajectory planning is proposed under kinematic and dynamic constraints for a 2-DOF wheeled robot. In order to make full use of the motor’s capacity, we calculate the maximum torque and the minimum torque by considering the maximum heat-converted power generated by the DC motor. The shortest path is planned by using the geometric method under kinematic constraints. Under the bound torques, the velocity limits and the maximum acceleration (deceleration) are obtained by combining with the dynamics. We utilize the phase-plane analysis technique to generate the time optimal trajectory based on the shortest path. At last, the computer simulations for our laboratory mobile robot were performed. The simulation results prove the proposed method is simple and effective for practical use.展开更多
The shortest path is a widely studied network science problem and has attracted great attention.Nevertheless,it draws little attention in temporal networks,in which temporal edges determine information dissemination.I...The shortest path is a widely studied network science problem and has attracted great attention.Nevertheless,it draws little attention in temporal networks,in which temporal edges determine information dissemination.In this paper,we propose an information spreading-based method to calculate the shortest paths distribution in temporal networks.We verify our method on both artificial and real-world temporal networks and obtain a good agreement.We further generalize our method to identify influential nodes and found an effective method.Finally,we verify the influential nodes identifying method on four networks.展开更多
On the basis of Floyd algorithm with the extended path matrix, a parallel algorithm which resolves all-pair shortest path （APSP） problem on cluster environment is analyzed and designed. Meanwhile, the parallel APSP ...On the basis of Floyd algorithm with the extended path matrix, a parallel algorithm which resolves all-pair shortest path （APSP） problem on cluster environment is analyzed and designed. Meanwhile, the parallel APSP pipelining algorithm makes full use of overlapping technique between computation and communication. Compared with broadcast operation, the parallel algorithm reduces communication cost. This algorithm has been implemented on MPI on PC-cluster. The theoretical analysis and experimental results show that the parallel algorithm is an efficient and scalable algorithm.展开更多
The Floyd-Warshall algorithm is frequently used to determine the shortest path between any pair of nodes.It works well for crisp weights,but the problem arises when weights are vague and uncertain.Let us take an examp...The Floyd-Warshall algorithm is frequently used to determine the shortest path between any pair of nodes.It works well for crisp weights,but the problem arises when weights are vague and uncertain.Let us take an example of computer networks,where the chosen path might no longer be appropriate due to rapid changes in network conditions.The optimal path from among all possible courses is chosen in computer networks based on a variety of parameters.In this paper,we design a new variant of the Floyd-Warshall algorithm that identifies an All-Pair Shortest Path(APSP)in an uncertain situation of a network.In the proposed methodology,multiple criteria and theirmutual associationmay involve the selection of any suitable path between any two node points,and the values of these criteria may change due to an uncertain environment.We use trapezoidal picture fuzzy addition,score,and accuracy functions to find APSP.We compute the time complexity of this algorithm and contrast it with the traditional Floyd-Warshall algorithm and fuzzy Floyd-Warshall algorithm.展开更多
Efficient airport airside ground movement(AAGM)is key to successful operations of urban air mobility.Recent studies have introduced the use of multi-objective multigraphs(MOMGs)as the conceptual prototype to formulate...Efficient airport airside ground movement(AAGM)is key to successful operations of urban air mobility.Recent studies have introduced the use of multi-objective multigraphs(MOMGs)as the conceptual prototype to formulate AAGM.Swift calculation of the shortest path costs is crucial for the algorithmic heuristic search on MOMGs,however,previous work chiefly focused on single-objective simple graphs(SOSGs),treated cost enquires as search problems,and failed to keep a low level of computational time and storage complexity.This paper concentrates on the conceptual prototype MOMG,and investigates its node feature extraction,which lays the foundation for efficient prediction of shortest path costs.Two extraction methods are implemented and compared:a statistics-based method that summarises 22 node physical patterns from graph theory principles,and a learning-based method that employs node embedding technique to encode graph structures into a discriminative vector space.The former method can effectively evaluate the node physical patterns and reveals their individual importance for distance prediction,while the latter provides novel practices on processing multigraphs for node embedding algorithms that can merely handle SOSGs.Three regression models are applied to predict the shortest path costs to demonstrate the performance of each.Our experiments on randomly generated benchmark MOMGs show that(i)the statistics-based method underperforms on characterising small distance values due to severe overestimation;(ii)A subset of essential physical patterns can achieve comparable or slightly better prediction accuracy than that based on a complete set of patterns;and(iii)the learning-based method consistently outperforms the statistics-based method,while maintaining a competitive level of computational complexity.展开更多
The All-pairs shortest path problem(ALL-SPP)aims to find the shortest path joining all the vertices in a given graph.This study proposed a new optimal method,Dhouib-matrix-ALL-SPP(DM-ALL-SPP)to solve the ALL-SPP based...The All-pairs shortest path problem(ALL-SPP)aims to find the shortest path joining all the vertices in a given graph.This study proposed a new optimal method,Dhouib-matrix-ALL-SPP(DM-ALL-SPP)to solve the ALL-SPP based on column-row navigation through the adjacency matrix.DM-ALL-SPP is designed to generate in a single execution the shortest path with details among all-pairs of vertices for a graph with positive and negative weighted edges.Even for graphs with a negative cycle,DM-ALL-SPP reported a negative cycle.In addition,DM-ALL-SPP continues to work for directed,undirected and mixed graphs.Furthermore,it is characterized by two phases:the first phase consists of adding by column repeated(n)iterations(where n is the number of vertices),and the second phase resides in adding by row executed in the worst case(n∗log(n))iterations.The first phase,focused on improving the elements of each column by adding their values to each row and modifying them with the smallest value.The second phase is emphasized by rows only for the elements modified in the first phase.Different instances from the literature were used to test the performance of the proposed DM-ALL-SPP method,which was developed using the Python programming language and the results were compared to those obtained by the Floyd-Warshall algorithm.展开更多
文摘This paper presents an efficient parallel algorithm for the shortest path problem in planar layered digraphs that runs in O(log^3n) time with n processors. The algorithms uses a divide and conquer approach and is based on the novel idea of a one-way separator, which has the property that any directed path can be crossed only once.
文摘In most network analysis tools the computation of the shortest paths between all pairs of nodes is a fundamental step to the discovery of other properties. Among other properties is the computation of closeness centrality, a measure of the nodes that shows how central a vertex is on a given network. In this paper, the authors present a method to compute the All Pairs Shortest Paths on graphs that present two characteristics： abundance of nodes with degree value one, and existence of articulation points along the graph. These characteristics are present in many real life networks especially in networks that show a power law degree distribution as is the case of biological networks. The authors＇ method compacts the single nodes to their source, and then by using the network articulation points it disconnects the network and computes the shortest paths in the biconnected components. At the final step the authors proposed methods merges the results to provide the whole network shortest paths. The authors＇ method achieves remarkable speedup compared to state of the art methods to compute the shortest paths, as much as 7 fold speed up in artificial graphs and 3.25 fold speed up in real application graphs. The authors＇ performance improvement is unlike previous research as it does not involve elaborated setups since the authors algorithm can process significant instances on a popular workstation.
基金supported by Northern Border University,Arar,Kingdom of Saudi Arabia,through the Project Number“NBU-FFR-2024-2248-03”.
文摘This study is trying to address the critical need for efficient routing in Mobile Ad Hoc Networks(MANETs)from dynamic topologies that pose great challenges because of the mobility of nodes.Themain objective was to delve into and refine the application of the Dijkstra’s algorithm in this context,a method conventionally esteemed for its efficiency in static networks.Thus,this paper has carried out a comparative theoretical analysis with the Bellman-Ford algorithm,considering adaptation to the dynamic network conditions that are typical for MANETs.This paper has shown through detailed algorithmic analysis that Dijkstra’s algorithm,when adapted for dynamic updates,yields a very workable solution to the problem of real-time routing in MANETs.The results indicate that with these changes,Dijkstra’s algorithm performs much better computationally and 30%better in routing optimization than Bellman-Ford when working with configurations of sparse networks.The theoretical framework adapted,with the adaptation of the Dijkstra’s algorithm for dynamically changing network topologies,is novel in this work and quite different from any traditional application.The adaptation should offer more efficient routing and less computational overhead,most apt in the limited resource environment of MANETs.Thus,from these findings,one may derive a conclusion that the proposed version of Dijkstra’s algorithm is the best and most feasible choice of the routing protocol for MANETs given all pertinent key performance and resource consumption indicators and further that the proposed method offers a marked improvement over traditional methods.This paper,therefore,operationalizes the theoretical model into practical scenarios and also further research with empirical simulations to understand more about its operational effectiveness.
基金supported by the National Natural Science Foundation of China under Grant Nos.61973001,61806001the Natural Science Foundation of Anhui Province under Grant No.1808085MF201+1 种基金the State Key Laboratory for Ocean Big Data Mining and Application of Zhejiang Province under Grant No.OBDMA201502Anhui University Foundation under Grant No.01005102。
文摘The study on how to identify influential spreaders in complex networks is becoming increasingly significant.Previous studies demonstrate that considering the shortest path length can improve the accuracy of identification,but which ignore the influence of the number of shortest paths.In many cases,even though the shortest path length of two nodes is rather larger,their interaction influence is also significant if the number of shortest paths between them is considerable.Inspired by this fact,the authors propose an improved centrality index(ICC)based on well-known closeness centrality and a semi-local iterative algorithm(semi-IA)to study the impact of the number of shortest paths on the identification of the influential spreaders.By comparing with several traditional centrality indices,such as degree centrality,k-shell decomposition,betweenness centrality and eigenvector centrality,the experimental results on real networks indicate that the ICC index and semi-IA have a better performance,regardless of the identification capability or the resolution.
文摘To effectively solve the single-source shortest path(SSSP)problem for massive road networks in geographical information systems,a new synchronization method is proposed in the implementations of parallel SSSP algorithm.It applies spinlock by inline assembly language for the sake of small overheads of controlling the interaction of multiple threads.The performance of our method is compared with widely used Pthreads application programming interfaces and the powerful sequential solution given by DIMACS.The experimental platform is a shared address space workstation with two processors(i.e.eight cores)at a clock speed of 3 GHz.Problem instances for experiments contain a directed road networks of the USA with more than 23 million vertices and 57 million edges,and its 11 subnetworks of variant sizes.This method answers the SSSP of the USA road network in 1231 ms,while Pthreads costs 1808 ms and DIMACS sequential solution takes 4856 ms.It achieves a speedup of 3.95,which is 47%faster than Pthreads with the speedup of 2.69.When the size of instance is larger,our method achieves a better performance.
文摘This paper discusses the problem of finding a shortest path from a fixed origin s to a specified node t in a network with arcs represented as typical triangular fuzzy numbers (TFN). Because of the characteristic of TFNs, the length of any path p from s to t , which equals the extended sum of all arcs belonging to p , is also TFN. Therefore, the fuzzy shortest path problem (FSPP) becomes to select the smallest among all those TFNs corresponding to different paths from s to t (specifically, the smallest TFN represents the shortest path). Based on Adamo's method for ranking fuzzy number, the pessimistic method and its extensions - optimistic method and λ combination method, are presented, and the FSPP is finally converted into the crisp shortest path problems.
文摘Purpose:To contribute to the study of networks and graphs.Design/methodology/approach:We apply standard mathematical thinking.Findings:We show that the distance distribution in an undirected network Lorenz majorizes the one of a chain.As a consequence,the average and median distances in any such network are smaller than or equal to those of a chain.Research limitations:We restricted our investigations to undirected,unweighted networks.Practical implications:We are convinced that these results are useful in the study of small worlds and the so-called six degrees of separation property.Originality/value:To the best of our knowledge our research contains new network results,especially those related to frequencies of distances.
文摘Unlike the shortest path problem that has only one optimal solution and can be solved in polynomial time, the muhi-objective shortest path problem （ MSPP ） has a set of pareto optimal solutions and cannot be solved in polynomial time. The present algorithms focused mainly on how to obtain a precisely pareto optimal solution for MSPP resulting in a long time to obtain multiple pareto optimal solutions with them. In order to obtain a set of satisfied solutions for MSPP in reasonable time to meet the demand of a decision maker, a genetic algo- rithm MSPP-GA is presented to solve the MSPP with typically competing objectives, cost and time, in this pa- per. The encoding of the solution and the operators such as crossover, mutation and selection are developed. The algorithm introduced pareto domination tournament and sharing based selection operator, which can not only directly search the pareto optimal frontier but also maintain the diversity of populations in the process of evolutionary computation. Experimental results show that MSPP-GA can obtain most efficient solutions distributed all along the pareto frontier in less time than an exact algorithm. The algorithm proposed in this paper provides a new and effective method of how to obtain the set of pareto optimal solutions for other multiple objective optimization problems in a short time.
基金Project(2009CB219703) supported by the National Basic Research Program of ChinaProject(2011AA05A117) supported by the National High Technology Research and Development Program of China
文摘In order to form an algorithm for distribution network routing,an automatic routing method of distribution network planning was proposed based on the shortest path.The problem of automatic routing was divided into two steps in the method:the first step was that the shortest paths along streets between substation and load points were found by the basic ant colony algorithm to form a preliminary radial distribution network,and the second step was that the result of the shortest path was used to initialize pheromone concentration and pheromone updating rules to generate globally optimal distribution network.Cases studies show that the proposed method is effective and can meet the planning requirements.It is verified that the proposed method has better solution and utility than planning method based on the ant colony algorithm.
基金Supported by Science Foundation of Heze University(XY14SK14)
文摘Rational planning of agricultural product transport route from initial node to destination node can effectively reduce the cost price of agricultural products,and the calculation of shortest path between any two points also affects people’s daily travel.Taking Heze Railway Station to Heze College for example,with remote sensing image data as the base map,we conduct vectorization and topological analysis on roads in the target area.With Dijkstra as theoretical basis of shortest path algorithm,we use ArcG IS network analysis method to build road network,and calculate the planning program of the shortest distance path,the shortest path by driving and the shortest path by walking.
文摘In this figure, it finds a vertex to another vertex k shortest path algorithm. Provided there are n vertices and edges in the diagram. If the path loops, the time complexity of the algorithm is allowed O（w ＋ n log 2 n ＋ kw log 2 k）. If the request path does not contain the loop, the time complexity of the algorithm O（kn（w ＋ n log2 n）＋ kw log2 k）. The algorithm utilizes a simple extension of the Dijkstra algorithm determined the end of the length of the shortest path to the other vertices, and then, based on these data, branch and bound method to identify the required path. Experimental results show that the actual running time has relations with the structure of FIG.
文摘Finding the shortest path （SP） in a large-scale network analysis between any two nodes is a tough but very significant task. The SP can help us to analyze the information spreading performance and research the latent relationship in the weighted social network, and so on. As the size of the social network increases, the traditional SP algorithms have poor performance and there is not a suitable algorithm for weighted social network. Some features of the network analysis are beneficial to solve this problem, and community structure ignored by the traditional methods is one of the most important features. In this paper, we propose a shortest path algorithm based on community detection （SPCD） by integrating community detection algorithm with traditional search methods. SPCD constructs a community graph by using community structure to narrow the searching scope. The algorithm presented improves the time efficiency and maintains the accuracy scale of the SR Experimental results on five real-world networks demonstrate the effectiveness of the proposed methods for the SP problem.
基金supported by the National Natural Science Foundation of China (Grant No 60672095)the National High-Tech Research and Development Program of China (Grant No 2007AA11Z210)+3 种基金the Doctoral Fund of Ministry of Education of China (Grant No 20070286004)the Natural Science Foundation of Jiangsu Province,China (Grant No BK2008281)the Science and Technology Program of Southeast University,China (Grant No KJ2009351)the Excellent Young Teachers Program of Southeast University,China (Grant No BG2007428)
文摘The shortcomings of traditional methods to find the shortest path are revealed, and a strategy of finding the self- organizing shortest path based on thermal flux diffusion on complex networks is presented. In our method, the shortest paths between the source node and the other nodes are found to be self-organized by comparing node temperatures. The computation complexity of the method scales linearly with the number of edges on underlying networks. The effects of the method on several networks, including a regular network proposed by Ravasz and Barabasi which is called the RB network, a real network, a random network proposed by Ravasz and Barabasi which is called the ER network and a scale-free network, are also demonstrated. Analytic and simulation results show that the method has a higher accuracy and lower computational complexity than the conventional methods.
文摘A shortest path routing algorithm based on transient chaotic neural network is proposed in this paper. Gam-pared with previous models adopting Hopfield neural network, this algorithm has a higher ability to overcome the local minimum, and achieves a better performance. By introducing a special post-processing technique for the output matrixes, our algorithm can obtain an optimal solution with a high probability even for the paths that need more hops in large-size networks.
文摘The time-optimal trajectory planning is proposed under kinematic and dynamic constraints for a 2-DOF wheeled robot. In order to make full use of the motor’s capacity, we calculate the maximum torque and the minimum torque by considering the maximum heat-converted power generated by the DC motor. The shortest path is planned by using the geometric method under kinematic constraints. Under the bound torques, the velocity limits and the maximum acceleration (deceleration) are obtained by combining with the dynamics. We utilize the phase-plane analysis technique to generate the time optimal trajectory based on the shortest path. At last, the computer simulations for our laboratory mobile robot were performed. The simulation results prove the proposed method is simple and effective for practical use.
基金Project supported by the National Natural Science Foundation of China(Grant No.61903266)China Postdoctoral Science Foundation(Grant No.2018M631073)+2 种基金China Postdoctoral Science Special Foundation(Grant No.2019T120829)the Fundamental Research Funds for the Central Universities,ChinaSichuan Science and Technology Program,China(Grant No.20YYJC4001)。
文摘The shortest path is a widely studied network science problem and has attracted great attention.Nevertheless,it draws little attention in temporal networks,in which temporal edges determine information dissemination.In this paper,we propose an information spreading-based method to calculate the shortest paths distribution in temporal networks.We verify our method on both artificial and real-world temporal networks and obtain a good agreement.We further generalize our method to identify influential nodes and found an effective method.Finally,we verify the influential nodes identifying method on four networks.
基金the National Natural Science Foundation of China under Grant No. 60671033.
文摘On the basis of Floyd algorithm with the extended path matrix, a parallel algorithm which resolves all-pair shortest path （APSP） problem on cluster environment is analyzed and designed. Meanwhile, the parallel APSP pipelining algorithm makes full use of overlapping technique between computation and communication. Compared with broadcast operation, the parallel algorithm reduces communication cost. This algorithm has been implemented on MPI on PC-cluster. The theoretical analysis and experimental results show that the parallel algorithm is an efficient and scalable algorithm.
基金extend their appreciation to the Deanship of Scientific Research at King Khalid University for funding this work through General Research Project under Grant No.(R.G.P.2/48/43).
文摘The Floyd-Warshall algorithm is frequently used to determine the shortest path between any pair of nodes.It works well for crisp weights,but the problem arises when weights are vague and uncertain.Let us take an example of computer networks,where the chosen path might no longer be appropriate due to rapid changes in network conditions.The optimal path from among all possible courses is chosen in computer networks based on a variety of parameters.In this paper,we design a new variant of the Floyd-Warshall algorithm that identifies an All-Pair Shortest Path(APSP)in an uncertain situation of a network.In the proposed methodology,multiple criteria and theirmutual associationmay involve the selection of any suitable path between any two node points,and the values of these criteria may change due to an uncertain environment.We use trapezoidal picture fuzzy addition,score,and accuracy functions to find APSP.We compute the time complexity of this algorithm and contrast it with the traditional Floyd-Warshall algorithm and fuzzy Floyd-Warshall algorithm.
基金This work was supported by the UK Engineering and Physical Sciences Research Council(grant no.EP/N029496/1,EP/N029496/2,EP/N029356/1,EP/N029577/1,and EP/N029577/2)the joint scholarship of the China Scholarship Council and Queen Mary,University of London(grant no.202006830015).
文摘Efficient airport airside ground movement(AAGM)is key to successful operations of urban air mobility.Recent studies have introduced the use of multi-objective multigraphs(MOMGs)as the conceptual prototype to formulate AAGM.Swift calculation of the shortest path costs is crucial for the algorithmic heuristic search on MOMGs,however,previous work chiefly focused on single-objective simple graphs(SOSGs),treated cost enquires as search problems,and failed to keep a low level of computational time and storage complexity.This paper concentrates on the conceptual prototype MOMG,and investigates its node feature extraction,which lays the foundation for efficient prediction of shortest path costs.Two extraction methods are implemented and compared:a statistics-based method that summarises 22 node physical patterns from graph theory principles,and a learning-based method that employs node embedding technique to encode graph structures into a discriminative vector space.The former method can effectively evaluate the node physical patterns and reveals their individual importance for distance prediction,while the latter provides novel practices on processing multigraphs for node embedding algorithms that can merely handle SOSGs.Three regression models are applied to predict the shortest path costs to demonstrate the performance of each.Our experiments on randomly generated benchmark MOMGs show that(i)the statistics-based method underperforms on characterising small distance values due to severe overestimation;(ii)A subset of essential physical patterns can achieve comparable or slightly better prediction accuracy than that based on a complete set of patterns;and(iii)the learning-based method consistently outperforms the statistics-based method,while maintaining a competitive level of computational complexity.
文摘The All-pairs shortest path problem(ALL-SPP)aims to find the shortest path joining all the vertices in a given graph.This study proposed a new optimal method,Dhouib-matrix-ALL-SPP(DM-ALL-SPP)to solve the ALL-SPP based on column-row navigation through the adjacency matrix.DM-ALL-SPP is designed to generate in a single execution the shortest path with details among all-pairs of vertices for a graph with positive and negative weighted edges.Even for graphs with a negative cycle,DM-ALL-SPP reported a negative cycle.In addition,DM-ALL-SPP continues to work for directed,undirected and mixed graphs.Furthermore,it is characterized by two phases:the first phase consists of adding by column repeated(n)iterations(where n is the number of vertices),and the second phase resides in adding by row executed in the worst case(n∗log(n))iterations.The first phase,focused on improving the elements of each column by adding their values to each row and modifying them with the smallest value.The second phase is emphasized by rows only for the elements modified in the first phase.Different instances from the literature were used to test the performance of the proposed DM-ALL-SPP method,which was developed using the Python programming language and the results were compared to those obtained by the Floyd-Warshall algorithm.
