Abstract
In the last decade, concealed by uncertain atmosphere, many algorithms have been studied deeply to workout the shortest path problem. In this paper, we compared the shortest path problem with various existing algorithms. Finally, we concluded the best algorithm for certain environment.
Similar content being viewed by others
Avoid common mistakes on your manuscript.
Introduction
SPP is a cardinal issue among familiar connectional problems which occur in different areas of engineering and science, such as application in highway networks, portage and conquer in intelligence channels and problem of scheduling. The SPP focuses on recommending the path which has minimum length enclosed by two vertices. The length of the arc/edge produces the quantities of the real life, namely cost, time, etc. In the case of conventional method of measuring SP, the length of each bend is assumed as a crisp numbers. If there is uncertainty on the parameters in the network, then the length can be represented by fuzzy number.
In the current preceding, many of the SPPs with various types of input data have been examined in junction with fuzzy, intuitionistic, vague, interval fuzzy, interval-valued intuitionistic fuzzy and neutrosophic sets [2, 3, 8, 9, 11, 13, 14, 17–20, 23, 30, 39, 46,47,48,49,50,51,52, 83,84,85,86,87,88,89,90,91,92]. Up until now plenty of new algorithms have been designed.
The paper is arranged as: section “Preliminaries” comprehends the primary definitions and overviewed SPP under different sets in sections, “SPP in vague environment”, “SPP in fuzzy environment”, “SPP in intuitionistic fuzzy environment” and “SPP in neutrosophic environment”, respectively. Lastly, conclusion has been presented for the objective of the paper.
Preliminaries
Here, we principally recollected some of the concepts connected to neutrosophic sets (NSs), single-valued neutrosophic sets (SVNSs) related to the present work. See especially [10, 12] for further details and background.
Definition 2.1.
Let \( X \) be a nonempty set. A fuzzy set \( A \) drawn from \( X \) is defined as,
where \( \mu_{A} :X \to [0,1], \) is called the membership function of \( A \) and defined over a universe of discourse \( X. \)
Definition 2.2.
A type-2 fuzzy set, denoted by \( \overline{A} \) is characterized by a type-2 membership function \( \mu_{{\overline{A} }} \left( {x,u} \right), \) where \( x \in X, \)\( u \in J{}_{x} \subseteq [0,1], \) i.e.,
Definition 2.3.
An interval-valued fuzzy set is a special case of type-2 fuzzy sets by representing the membership function \( \mu_{{\overline{A} }} = \left[ {\underline{{\mu_{{\overline{A} }} }} ,\overline{{\mu_{{\overline{A} }} }} } \right], \) where \( \underline{{\mu_{{\overline{A} }} }} \) is a lower membership function and \( \overline{{\mu_{{\overline{A} }} }} \) is an upper membership function. The area between these lower and upper membership functions is called a footprint of uncertainty (FOU), which represents the level of uncertainty of the set.
Definition 2.4.
Let \( X \) be a nonempty set. An intuitionistic fuzzy set (IFS)\( A \) in \( X \) is an object having the form
where the functions \( \mu_{A} \left( x \right),\nu_{A} \left( x \right):X \to \left[ {0,1} \right] \) define the degree of membership and nonmembership, respectively, of the element \( x \in X \) to \( A, \) for the entire element \( x \in X\;0 \le \mu_{A} \left( x \right) + \nu_{A} \left( x \right) \le 1. \) Also, \( \pi_{A} \left( x \right) = 1 - \mu_{A} \left( x \right) - \nu_{A} \left( x \right) \) is called the index of IFS, and is the degree of indeterminacy of \( x \in X \) to the IFS \( A, \) which expresses the lack of knowledge of whether \( x \) belongs to IFS or not. Also \( \pi_{A} \left( x \right) \in \left[ {0,1} \right] \), i.e., \( \pi_{A} \left( x \right):X \to \left[ {0,1} \right] \) and \( 0 \le \pi_{A} \left( x \right) \le 1,\quad \forall x \in X. \)
Definition 2.5.
An interval-valued intuitionistic fuzzy set (IVIFS) \( A \) in \( X \) is defined as an object of the form
where the functions \( P_{A} \left( x \right):X \to \left[ {0,1} \right] \), \( Q_{A} \left( x \right):X \to \left[ {0,1} \right] \) denote the degree of membership and non-membership of \( A \), respectively. Also, \( P_{A} \left( x \right) = \left[ {P_{A}^{L} \left( x \right),P_{A}^{U} \left( x \right)} \right] \) and \( Q_{A} \left( x \right) = \left[ {Q_{A}^{L} \left( x \right),Q_{A}^{U} \left( x \right)} \right], \)\( 0 \le P_{A}^{U} \left( x \right) + Q_{A}^{U} \left( x \right) \le 1,\forall x \in X \)
Definition 2.6.
Let \( U \) be the universe, \( U = \left\{ {x_{1} ,x_{2} , \ldots ,x_{n} } \right\}, \) with a generic element of \( U \) denoted by \( x_{i} ,i = 1,2, \ldots ,n. \) A vague set is defined as an object of the form \( A = \left\{ {\left\langle {x_{i} ,T_{A} \left( {x_{i} } \right),F_{A} \left( {x_{i} } \right)} \right\rangle |x_{i} \in X} \right\} \) in \( U \) is characterized by a truth membership function \( T_{A} \) and a false membership function \( F_{A} , \) i.e., \( T_{A} :U \to \left[ {0,1} \right], \)\( F_{A} :U \to \left[ {0,1} \right], \) where \( T_{A} \left( {x_{i} } \right) \) is the lower bound on the grade of membership of \( x_{i} , \)\( F_{A} \left( {x_{i} } \right) \) is the lower bound on the negation of \( x_{i} , \) derived from the evidence against \( x_{i} \) and \( T_{A} \left( {x_{i} } \right) + F_{A} \left( {x_{i} } \right) \le 1. \) The grade of membership of \( x_{i} \) in the vague set \( A \) is bounded to the subinterval \( \left[ {T_{A} \left( {x_{i} } \right),1 - F_{A} \left( {x_{i} } \right)} \right] \) of the interval \( \left[ {0,1} \right]. \) The vague value \( \left[ {T_{A} \left( {x_{i} } \right),1 - F_{A} \left( {x_{i} } \right)} \right] \) indicates that the exact grade of membership \( \mu_{A} \left( {x_{i} } \right) \) of \( x_{i} \) may be unknown. But it is bounded by \( T_{A} \left( {x_{i} } \right) \le \mu_{A} \left( {x_{i} } \right) \le 1 - F_{A} \left( {x_{i} } \right). \)
Definition 2.7.
An interval-valued vague set \( A \) over a universe of discourse \( X \) is defined as an object of the form \( A = \left\{ {\left\langle {x_{i} ,\left[ {T_{A}^{L} ,T_{A}^{U} } \right],\left[ {F_{A}^{L} ,F_{A}^{U} } \right]} \right\rangle |x_{i} \in X} \right\}, \)where \( 0 \le T_{A}^{L} \le T_{A}^{U} \le 1 \) and \( 0 \le T_{A}^{U} \le T_{A}^{L} \le 1. \) For each interval-valued vague set \( A, \)\( \pi_{A} \left( {x_{i} } \right) = 1 - T_{A}^{L} \left( {x_{i} } \right) - F_{A}^{L} \left( {x_{i} } \right) \) and are called degree of hesitancy of \( x_{i} . \)
Definition 2.8
Consider the space X consists of universal elements characterized by x. The NS A is a phenomenon which has the structure \( A = \left\{ {\left( {T_{A} \left( x \right),I_{A} \left( x \right),F_{A} \left( x \right)} \right)/x \in X} \right\}, \) where the three grades of memberships are from X to ] −0, 1+ [ of the element x ∈ X to the set A, with the criterion:
The functions, and are the truth, indeterminate and falsity grades which lie in real standard/non-standard subsets of ]−0, 1+[. Since there is a complication of applying NSs to realistic issues, Samarandache and Wang wt al. [11, 12] proposed the notion of SVNS, which is a specimen of NS and it is useful for realistic applications of all the fields.
Definition 2.9.
Let X be the space of objects which contains global elements. A SVNS is represented by degrees of membership grades mentioned in Definition 2.1. For all x in X, \( T_{A} (x), \)\( I_{A} (x)\;F_{A} (x) \) ∈ [0, 1]. A SVNS can be written as
Definition 3.
Let \( X \) be a space of objects with generic elements in \( X \) denoted by \( x. \) An interval-valued neutrosophic set (IVNS) \( A \) in \( X \) is characterized by truth membership function, \( T_{A} (x), \) indeterminacy membership function \( I_{A} (x) \) and falsity membership function \( F_{A} (x). \) For each point \( x \) in \( X, \)\( T_{A} (x), \)\( I_{A} (x), \)\( F_{A} (x) \in \left[ {0,1} \right], \) and an IVNS \( A \) is defined by
where \( T_{A} (x) = \left[ {T_{A}^{L} \left( x \right),T_{A}^{U} \left( x \right)} \right], \)\( I_{A} (x) = \left[ {I_{A}^{L} \left( x \right),I_{A}^{U} \left( x \right)} \right] \) and \( F_{A} (x) = \left[ {F_{A}^{L} \left( x \right),F_{A}^{U} \left( x \right)} \right]. \)
SPP in vague environment
A peculiar way for getting a shortest path (SP) of a given network was found by Dou et al. [26]. in 2008, where the sets are vague. Firstly, the authors recommended that the length of the SP was determined using vague sets from the source node (SN) to the destination node (DN) for conventional network with direction. Secondly, they calculated the degree of resemblance among the lengths of the vague paths under vague similarity measure. Finally, it was concluded that the path which has the greater degree of similarity is a SP. A novel algorithm was constructed to identify the SP in a directed graph (DG), where the distance between the arcs is considered as vague number in triangular measure rather than real number. In 2018, Rashmanlou et al. solved SPP using Euclidean distance for vague network [57].
SPP in fuzzy environment
This part describes about various methods to solve SPP using fuzzy arc length by many authors. SPP can be solved in an optimized way for a given network using fuzzy logic as the real-world problems are uncertain in nature. Dubois and Prade solved fuzzy SPP (FSPP) using Floyd’s and Ford’s algorithms firstly [5]. In the year 2000, Okada and soper introduced an algorithm to solve FSPP in terms of multiple labeling procedure [32]. Klein [27] projected a vital programming fuzzy algorithm based on recursive concept. Lin [41] constructed a technique of fuzzy linear programming to find the fuzzy SP (FSPP) length of a network. Yao [42] contemplated two different FSPP such as SPP using triangular fuzzy numbers (TFNs) and SPP using level (1–β 1–α) interval-valued fuzzy numbers (IVFNs).
In 2003, the same author solved FSSP using two different types of methods, namely TFNs and level \( \left( {1 - \beta ,1 - \alpha } \right) \) interval-valued FNs (IVFNs). Nayeem and Pal introduced an algorithm to solve SPP using notoriety index, where the lengths of the arc were taken as interval numbers or TFNs [44]. In the year 2005, Chuang recommended a novel idea to identify FSP by finding the length of the FSP encompassed by all possible paths of a given network [38]. Kung et al. established new technique to handle FSPP by representing the arc length as TFN [40]. In 2009, Yadav and Biswas conferred a new method to solve SPP by considering the edge length as FN in a directed graph instead of real number. The authors constructed an algorithm to discover an optimal path by considering that both input and output are FNs [22]. Also in the same period, Lin solved SPP using interval-valued FNs and endorsed distance method of defuzzification [62]. In 2010, Pandian and Rajendran introduced path classification algorithm to find the minimal path by considering crisp or uncertain weights (TFNs) from one node to another. In this method, indeterminate nodes in the minimum path can be found without going backward and this is the major advantage. This would be very helpful for the decision-makers to omit indeterminate nodes [28]. Seda presented all-pairs SPP by applying fuzzy ranking method [25]. In 2012, Meenakshi and Kaliraja determined SP for IVFN (Interval Valued Fuzzy Network) [61].
In 2013, Shukla projected Floyd’s algorithm to solve SPP using a concept of fuzzy sets which is based on graded mean unification of FNs [21]. In 2014, Elizabeth and Sujatha introduced a novel approach to solve FSPP by finding minimum arithmetic mean among IVFN matrices [31]. The same authors Huyen et al. gave a direction on establishing a design for SPP with TFNs as the edge weights. In this work, mathematical concept of the algorithm is developed on Defined Strict Comparative Relation Function for the set of TFNs [56]. Nayeem proposed a novel expected value algorithm for the FSSP [60].
In 2015, Mukerje [34] explored the fuzzy approach programming to solve FSPP. Here, the authors converted a single-objective fuzzy linear programming (SOFLP) by considering TFNs and TpFNs as the edge weight into crisp multi-objective Linear Programming (CMOLP). Anusuya and Sathya proposed a design for SPP where the arc lengths are type-2 fuzzy numbers (T2FNs) from SN to DN in a network [54]. Also, the authors established an algorithm for SPP using type reduction on the edges using centroid and center of gravity of FSwhich gives the FSP where the arc lengths are represented by discrete T2FN [55]. Mahdavi et al. [16] applied dynamic programming method for finding the shortest chain in a fuzzy network. In [33] Okada solved FSPPs by incorporating interactivity among path. Deng et al. [53] established fuzzy Dijikstra algorithm for solving SPP under uncertain environment. Dey et al. have contributed the following ideas: solved FSPP using IT2FSs (interval type-2 fuzzy set) as the edge weights, they have altered conventional Dijikstra’s design by including impreciseness using IT2FSs to solve SPP from SN to DN, afford a new way for SPP in imprecise setting using IT2FSs for the edge weights and examined the path algebra and its generalized algorithm for FSPP [6]. Meenakshi and Kaliraja described the SP for a network under the notion of interval valued fuzzy (IVF) where the SP in lower limit fuzzy networks coexists with the case for upper limit [7]. In 2016, Dey et al. introduced a model to solve FSPP for using Interval Type-2 Fuzzy (IT2F) [59].In 2017, Biswas proposed IVFSP in a multi-graph [63]. In 2018, Eshaghnezhad et al. presented a first scientific paper for resolving of FSP by artificial network model which has the property of the global exponential stability [82].
SPP in intuitionistic fuzzy environment
In this part, various methods have been disclosed in literature to handle the SPP by taking intuitionistic fuzzy (IF) as the arc lengths by different authors.
In 2007, Karunambigai et al. refined an approach found on dynamic programming to solve SPP using intuitionistic fuzzy graphs (IFGs) [24]. In 2010, Gani also established a technique to identify intuitionistic fuzzy shortest path (IFSP) for a given network [3]. Mukherje pre-owned an interesting methodology to solve IFSPP using the idea of Dijikstra’s algorithm and intuitionistic fuzzy hybrid Geometric (IFHG) operator [45]. Majudmder and Pal [30] solved SPP for intuitionistic fuzzy network. In 2013, Biswas modified an IF method for SPP in a realistic multigraph [35]. Rangasamy et al. proposed score-based methodology to find the shortest hyper paths for a given network where hyper edges are characterized by IF weights without describing similarity measure and Euclidean distance [43]. Babacioru conferred an algorithm to find the minimum arc length of an IF hyper path using MAPLE [15]. In [29], Jayagowri and GeethaRamani solved SPP on a network with the use of Trapezoidal Intuitionistic Fuzzy Numbers (TpFNs).In 2014, Porchelvi and Sudha recommended a minimum path labeling algorithm to solve SPP using triangular IF number (TIFN) [36]. Also, they proposed a new and different methodology to solve SPP with TIFNs, where the authors found the minimal edge using IF distance by applying graded mean integration and examined SPP from a particular vertex to all other ones in a network [37]. In 2015, Kumar et al. suggested a design to identify the SP and shortest distance in an IVIF graph where the nodes are taken as crisp numbers and edge weights are assigned by IVITpFNs (Interval Valued Intuitionistic Trapezoidal Fuzzy Numbers) [1]. Kumar et al. proposed an algorithm for SPP using IVITpFN as the weights in a network [58].
SPP in neutrosophic environment
The authors modeled a design to find the ideal path where the inputs and outputs are neutrosophic numbers (NNs) [4]. In 2016, Broumi et al.solved SPP, by considering the edge weights as, SVTpNNs as the edge weights [68], Triangular fuzzy neutrosophic numbers (TFNNs) [69], bipolar neutrosophic set [70] and applied Dijikstra’s method to solve NSPP and IVNSPP [67, 72]. In 2017, Broumi et al. solved SPP using SVNGs [64], by adopting SVTNNs and SVTpNNs [65, 66]; found an optimal solution for the NSPP using trapezoidal data under neutrosophic environment [68], by SVNN; solved the MST problem [73], by Trapezoidal fuzzy neutrosophic [74]; introduced a new notion of matrix design for MST in IVNG [79]; and introduced computational method to MST in IV bipolar neutrosophic setting [80]. Also in [75], Broumi et al. proposed another algorithm to solve MST problem on a network with the use of SVTpNNs. Broumi et al. [76] solved MST problem in a bipolar neutrosophic environment. Mullai et al. solved SPP by minimal spanning tree (MST) using BNS [77]. In 2018, Broumi et al. applied IVNNs and BNS SPP for a given network [70, 71]. Dey et al. proposed a novel design for MST for NGs which are undirected [78]. Jeyanthi and Radhika [81] solved NSPP using Floyd’s algorithm firstly. Basset et al. proposed a hybrid approach of neutrosophic sets and DEMATEL method for developing the criteria for supplier selection [83]. Basset et al. introduced a novel method, to solve the fully neutrosophic linear programming problems [84]. Basset et al. proposed three-way decisions based on neutrosophic sets and AHP-QFD framework for the problem supplier selection [85]. Basset et al. proposed a novel framework to evaluate cloud computing services [86]. Basset et al. introduced an extension of neutrosophic AHP-SWOT analysis for strategic planning and decision-making [87]. Basset et al. proposed an approach of hybrid neutrosophic multiple criteria group decision-making for project selection. [88]. Basset et al. proposed a framework for a group decision-making problem, based on neutrosophic VIKOR approach for e-government website evaluation [89]. Basset et al. proposed an economic tool for quantifying risks in supply chain as a framework for risk assessment, management and evaluation [90].
The following table confers four types of SPP containing FSPP, IFSPP and neutrosophic SPP (NSPP) and for the case of interval numbers to all the types of parameters.
Shortest path problem on network with | Edges/ vertices | Indeterminacy | Ambiguity | Uncertainty |
---|---|---|---|---|
Crisp parameters | Crisp Number (CN) | Inadequate to handle | Inadequate to handle | Inadequate to handle |
Crisp Interval Parameters | Crisp Interval Number (IN) | Inadequate to handle | Inadequate to handle | Inadequate to handle |
Fuzzy parameters (FPs) | Fuzzy Number (FN) | Unable to deal | Unable to deal | Able to deal with uncertainty |
Interval FPs | Interval Fuzzy Number (IFN) | Unable to deal | Unable to deal | Able to deal with more uncertainty, as it has lower and upper membership values |
Intuitionistic fuzzy parameters (IFPs) | Intuitionistic Fuzzy Number (IFN) | Inadequate to deal | Adequate to deal | Adequate to deal |
Interval IFPs | Interval Intuitionistic Fuzzy Number (IFN) | Inadequate to deal | Adequate to deal clearly as it has loer and upper membership values | Adequate to deal more uncertainty as it has lower and upper membership functions |
Neutrosophic parameters (NPs) | Neutrosophic Number (NN) | Able to handle | Able to handle | Able to handle |
Interval NPs | Interval Neutrosophic Number (INN) | Able to handle more indeterminacy | Able to handle more ambiguity | Able to handle more uncertainty as it has lower and upper membership functions. |
From the overhead table, it is seen that the available methods could not employed to solve NSPP from SN to DN for a given network with IVNN as the edge weights.
But neutrosophic environment can able to solve SPP effectively as it handles indeterminacy together with impreciseness and ambiguity to take the best decision in identifying the SP with the use of IVNN rather than single-valued NN. Effortlessly, the proposed algorithm can be adapted to any kind of NNs.
As the neutrosophic logic deals indeterminacy with the collected/given information, the algorithms proposed to find SPP may be the best one than other algorithms under fuzzy and intuitionistic fuzzy environments.
Advantages and limitations of different types of sets
The below table expresses the capacity of various types of sets as an advantage and their incapability to handle some conditions or important situations towards to realistic problems.
Various types of sets | Advantages | Limitations |
---|---|---|
Crisp sets | Can accurately determine with no hesitation | Cannot describe the uncertain Information |
Fuzzy sets | Can describe the uncertain Information | Cannot describe the uncertain Information with non-membership degree |
Interval valued fuzzy sets | Can able to deal interval data instead of exact data | Cannot handle the uncertain Information with non-membership degree |
Intuitionistic fuzzy sets | Can describe the uncertain Information with membership (MS) and non-membership (NMS) degrees simultaneously | Cannot describe the sum of MS and NMS degrees bigger than 1 |
Interval valued Intuitionistic fuzzy sets | Able to handle interval data | Cannot portray the addition of MS and NMS degrees bigger than 1 |
Vague sets | Can describe uncertain Information with grades of MS and NMS at the same time. | Cannot describe the sum of MS and NMS degrees greater than 1. |
Pythagorean fuzzy sets | It has full space to describe the sum of MS and NMS degrees greater than 1 | Cannot describe the square sum of MS and NMS degrees greater than 1 |
Interval valued Pythagorean fuzzy sets | Capable of dealing interval data | Unable to define the square sum of MS and NMS degrees greater than 1 |
Neutrosophic Sets | Able to deal indeterminacy of the data and the optimized solution can be obtained completely. | Unable to handle interval data |
Interval valued Neutrosophic sets | Able to deal indeterminacy of the interval data and the optimized solution can be obtained . | Unable to handle incomplete weight information |
Conclusion
Crisp SPP (CSPP) can be adopted only if there exists certainty on the parameters of nodes and edges. If uncertainty exists in the arc, then the authors have been recommended to use FSPP. Later, FSPPs cannot be enforced for the certain message which is not endured and indecisive, and so the investigation invented the concept of IFSPP. Further when the information about the path is indetermined, uncertain and unreliable, neutrosophic concept has been implemented and obtained the solution for neutrosophic shortest path problem in the literature. All the existing algorithms developed by the reserachers. The algorithms have been used for various real world problems but occasionally not suitable for persuade situations. Hence, the recognized algorithms in various sets such as vague set (VS), FS, IFS and NS are forced. In real world, the researcher who has clear knowledge about the data can accept and implement the algorithms for solving SPP. This paper will be very helpful to the new researchers to propose novel concepts to solve the shortest path problem. In the future, based on this present study, new algorithms and frameworks will be designed to find the shortest path for a given network under various types of sets environments.
References
Kumar A, Kaur M (2011) A new algorithm for solving shortest path problem on a network with imprecise edge weight. Appl Appl Math 6(2):602–619
Kumar A, Kaur M (2011) Solution of fuzzy maximal flow problems using fuzzy linear programming. World Acad Sci Technol 87:28–31
Gani AN (2010) On searching intuitionistic fuzzy shortest path in a network. Appl Math Sci 69(4):3447–3454
Thamaraiselvi A, Santhi R (2016) A new approach for optimization of real life transportation problems in neutrosophic environment. Math Problems Eng. https://doi.org/10.1155/2016/5950747
Dubois D, Prade H (1980) Fuzzy sets and systems: theory and application. Academic Press, New York
Dey A, Pal A, Pal T (2016) Interval type 2 fuzzy set in fuzzy shortest path problem. Mathematics 4(62):1–19
Meenakshi AR, Kaliraja M (2012) Determination of the shortest path in interval valued fuzzy networks. Int J Math Arch 3(6):2377–2384
Smarandache F (2015) Refined literal indeterminacy and the multiplication law of sub-indeterminacies. Neutrosophic Sets Syst 9:58–63
Smarandache F (2015) Types of Neutrosophic Graphs and neutrosophicAlgebraicStructures together with their Applications in Technology, seminar. UniversitateaTransilvania din Brasov, Facultatea de Design de ProdussiMediu, Brasov, Romania 06 June 2015
Smarandache F (2006) Neutrosophic set—a generalization of the intuitionistic fuzzy set, Granular Computing. IEEE Int Conf 2006:38–42
Smarandache F (2011) A geometric interpretation of the neutrosophic set—a generalization of the intuitionistic fuzzy set, Granular Computing (GrC). IEEE Int Conf 2011:602–606
Wang H, Smarandache F, Zhang Y, Sunderraman R (2010) Single valued neutrosophic sets. Multispace Multistruct 4:410–413
Wang H, Smarandache F, Zhang YQ, Sunderraman R (2005) Interval neutrosophic sets and logic: theory and applications in computing. Hexis, Phoenix
Turksen I (1986) Interval valued fuzzy sets based on normal forms. Fuzzy Sets Syst 20:191–210
Barbacioru IC (2016) Using maple for determination minimum arc length of an intuitionistic fuzzy hyperpath. Ann CanstantinBrzncusi Univ TarguJiu Eng Ser 4:81–85
Mahdavi I, Nourifar R, Heidarzade A, Amiri NM (2009) A dynamic programming approach for finding shortest chains in a fuzzy network. Appl Soft Comput 9:503–511
Ye J (2014) Single-valued neutrosophic minimum spanning tree and its clustering method. J Intell Syst 23(3):311–324
Atanassov K (1986) Intuitionistic fuzzy sets. Fuzzy Sets Syst 20:87–96
Atanassov K (1999) Intuitionistic fuzzy sets: theory and applications. Physica, New York
Atanassov K, Gargov G (1989) Interval valued intuitionistic fuzzy sets. Fuzzy Sets Syst 31:343–349
Shukla KT (2013) Fuzzy Floyd’s algorithm to find shortest route between nodes under uncertain environment. Int J Math Comput Appl Res 3(5):34–54
Yadav K, Biswas R (2009) On searching fuzzy shortest path in a network. Int J Recent Trends Eng 2(3):16–18
Zadeh L (1965) Fuzzy sets. Inform Control 8:338–353
Karunambigai MG, Rangasamy P, Atanassov K, Palaniappan N (2007) An intuitionistic fuzzy graph method for finding the shortest path in networks. Adv Soft Comput 42:3–10
Seda (2006), Fuzzy all-pair shortest path problem. In: Proceedings of the computational intelligence, theory and applications international conference 9th fuzzy days in Dortmund, September 18–20, Germany, pp 395–404
Dou Y, Guo H, Zho J (2008) On the shortest path to solve the problem base on vague sets. In: Fifth international conference on fuzzy systems and knowledge discovery IEEE, 2008, pp.85-89
Klein CM (1991) Fuzzy shortest paths. Fuzzy Sets Syst 39:27–41
Pandian P, Rajendran P (2010) A new algorithm for Minimum path in a network. Appl Math Sci 4(54):2697–2710
Jayagowri P, GeethaRamani G (2014) Using trapezoidal intuitionistic fuzzy number to find optimized path in a network. Adv Fuzzy Syst. https://doi.org/10.1155/2014/183607
Majumder S, Pal A (2013) Shortest path problem on intuitionistic fuzzy network. Ann Pure Appl Math 5(1):26–36
Elizabeth S, Sujatha L (2014) Fuzzy shortest path problem based on interval valued fuzzy numbers matrices. IJMSEA 8(1):325–335
Okada S, Soper T (2000) A shortest path problem on network with fuzzy arc length. Fuzzy Sets Syst 109:129–140
Okada S (2004) Fuzzy shortest path problems incorporating interactivity among path. Fuzzy Sets Syst 142:335–357
Mukherjee S (2015) Fuzzy programming technique for solving the shortest path problem on networks under triangular and trapezoidal fuzzy environment. Int J Math Oper Res 7:549–576
Biswas SS, Alam B, Doja MN (2013) Real time multigraph for communication network: an intuitionistic fuzzy mathematical Model. J Comput Sci 9(7):847–855
Porchelvi S, Sudha G (2014) A new approach for finding Minimum path in a network using triangular intuitionistic fuzzy number. Int J Curr Res 6(8):8103–8109
Porchelvi RS, Sudha G (2014) Modified Approach on shortest path in intuitionistic fuzzy environment. Indian J Appl Res 4(9):341–342
Chuang TN, Kung JY (2005) The fuzzy shortest path length and the corresponding shortest path in a network. Comput Oper Res 32:1409–1428
Chuang TN, Kung JY (2006) A new algorithm for the discrete shortest path problem in a network. Appl Math Comput 174:1660–1668
Kung JY, Hiang TN, Lin CT (2006) Decision making on anetwork problem with fuzzy arc length, IMACS multiconference on computational engineering in System Application (CESA), October 4-6. Bejing, China
Lin K, Chen M (1994) The fuzzy shortest path problem and its most vital arcs. Fuzzy Sets Syst 58:343–353
Yao JS, Lin FT (2003) Fuzzy shortest path network problems with uncertain edge weights. J Inf Sci Eng 19:329–351
Rangasamy P, Akram M, Thilagavathi S (2013) Intuitionistic fuzzy shortest hyperpath in a network. Inf Process Lett 113:599–603
Nayeem SM, Pal M (2005) Shortest path problem on a network with imprecise edge weight. Fuzzy Optim Decis Mak 4:293–312
Mukherjee S (2012) Dijikstra’s algorithm for solving the shortest path problem on networks under intuitionistic fuzzy environment. J Math Model Algorithm 11:345–359
Broumi S, Talea M, Bakali A, Smarandache F (2016) Single valued neutrosophic graphs. J New Theory N 10:86–101
Broumi S, Talea M, Bakali A, Smarandache F (2016) On bipolar single valued neutrosophic graphs. J New Theory N11:84–102
Broumi S, Talea M, Bakali A, Smarandache F (2016) Interval valued neutrosophic graphs. In: SISOM & ACOUSTICS 2016, Bucharest 12–13 May, pp 79–91
Broumi S, Bakali A, Talea M, Smarandache F (2016) Isolated single valued neutrosophic graphs. Neutrosophic Sets Syst 11:74–78
Broumi S, Smarandache F, Talea M, Bakali A (2016) An introduction to bipolar single valued neutrosophic graph theory. Appl Mech Mater 841:184–191
Broumi S, Talea M, Smarandache F, Bakali A (2016) Single valued neutrosophic graphs: degree, order and size. In: IEEE international conference on fuzzy systems (FUZZ), pp 2444–2451
Broumi S, Smarandache F (2014) New distance and similarity measures of interval neutrosophic sets. In: Information fusion (FUSION), 2014 IEEE 17th international conference, pp 1–7
Deng Y, Zhang Y, Mahadevan S (2012) Fuzzy Dijikstra algorithm for shortest path problem under uncertain environment. Appl Soft Comput 12:1231–1237
Anusuya V, Sathya R (2013) Type-2 fuzzy shortest path. Int J Fuzzy Math Arch 2:36–42
Anusuya V, Sathya R (2014) Type reduction on fuzzy shortest path problem. IJMCAR 4(6):53–60
Huyen VTT, Luan NT, Tuan LM (2014) Fuzzy shortest path algorithm based on comparative relation. Int J Comput Sci Netw Security 14(5):20–25
Rashmanlou O, Sahoo S, Borzoei RA, Pal M, Lakdashti A (2018) Computation of shortest path in a vague network by euclidean distance. J Multi Valued Logic Soft Comput 30:115–123
Kumar G, Balaji RK, Gandotra N (2015) Algorithm for shortest path problem in a network with interval-valued intuitionistic trapezoidal fuzzy number. Proc Comput Sci 70:123–129
Dey A, Pal A, Pal T (2016) Interval type-2 fuzzy set in fuzzy shortest path problem. Math Project Fuzzy Shortest Path Problem 4(62):1–19
Nayeem SKA (2014) A new expected value model for the FSSP. Adv Intell Syst Comput 236:209–215
Meenakshi AR, Kaliraja M (2012) Determination of shortest path in interval valued fuzzy networks. Int J Math Arch 3(6):2377–2384
Lin FT (2009) Shortest path problem based on interval-valued fuzzy numbers and signed distance defuzzification method. In: 2009 Fourth international conference on innovative computing, information and control, pp 605–608
Biswas SS (2017) Interval valued fuzzy shortest path in a multigraph, oriental. J Comput Sci Technol 10(2):364–370
Broumi S, Bakali A, Talea M, Smarandache F (2017) Shortest path problem on single valued neutrosophic graphs. In: 2017 International symposium on networks, computers and communications, pp 1–8
Broumi S, Bakali A, Talea M, Smarandache F, Vladareanu L (2016) Computation of shortest path problem in a network, with SV-trapezoidal neutrosophic numbers. In: Proceedings of the 2016 international conference on advanced mechatronic systems, Melbourne, Australia, pp 417–422
Broumi S, Bakali A, Talea M, Smarandache F (2017) Shortest path problem in a network with SV-triangular neutrosophic numbers. In: 2017 IEEE international conference on innovations in intelligent systems and applications, Gdynia, Poland, 2017, pp 426–431
Broumi S, Bakali A, Talea M, Smarandache F (2016) Applying Dijkstra algorithm for solving neutrosophic shortest path problem. In: Proceedings of the 2016, international conference on advanced mechatronics systems, melbourne, Australia, 2016, pp 412–416
Broumi S, Bakali A, Talea M, Smarandache F (2017) Shortest path problem under trapezoidal neutrosophic information. In: Computing conference, 2017, pp 142–148
Broumi S, Bakali A, Talea M, Smarandache F, Vladareanu L (2016) Shortest path problem under triangular fuzzy neutrosophic information. In: 10th International conference on software, knowledge, information management and applications, pp 169–174
Broumi S, Bakali A, Talea M, Smarandache F, Ali M (2016) Shortest path problem under bipolar neutrosophic setting. Appl Mech Mater 859:59–66
Broumi S, Bakali A, Talea M, Smarandache F, Krishnan Kishore KP, Sahin R (2018) Shortest path problem under interval valued neutrosophic setting. J Fundam Appl Sci 10(4S):168–174
Broumi S, Talea M, Bakali A, Smarandache F (2016) Application of Dijkstra algorithm for solving interval valued neutrosophic shortest path problem. In: IEEE symposium series on computational intelligence, pp 1–6
Broumi S, Bakali A, Talea M, Smarandache F, Dey A, Son L (2018) Spanning tree problem with neutrosophic edge weights. Proc Comput Sci 127:190–199
Broumi S, Bakali A, Talea M, Smarandache F, Ulucay V (2017) Minimum spanning tree in trapezoidal fuzzy neutrosophic environment. In: 8th international conference on innovations in bio-inspired computing and applications, pp 25–35
Broumi S, Talea M, Bakali A, Smarandache F, Patro SK (2019) Minimum spanning tree problem with single-valued trapezoidal neutrosophic numbers. Adv Intell Syst Comput 857:93–105
Broumi S, Talea M, Bakali M, Smarandache F, Ullah K (2018) Bipolar neutrosophic minimum spanning tree. Smart Appl Data Anal Smart Cities 2:201–206
Mullai M, Broumi S, Stephen A (2017) Shortest path problem by minimal spanning tree algorithm using bipolar neutrosophic numbers. Int J Math Trends Technol 46(2):80–87
Dey A, Broumi S, Son LH, Bakali A, Talea M, Smarandache F (2018) A new algorithm for finding minimum spanning trees with undirected neutrosophic graphs. Granular Comput 4(1):63–69
Broumi S, Bakali A, Talea M, Smarandache F, Kishore Kumar PK (2017) A new concept of matrix algorithm for MST in undirected interval valued neutrosophic graph. In: Neutrosophic operational research, vol II. Pons Publishing House, Brussels, Belgium
Broumi S, Bakali A, Talea M, Smarandache F, Verma R (2017) Computing minimum spanning tree in interval valued bipolar neutrosophic environment. Int J Model Optim 7(5):300–304
Jeyanthi V, Radhika VS (2018) Applying Floyd‘s algorithm for solving neutrosophic shortest path problems. Int J Math Trends Technol 61(1):58–63
Eshaghnezhad M, Rahbarnia F, Effati S, Mansoori A (2018) An artificial neural network model to solve the fuzzy shortest path problem. Neural Process Lett. https://doi.org/10.1007/s11063-018-9945-y
Abdel-Basset M, Gunasekaran M, Mohamed M, Chilamkurti N (2019) A framework for risk assessment, management and evaluation: economic tool for quantifying risks in supply chain. Future Gener Comput Syst 90:489–502
Basset MA, Mohamed M, Sangaiah AK, Jain V (2018) An integrated neutrosophic AHP and SWOT method for strategic planning methodology selection. Benchmarking Int J 25(7):2546-2564
Abdel-Basset M, Mohamed M, Smarandache F (2018) A hybrid neutrosophic group ANP-TOPSIS framework for supplier selection problems. Symmetry 10(6):226
Abdel-Basset M, Mohamed M, Smarandache F (2018) An extension of neutrosophic AHP–SWOT analysis for strategic planning and decision-making. Symmetry 10(4):116
Abdel-Basset M, Mohamed M, Smarandache F, Chang V (2018) Neutrosophic association rule mining algorithm for big data analysis. Symmetry 10(4):106
Abdel-Basset M, Mohamed M, Chang V (2018) NMCDA: a framework for evaluating cloud computing services. Future Gener Comput Syst 86:12–29
Abdel-Basset M, Zhou Y, Mohamed M, Chang V (2018) A group decision making framework based on neutrosophic VIKOR approach for e-government website evaluation. J Intell Fuzzy Syst 34(6):4213–4224
Abdel-Basset M, Mohamed M, Zhou Y, Hezam I (2017) Multi-criteria group decision making based on neutrosophic analytic hierarchy process. J Intell Fuzzy Syst 33(6):4055–4066
Abdel-Basset M, Mohamed M (2018) The role of single valued neutrosophic sets and rough sets in smart city: imperfect and incomplete information systems. Measurement 124:47–55
Abdel-Basset M, Manogaran G, Gamal A, Smarandache F (2018) A hybrid approach of neutrosophic sets and DEMATEL method for developing supplier selection criteria. Design Autom Embed Syst 22(3):257–278
Acknowledgements
The authors are very grateful to the chief editor and reviewers for their comments and suggestions, which are helpful in improving the paper.
Author information
Authors and Affiliations
Corresponding author
Additional information
Publisher's Note
Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.
Rights and permissions
Open Access This article is distributed under the terms of the Creative Commons Attribution 4.0 International License (http://creativecommons.org/licenses/by/4.0/), which permits unrestricted use, distribution, and reproduction in any medium, provided you give appropriate credit to the original author(s) and the source, provide a link to the Creative Commons license, and indicate if changes were made.
About this article
Cite this article
Broumi, S., Talea, M., Bakali, A. et al. Shortest path problem in fuzzy, intuitionistic fuzzy and neutrosophic environment: an overview. Complex Intell. Syst. 5, 371–378 (2019). https://doi.org/10.1007/s40747-019-0098-z
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s40747-019-0098-z