China
Africa
Explore chapters and articles related to this topic
Energy-Efficient Unicast and Multicast Communication for Wireless Ad Hoc Networks Using Multiple Criteria
Published in Jonathan Loo, Jaime Lloret Mauri, Jesús Hamilton Ortiz, Mobile Ad Hoc Networks, 2016
Christos Papageorgiou, Panagiotis Kokkinos, Emmanouel Varvarigos
A multicost routing algorithm consists of two phases [47]. In the first phase, an enumeration of an appropriate set of candidate paths for a given source–destination pair is performed. This can be viewed as a generalization of Dijkstra’s algorithm. The basic difference of this algorithm with Dijkstra’s algorithm is that a set of paths between a source node and a destination node is obtained, instead of a single path. Also, a destination node for which a path has already been found may have to be considered again later. The set of candidate paths that a multicost routing algorithm produces at the end of the first phase consists of the so-called nondominated paths. These are paths for which it is impossible to find other paths that are better with respect to one cost parameter (of their cost vectors) without being worse with respect to some other cost parameter. This reduces to a large extent the algorithm’s computational effort, since the optimization function does not need to be applied to every possible path between a certain source–destination pair. An example of the enumeration of the nondominated paths is given in Figure 8.1, where an additive cumulative parameter h and a restrictive parameter R are assumed. In the second phase, the optimal path is chosen from this set according to the optimization function f(V) used.
Flight Planning
Published in Yasmina Bestaoui Sebbane, Multi-UAV Planning and Task Allocation, 2020
The A* algorithm is based on Dijkstra’s algorithm. It focuses the search in the graph toward the goal. A heuristic value is added to the objective function. It must be a lower-bound estimate of the distance from the current vertex to the goal vertex. A* heuristic algorithm computes the shortest path from one given start node to one given goal node. Distance graph with relative distance information between all nodes plus lower bounds of distance to goal from each node are required. In every step, it expands only the currently shortest path by adding adjacent node with shortest distance including estimate of remaining distance to goal. The algorithm stops when the goal vertex has been treated in the priority queue.
Graph theory concepts and definitions used in image processing and analysis
Published in Olivier Lézoray, Leo Grady, Image Processing and Analysis with Graphs, 2012
To compute the shortest path from one vertex to all the others, the most common algorithm is from Dijkstra [13]. Dijkstra’s algorithm solves the problem for every pair υi, υj, where υi is a fixed starting point and υj∈V. Dijkstra’s algorithm exploits the property that the path between any two nodes contained in a shortest path is also a shortest path. Specifically, let π(υi, υj) be a shortest path from υi to υj in a weighted connected graph G=(V,ℰ) with positive weights (w:ℰ→ℝ+) and let υk be a vertex in π(υi, υj). Then, the subpath π(υi, υk) ⊂ π(υi, υj) is a shortest path from υi to υk. Dijkstra’s algorithm for computing shortest paths with υi as a source is provided in Figure 1.7 with an example on a given graph. In computer vision, shortest paths have been used for example, for interactive image segmentation [14, 15].
A method for finding a least-cost corridor on an ordinal-scaled raster cost surface
Published in Annals of GIS, 2023
Lindsi Seegmiller, Takeshi Shirabe
The two assumptions also motivate an efficient solution method for the problem. It converts a raster cost surface to a graph in which nodes represent cells and arcs represent pairs of adjacent cells, and equates the length of each arc with the cost-weighted distance between the corresponding cells. A least-cost path on the original cost surface corresponds to a shortest path in the derived graph, which can be searched for by any classic shortest path algorithm such as the one by Dijkstra (1959). Dijkstra’s algorithm in its original form has a complexity of O(n2) where n represents the number of nodes (or cells in the present context). It has a better complexity with an advanced data structure such as a priority queue or heap (Ahuja, Magnanti, and Orlin 1993), and its actual computation time may be shortened with a heuristic such as A* (Hart, Nilsson, and Raphael 1968).
Smartphone-based parking guidance algorithm and implementation
Published in Journal of Intelligent Transportation Systems, 2021
Hongyan Gao, Qian Yun, Rundong Ran, Jun Ma
Next, we will discuss the computational complexity of the proposed algorithm. The weights calculation is conducted offline by AHP method. The online computation consists of Dijkstra algorithm, normalization, linear weighted sum and sorting operation. The computational complexity of the Dijkstra algorithm is O(n2), n is the number of nodes in search scope. In the absence of heuristics, the traditional Dijkstra algorithm examines all possible nodes on the network from the source node to the destination node. Many unnecessary nodes involve in the computation, resulting in time complexity in a large traffic network. So, this work restricts search scope as rectangular area to reduce the number of examined nodes and further improve computation efficiency. The linear weighted sum operation is a linear time complexity of O(m). The normalization and sorting operation take O(m2) time, where m is the number of the candidate parking lots. Generally, the number of the candidate parking lots within the accepted walking distance is small, so the complexity is reduced in practical application. According to the computational complexity analysis, the algorithm is able to respond user’s request timely.
Changeability analysis for existing systems
Published in Australian Journal of Multi-Disciplinary Engineering, 2020
Dylan M. Dwyer, Mahmoud Efatmaneshnik
Accounting for multiple transition paths at once brings about a new challenge for determining the most cost efficient way for achieving either specific or most desirable end states. Utilising the introduced extensions to the FOD method in this section, such as filtering beyond cost-based criteria and within particular performance thresholds or design constraints, it would become possible to strategically transition through the tradespace network to reach a desirable system end state. This notion is herein referred to as changeability path analysis (CPA). This problem bears many similarities to the typical shortest path problem (SPP). The SPP is a well-studied combinatorial optimisation problem (Ahuja et al. 1990), whereby the goal is to determine the shortest2 path between two nodes in a network. Algorithms that were established to resolve the SPP are likely to be applicable to CPA, such as the Dijkstra algorithm. The Dijkstra algorithm works by determining the shortest path between a source node and every other node, or a single destination node within a network comprising nodes and arcs (Dijkstra 1959). To determine the shortest path, the arcs have properties such as weights which may represent distance or any other minimum-based goal. In this manner, the typical network compatible with the Dijkstra algorithm is similar to the traditional tradespace network discussed throughout. Therefore, in applying the Dijkstra algorithm to an established tradespace network, the shortest path between an initial system state and the most desirable system end state could be found.