Neutrosophic Shortest Path Problem (NSPP) in a Directed Multigraph

Abstract

One of the important non-linear data structures in Computer Scienceis graph. Most of the real life network, be it a road transportation network, orairlines network ora communication network etc., cannotbe exactly transformed into a graph model, but into a Multigraphsmodel. The Multigraph is a topological generalization of the graph where multiple links (or edges/arcs) mayexist between twonodesunlike in graph. The existing algorithms to extractthe neutrosophic shortestpath in a graph cannotbe applied to a Multigraphs.In this paper a method is developed to extract the neutrosophic shortest path in a directed Multigraphand then the corresponding algorithmis designed. The classical Dijkstra’s algorithm is applicable to graphs only where all the link weightsare crisp, but we borrow this concept to apply to Multigraphswhere the weights of the linksare neutrosophic numbers (NNs). This newmethod may be useful in many application areas of computer science, communication networks, transportation networks, etc. in particular in those type of networks which cannotbe modelledinto graphs but into Multigraphs.