China
Africa
Explore chapters and articles related to this topic
Network Analysis
Published in Michael W. Carter, Camille C. Price, Ghaith Rabadi, Operations Research, 2018
Michael W. Carter, Camille C. Price, Ghaith Rabadi
Suppose we have a network for which we would like to know the shortest distance between any two nodes. This is called the all-pairs shortest path problem. For this problem, Dijkstra’s algorithm could be applied n times (using a different node each time as the source) to obtain the desired result in time O(n3). Another algorithm known as Floyd’s algorithm provides the solution in a more direct way, also in time O(n3) but with a much lower constant factor than Dijkstra’s algorithm. However, for large sparse graphs, clever use of data structures will allow Dijkstra’s algorithm to operate in O(n e log n) time. Algorithms for the second shortest path through a network, the n-th shortest path, and for all possible paths between two specified nodes, are described and illustrated in Price (1971).
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
The advantage of adjacency lists over matrix representations is less memory usage. Indeed, a full incidence matrix requires O(|V|×|ℰ|) memory, and a full adjacency matrix requires O(|V|2) memory. However, sparse graphs can take advantage of sparse matrix representations for a much more efficient storage.
Optimal Path Planning of an Unmanned Surface Vehicle in a Real- Time Marine Environment using a Dijkstra Algorithm
Published in Adam Weintrit, Marine Navigation, 2017
Y. Singh, S. Sharma, R. Sutton, D. Hatton
There are various variants of the Dijkstra algorithm. The variant used in this study fixes a source node which is the start point of the USV and finds the shortest paths from source node to all other nodes in the graph leading to shortest- path tree. In order to reduce the computational load in the original variant, a sparse graph i.e. graph with fewer edges approach has been adopted leading to more efficient storage of graph nodes. The algorithm is defined in Algorithm 1 (Ahuja, 1990).
Improved formulations of the joint order batching and picker routing problem
Published in International Journal of Production Research, 2022
Let denote a set of picking locations, each of which is on a subaisle and contains one or more requested products. Let denote a set of endpoints of each subaisle, and we call these points ‘artificial locations’. For simplicity, we assume that the origin s is located at the top left corner of the warehouse, and it just overlaps the first artificial location. We define a sparse graph using the vertex set and the edge set E. Edges in E connect the following pair of vertices: (1) two neighboring locations within a picking aisle and (2) two neighboring artificial locations within a cross-aisle. The length of any edge is equal to the direct distance between two locations. The graphical representation of a warehouse is shown in Figure 2.
Anomaly detection in large-scale networks: A state-space decision process
Published in Journal of Quality Technology, 2021
Abdullah Alghuried, Ramin Moghaddass
All of the above variables for large-scale sparse networks can be determined from the adjacency lists with labeled nodes, which are known as the most common representations for sparse graphs. For node i, adjacency list Ai is defined as an array A, which contains all the vertices that are adjacent to any vertex i. Since most real-world networks have a large structure, and thus, have large sparse graphs, representing the edges using adjacency lists for such systems requires less storage space.
Assessing network vulnerability using shortest path network problems
Published in Journal of Transportation Safety & Security, 2021
Identifying the shortest path from origin to destination is one of the recognized network performance functions. The “shortest path” could be variously defined as that covering the least distance, taking the least travel time, or incurring the least travel cost, depending on the types of network cost structure. In general, there are two approaches to construct the shortest path problems – algorithmic approach and mathematical programing approach. First, algorithmic approach is widely used in practice because of its easy implementation, and computationally reasonable to have optimal solutions. Given this approach, three classical types of shortest path problems are mentioned: single-source shortest path problem, all-pairs shortest path problem, and k-shortest path problem. Single-source shortest path problem refers to the problem that finding shortest paths from one node to all other nodes in a network (Ahuja et al., 1993). The Dijkstra’s algorithm (Dijkstra, 1959; Whiting and Hillier, 1960; Dantzig, 1960) identifies the shortest path from a single source node to other nodes in directional networks. With slight modification, the reverse Dijkstra’s algorithm searches for the shortest path from all other nodes to a single sink node; the bidirectional Dijkstra’s algorithm recognizes the shortest path from a single source node to a specific sink node. When arcs with negative length present, the Bellman–Ford algorithm (Ford and Lester, 1956; Bellman, 1958) is adopted to handle the single-source shortest path problem. All-pairs shortest path problem refers to the problem that finding the shortest paths from every node to every other node in a network. Floyd (1962) presented an algorithm to find all the shortest paths in a network, where the arc lengths can be negative but no circuits can have negative length. The Floyd–Warshall algorithm returns a matrix of the shortest paths among all node pairs through comparing all possible paths from origin to destination especially in dense networks. Johnson's algorithm (Johnson, 1977) is faster and more efficient in solving all-pairs shortest path problem on sparse graphs. In contrast, k-shortest path problem refers to the problem that finding the shortest path as well as the other k-1 paths, such as the second shortest path and the third shortest path, etc. K specifies the total number of shortest paths to be identified. Bock et al. (1957) developed a method to find all possible paths from source to sink and then rank them systematically. Bellman and Kalaba (1960) described a method in searching k shortest paths for larger networks that finding k shortest paths from all origins to a given set of destinations.