Optimizing set of paths connecting multiple source-sink pairs

Abstract

In this paper we aim to propose an algorithm for finding the most optimal path with some must-include nodes. The algorithm will be used to look for the best path that includes all the required nodes arranged in static topology in the most cost efficient way while keeping in mind the given constraint. We have developed the algorithm for nodes, where information about all nearby nodes is available beforehand. The main aim of the algorithm is to get the optimal paths between nodes with the given constraints. After getting all optimal paths, the algorithm will use a heuristic function to determine the best path out of the all paths as the final path. The main aim of our proposed methodology is to minimize the input resources to achieve the maximum output. For doing this we have proposed a method to combine multiple paths from a source to sink in one single optimal path, thus reducing the number of paths and achieving the same output. For developing this algorithm we have used concepts of graph theory, combinatorial optimizations and well known approach of Knuth for finding exact cover for given graph. © 2016 IEEE.