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 92
- Downloads 0
Role of Requirements Elicitation & Prioritization to Optimize Quality in Scrum Agile Development
One of most common aspect with traditional software development is managing requirements. As requirements emerge throughout the software development process and thus are needed to be addressed through proper communicatio...
Reengineering Framework to Enhance the Performance of Existing Software
Term reengineering refers to improve the quality of the system. Continues maintenance and aging degrade the performance of the software system. Right approach and methodology must be adapted to perform reengineering. Wit...
Development of Mobile-Interfaced Machine Learning-Based Predictive Models for Improving Students’ Performance in Programming Courses
Student performance modelling (SPM) is a critical step to assessing and improving students’ performances in their learning discourse. However, most existing SPM are based on statistical approaches, which on one hand are...
Computer Students Attitudes on the Integration of m-Learning Applications
Technology has an important role in the lives particularly in the field of education nowadays because of its accessibility and affordability. Mobile learning (m-Learning) which is form of e-learning is a novel approach i...
Audio Watermarking with Error Correction
In recent times, communication through the internet has tremendously facilitated the distribution of multimedia data. Although this is indubitably a boon, one of its repercussions is that it has also given impetus to the...