The flexible and dynamic operation condition of the power system requires that the fault isolation scheme has sufficient adaptability. A novel fault isolation scheme based on wide-area information is ...proposed in this article. Based on graph theory, the adjacency matrices of the electrical components and circuit breakers are constructed. The real-time switch status data is exploited to reflect the dynamic changes of the network topology. Then, the tripping path of the circuit breaker connecting each protected electrical component is searched by the Floyd-Warshall algorithm to formulate the fault isolation set for all protected electrical components. The proposed approach is applied to fault isolation from a wide-area perspective, and it is not affected by system coordination and selectivity compared with the one based on local information. The effectiveness of the proposed scheme is verified on a power system with the typical electrical connection under the cases of a single fault, multiple faults, circuit breaker failure, and substation with the outage of dc power supply, and the case where the circuit breakers cannot trip. Since the tripping sequence of the circuit breakers is determined before the fault occurs, even with dynamic changes of the power system conditions, the proposed scheme can minimize the fault isolation zone with low fault clearance time.
Multi-point shortest path planning problem is a typical problems in discrete optimization. The bat algorithm is a nature-inspired metaheuristic optimization algorithm that is used in a wide range of ...fields. However, there is one problem with the BA, which is easy to premature. To solve multi-point shortest path planning problem, an improved discrete bat algorithm (IDBA) is proposed in this paper. In this algorithm, the Floyd–Warshall algorithm is first used to transform an incomplete connected graph into a complete graph whose vertex set consists of a start point and necessary points. Then the algorithm simulates the bats’ foraging and obstacle avoidance process to find the shortest path in the complete graph to satisfy the constraints. Finally, the path is transferred to the original incomplete graph to get the solution. In order to overcome the premature phenomenon of a discrete bat algorithm, the modified neighborhood operator is proposed. To prove the effectiveness of our method, we compared its performance in 26 instances with the results obtained by three different algorithms: DBA, IBA and GSA-ACS-PSOT. We also performed a sensitivity analysis on the parameters. The results indicate that the improved bat algorithm outperforms all the other alternatives in most cases.
•Multi-point shortest path planning problem is solved by using an improved discrete bat algorithm (IDBA).•An incomplete connected graph is first converted into a complete graph.•The bats’ foraging and obstacle avoidance process are then simulated to find the shortest path in the complete graph.•The path is finally transferred to the original incomplete graph to get the solution.
As start-up companies may leverage information spreading through Instagram's hashtag-setting, algorithms in influence maximization can be encoded. The objective is to find a maximum impact which can ...activate users in spreading advertisement marketing campaign through social network. This paper contributes an influence analysis on Instagram and reproduces it into a hashtag network by transforming postings with hashtag interdependence. In finding optimal paths such network structure with influence probabilities, we employ Floyd-Warshall algorithm under uncertainty. The technique is simulated on Indonesian FnB unicorn company and demonstrated in numerical example. The result shows that the hashtag #promokopi may impact the most.
The Floyd–Warshall algorithm is a simple and widely used algorithm to compute shortest paths between all pairs of vertices in an edge weighted directed graph. It can also be used to detect the ...presence of negative cycles. We will show that for this task many existing implementations of the Floyd–Warshall algorithm will fail because exponentially large numbers can appear during its execution.
This paper focuses on measuring the industrial sector’s position on the Global Value Chain (GVC), as reinforcements to the present studies on international trade. We firstly reconsidered the ...length-related and position-related measures in literatures about vertical specialization from the perspective of bibliometrics and econophysics. Secondly, the inter-country and inter-sector propagating process of intermediate goods was redefined, resulting in the concept of Strongest Relevance Path Length (SRPL) based on Revised Floyd–Warshall Algorithm (RFWA). Thirdly, enlightened by closeness centrality, we introduced two new SRPL-based indices to measure the Interdependence from a given sector to all its upstream and downstream sectors, and proposed Relative Upstreamness Index (RUI) to measure the relative position of the industrial sector. Finally, these indices were applied to the empirical analysis of the global economic system by physical statistics.
•SRPL-based closeness centralities measure the position of sectors on the GVC.•Relative upstreamness index embodies the relative position of sectors on the GVC.•China surpassed the United States except in the field of services sectors.•Agriculture and mining sectors have much closer relations with the demand-side.•Manufacturing sectors require more supports from the supply-side.
We present a new approach for solving the All-Pairs Shortest-Path (APSP) problem for planar graphs that exploits the massive on-chip parallelism available in today’s Graphics Processing Units (GPUs). ...We describe two new algorithms based on our approach. Both algorithms use Floyd–Warshall method, have near optimal complexity in terms of the total number of operations, while their matrix-based structure is regular enough to allow for efficient parallel implementation on the GPUs. By applying a divide-and-conquer approach, we are able to make use of multi-node GPU clusters, resulting in more than an order of magnitude speedup over fastest known Dijkstra-based GPU implementation and a two-fold speedup over a parallel Dijkstra-based CPU implementation.
•We develop a new approach for the All-Pairs Shortest Path problem in planar graphs.•We target execution on large CPU–GPU clusters and graphs with millions of vertices.•We design a centralized (master/slave) and a decentralized (distributed) version.•Our algorithms are work-efficient and allow a high-degree of parallelism.•Our algorithms are significantly faster than the previous ones.
Abstract
With the development of the society, people increasingly frequent application in social network, the formation of social networking groups become important step in people’s life. How to ...analyze the evolution of social network group relations become very important. In this paper, an Floyd-Warshall evolution relations algorithm based on social networks key groups is proposed. Mainly includes four parts, initial construction of social network group relations, social big data acquisition, network group relations weighting, and group relations reconstruction. Experimental results show that, by analyzing group communication frequency, group membership relationship and the number of social group members, the evolution map of social network group relationship can be obtained, which can make a more intuitive analysis and expression of the development process of social network group and the evolution of social network group relationship.
The Sumba region, Indonesia, is known for its extraordinary natural beauty and unique cultural richness. There are 19 interesting tourist attractions spread throughout the area, but tourists often ...face difficulties in planning efficient visiting routes. From this case, it can be solved by applying graph theory in terms of searching for the shortest distance which is completed using the shortest path search algorithm. Then these 19 tourist objects are used to build a weighted graph, where the nodes represent the tourist objects and the edges of the graph describe the distance or travel time between these objects. Therefore, this research aims to compare the shortest path search algorithm with parameters to compare the shortest distance results, algorithm complexity and execution time for tourism in the Sumba area. The results of this research involve a comparison of several shortest path search algorithms, with the aim of finding the shortest distance results, algorithm complexity, and execution time for tourism in the Sumba area. Based on the test results of the five algorithms with the parameters that have been prepared, and the findings show that each algorithm has its own characteristics, the results are as follows: Dijkstra's algorithm can be used to calculate the shortest route for single-source and single-destination types. This resembles the Bellman-Ford algorithm, only the Bellman-Ford algorithm can be used simultaneously on graphs that have negative weight values. Meanwhile, the Floyd-Warshall algorithm is suitable for use on the all-pairs type. Then, the Johnson Algorithm can be used to determine the shortest path from all pairs of paths where the destination node is located in the graph. Finally, the Ant Colony algorithm to compute from a node to each pair of destination nodes.
PDF
