An Efficient Algorithm for Enumerating all Minimal Paths of a Graph
Journal Title: International Journal of Advanced Computer Science & Applications - Year 2019, Vol 10, Issue 1
Abstract
The enumeration of all minimal paths between a terminal pair of a given graph is widely used in a lot of applications such as network reliability assessment. In this paper, we present a new and efficient algorithm to generate all minimal paths in a graph G(V, E). The algorithm proposed builds the set of minimal paths gradually, starting from the source nodes. We present two versions of our algorithm; the first version determines all feasible paths between a pair of terminals in a directed graph without cycle, and this version runs in linear time O(|V| + |E|). The second version determines all minimal paths in a general graph (directed and undirected graph). In order to show the process and the effectiveness of our method, an illustrative example is presented for each case.
Authors and Affiliations
Khalid Housni
Keywords
Related Articles
- EP ID EP448908
- DOI 10.14569/IJACSA.2019.0100159
- Views 107
- Downloads 0
DDoS Attacks Classification using Numeric Attribute-based Gaussian Naive Bayes
Cyber attacks by sending large data packets that deplete computer network service resources by using multiple computers when attacking are called Distributed Denial of Service (DDoS) attacks. Total Data Packet and import...
Method for Productive Cattle Finding with Estrus Cycle Estimated with BCS and Parity Number and Hormone Treatments based on a Regressive Analysis
Estrus cycle estimation method through correlation analysis among influencing factors based on regressive analysis is carried out for Japanese Dairy Cattle Productivity Analysis. Through the experiments with 280 Japanese...
Capacitated Vehicle Routing Problem Solving using Adaptive Sweep and Velocity Tentative PSO
Vehicle Routing Problem (VRP) has become an integral part in logistic operations which determines optimal routes for several vehicles to serve customers. The basic version of VRP is Capacitated VRP (CVRP) which considers...
Downlink and Uplink Message Size Impact on Round Trip Time Metric in Multi-Hop Wireless Mesh Networks
In this paper, the authors propose a novel real-time study metrics of Round Trip Time (RTT) for Multi-Hop Wireless Mesh Networks. They focus on real operational wireless networks with fixed nodes, such as industrial wire...
Application of Artificial Neural Network and Information Gain in Building Case-Based Reasoning for Telemarketing Prediction
Traditionally, case-based reasoning (CBR) has been used as advanced technique for representing expert knowledge and reasoning. However, for stochastic business data such as customers’ behavior and users’ preferences, the...