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.展开更多
This study proposes a decentralized urban traffic optimization approach by integrating Dijkstra’s algorithm with edge computing.The system models road networks as dynamic graphs,using real-time data from IoT sensors ...This study proposes a decentralized urban traffic optimization approach by integrating Dijkstra’s algorithm with edge computing.The system models road networks as dynamic graphs,using real-time data from IoT sensors to adapt routing decisions.A three-layer architecture reduces latency and im-proves scalability.Simulation results show a 42% decrease in response time and a 25%reduction in congestion compared to centralized systems.The ap-proach demonstrates high reliability and potential for smart city applications.展开更多
We propose a high-performance path planning algorithm for automatic target tracking in the applications of real-time simulation and visualization of large-scale terrain datasets, with a large number of moving objects ...We propose a high-performance path planning algorithm for automatic target tracking in the applications of real-time simulation and visualization of large-scale terrain datasets, with a large number of moving objects （such as vehicles） tracking multiple moving targets. By using a modified Dijkstra＇s algorithm, an optimal path between each vehicle-target pair over a weighted grid-presented terrain is computed and updated to eliminate the problem of local minima and losing of tracking. Then, a dynamic path re-planning strategy using multi-resolution representation of a dynamic updating region is proposed to achieve high-performance by trading-off precision for efficiency, while guaranteeing accuracy. Primary experimental results showed that our algorithm successfully achieved l0 to 96 frames per second interactive path-replanning rates during a terrain simulation scenario with 10 to 100 vehicles and multiple moving targets.展开更多
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 the shipbuilding industry,market competition is currently operating in an intense state.To be able to strive in the global market,the shipbuilders must able to produce ships that are more efficient and can be const...In the shipbuilding industry,market competition is currently operating in an intense state.To be able to strive in the global market,the shipbuilders must able to produce ships that are more efficient and can be constructed in a relatively short amount of time.The piping layouts in the engine room requires a lot of time for the designer to design the best possible route and in a way are not the most efficient route.This paper presents an automatic piping support system in the ship’s engine room based on the Dijkstra’s algorithm of pathfinding method.The proposed method is focused on finding the shortest possible route with a consideration of the following things:cost of the bend pipe,cost of the crossing pipe,cost reduction by pipe support,restriction on piping,reduction of calculation time,and design procedure of piping route.Dijkstra’s shortest path algorithm is adopted to find the shortest path route between the start and goal point that is determined based on the layout of the ship’s engine room.Genetic algorithm is adopted to decide the sequence of the pipe execution.The details of the proposed method are explained in this paper.This paper also discusses the application of the proposed method on an actual ship and evaluates its effectiveness.展开更多
In recent years, Japan, and especially rural areas have faced the growing problems of debt-ridden local railway lines along with the population decline and aging population. Therefore, it is best to consider the disco...In recent years, Japan, and especially rural areas have faced the growing problems of debt-ridden local railway lines along with the population decline and aging population. Therefore, it is best to consider the discontinuation of local railway lines and introduce replacement buses to secure the transportation methods of the local people especially in rural areas. Based on the above background, targeting local railway lines that may be discontinued in the near future, appropriate bus stops when provided with potential bus stops were selected, the present study proposed a method that introduces routes for railway replacement buses adopting ant colony optimization (ACO). The improved ACO was designed and developed based on the requirements set concerning the route length, number of turns, road width, accessibility of railway lines and zones without bus stops as well as the constraint conditions concerning the route length, number of turns and zones without bus stops. Original road network data were generated and processed adopting a geographic information systems (GIS), and these are used to search for the optimal route for railway replacement buses adopting the improved ACO concerning the 8 zones on the target railway line (JR Kakogawa line). By comparing the improved ACO with Dijkstra’s algorithm, its relevance was verified and areas needing further improvements were revealed.展开更多
Purpose-Isometric feature mapping(Isomap)is a very popular manifold learning method and is widely used in dimensionality reduction and data visualization.The most time-consuming step in Isomap is to compute the shorte...Purpose-Isometric feature mapping(Isomap)is a very popular manifold learning method and is widely used in dimensionality reduction and data visualization.The most time-consuming step in Isomap is to compute the shortest paths between all pairs of data points based on a neighbourhood graph.The classical Isomap(C-Isomap)is very slow,due to the use of Floyd’s algorithm to compute the shortest paths.The purpose of this paper is to speed up Isomap.Design/methodology/approach-Through theoretical analysis,it is found that the neighbourhood graph in Isomap is sparse.In this case,the Dijkstra’s algorithm with Fibonacci heap(Fib-Dij)is faster than Floyd’s algorithm.In this paper,an improved Isomap method based on Fib-Dij is proposed.By using Fib-Dij to replace Floyd’s algorithm,an improved Isomap method is presented in this paper.Findings-Using the S-curve,the Swiss-roll,the Frey face database,the mixed national institute of standards and technology database of handwritten digits and a face image database,the performance of the proposed method is compared with C-Isomap,showing the consistency with C-Isomap and marked improvements in terms of the high speed.Simulations also demonstrate that Fib-Dij reduces the computation time of the shortest paths from O(N3)to O(N2lgN).Research limitations/implications-Due to the limitations of the computer,the sizes of the data sets in this paper are all smaller than 3,000.Therefore,researchers are encouraged to test the proposed algorithm on larger data sets.Originality/value-The new method based on Fib-Dij can greatly improve the speed of Isomap.展开更多
基金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.
文摘This study proposes a decentralized urban traffic optimization approach by integrating Dijkstra’s algorithm with edge computing.The system models road networks as dynamic graphs,using real-time data from IoT sensors to adapt routing decisions.A three-layer architecture reduces latency and im-proves scalability.Simulation results show a 42% decrease in response time and a 25%reduction in congestion compared to centralized systems.The ap-proach demonstrates high reliability and potential for smart city applications.
基金Project partially supported by NSF (No. CCR0306438) and theBoeing Company, USA
文摘We propose a high-performance path planning algorithm for automatic target tracking in the applications of real-time simulation and visualization of large-scale terrain datasets, with a large number of moving objects （such as vehicles） tracking multiple moving targets. By using a modified Dijkstra＇s algorithm, an optimal path between each vehicle-target pair over a weighted grid-presented terrain is computed and updated to eliminate the problem of local minima and losing of tracking. Then, a dynamic path re-planning strategy using multi-resolution representation of a dynamic updating region is proposed to achieve high-performance by trading-off precision for efficiency, while guaranteeing accuracy. Primary experimental results showed that our algorithm successfully achieved l0 to 96 frames per second interactive path-replanning rates during a terrain simulation scenario with 10 to 100 vehicles and multiple moving targets.
基金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.
基金supported the Directorate of Research and Community Engagement,Universitas Indonesia,and scheme of Research Collaboration,contract number:NKB-1954/UN2.R3.1/HKP.05.00/2019.
文摘In the shipbuilding industry,market competition is currently operating in an intense state.To be able to strive in the global market,the shipbuilders must able to produce ships that are more efficient and can be constructed in a relatively short amount of time.The piping layouts in the engine room requires a lot of time for the designer to design the best possible route and in a way are not the most efficient route.This paper presents an automatic piping support system in the ship’s engine room based on the Dijkstra’s algorithm of pathfinding method.The proposed method is focused on finding the shortest possible route with a consideration of the following things:cost of the bend pipe,cost of the crossing pipe,cost reduction by pipe support,restriction on piping,reduction of calculation time,and design procedure of piping route.Dijkstra’s shortest path algorithm is adopted to find the shortest path route between the start and goal point that is determined based on the layout of the ship’s engine room.Genetic algorithm is adopted to decide the sequence of the pipe execution.The details of the proposed method are explained in this paper.This paper also discusses the application of the proposed method on an actual ship and evaluates its effectiveness.
文摘In recent years, Japan, and especially rural areas have faced the growing problems of debt-ridden local railway lines along with the population decline and aging population. Therefore, it is best to consider the discontinuation of local railway lines and introduce replacement buses to secure the transportation methods of the local people especially in rural areas. Based on the above background, targeting local railway lines that may be discontinued in the near future, appropriate bus stops when provided with potential bus stops were selected, the present study proposed a method that introduces routes for railway replacement buses adopting ant colony optimization (ACO). The improved ACO was designed and developed based on the requirements set concerning the route length, number of turns, road width, accessibility of railway lines and zones without bus stops as well as the constraint conditions concerning the route length, number of turns and zones without bus stops. Original road network data were generated and processed adopting a geographic information systems (GIS), and these are used to search for the optimal route for railway replacement buses adopting the improved ACO concerning the 8 zones on the target railway line (JR Kakogawa line). By comparing the improved ACO with Dijkstra’s algorithm, its relevance was verified and areas needing further improvements were revealed.
基金supported by the National Natural Science Foundation of China under Grant Nos 91220301,61273314 and 61175064.
文摘Purpose-Isometric feature mapping(Isomap)is a very popular manifold learning method and is widely used in dimensionality reduction and data visualization.The most time-consuming step in Isomap is to compute the shortest paths between all pairs of data points based on a neighbourhood graph.The classical Isomap(C-Isomap)is very slow,due to the use of Floyd’s algorithm to compute the shortest paths.The purpose of this paper is to speed up Isomap.Design/methodology/approach-Through theoretical analysis,it is found that the neighbourhood graph in Isomap is sparse.In this case,the Dijkstra’s algorithm with Fibonacci heap(Fib-Dij)is faster than Floyd’s algorithm.In this paper,an improved Isomap method based on Fib-Dij is proposed.By using Fib-Dij to replace Floyd’s algorithm,an improved Isomap method is presented in this paper.Findings-Using the S-curve,the Swiss-roll,the Frey face database,the mixed national institute of standards and technology database of handwritten digits and a face image database,the performance of the proposed method is compared with C-Isomap,showing the consistency with C-Isomap and marked improvements in terms of the high speed.Simulations also demonstrate that Fib-Dij reduces the computation time of the shortest paths from O(N3)to O(N2lgN).Research limitations/implications-Due to the limitations of the computer,the sizes of the data sets in this paper are all smaller than 3,000.Therefore,researchers are encouraged to test the proposed algorithm on larger data sets.Originality/value-The new method based on Fib-Dij can greatly improve the speed of Isomap.
