An Efficient Algorithm for Enumerating all Minimal Paths of a Graph

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.

Khalid Housni. “An Efficient Algorithm for Enumerating all Minimal Paths of a Graph”. International Journal of Advanced Computer Science and Applications (IJACSA) 10.1 (2019). http://dx.doi.org/10.14569/IJACSA.2019.0100159

@article{Housni2019,
title = {An Efficient Algorithm for Enumerating all Minimal Paths of a Graph},
journal = {International Journal of Advanced Computer Science and Applications},
doi = {10.14569/IJACSA.2019.0100159},
url = {http://dx.doi.org/10.14569/IJACSA.2019.0100159},
year = {2019},
publisher = {The Science and Information Organization},
volume = {10},
number = {1},
author = {Khalid Housni}
}