30.03.2019 | Original Article Open Access

# Shortest path problem in fuzzy, intuitionistic fuzzy and neutrosophic environment: an overview

- Zeitschrift:
- Complex & Intelligent Systems

Wichtige Hinweise

## Publisher's Note

Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.

## 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–52, 83–92]. Up until now plenty of new algorithms have been designed.

Anzeige

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. \)

$$ A = \left\{ {x,\mu_{A} (x)|x \in X} \right\}, $$

(1)

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.,

$$ \overline{A} = \left\{ {\left( {\left( {x,u} \right),\mu_{{\overline{A} }} \left( {x,u} \right)} \right)|x \in X,\quad \forall u \in J_{x} \subseteq \left[ {0,1} \right]} \right\}. $$

(2)

Anzeige

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 formwhere 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. \)

$$ A = \left\{ {\left\langle {x,\mu_{A} \left( x \right),\nu_{A} \left( x \right)} \right\rangle |x \in X} \right\}, $$

(3)

Definition 2.5.

An interval-valued intuitionistic fuzzy set (IVIFS) \( A \) in \( X \) is defined as an object of the formwhere 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 \)

$$ A = \left\{ {\left\langle {x,P_{A} \left( x \right),Q_{A} \left( x \right)} \right\rangle |x \in X} \right\}, $$

(4)

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 ] The functions, and are the truth, indeterminate and falsity grades which lie in real standard/non-standard subsets of ]

^{−}0, 1^{+}[ of the element x ∈ X to the set A, with the criterion:$$ ^{ - } 0 \le T_{A} (x) + I_{A} (x) + F_{A} (x) \le 3^{ + } . $$

(5)

^{−}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

$$ A = \left\{ { < x:T_{A} \left( x \right),I_{A} \left( x \right),F_{A} \left( x \right)>/x \in X} \right\} $$

(6)

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 bywhere \( 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]. \)

$$ A = \left\{ {\left\langle {\left[ {T_{A}^{L} \left( x \right),T_{A}^{U} \left( x \right)} \right],} \right.} \right.\left[ {I_{A}^{L} \left( x \right),I_{A}^{U} \left( x \right)} \right],\left. {\left. {\left[ {F_{A}^{L} \left( x \right),F_{A}^{U} \left( x \right)} \right]} \right\rangle |x \in X} \right\}, $$

(7)

## 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.

## Acknowledgements

The authors are very grateful to the chief editor and reviewers for their comments and suggestions, which are helpful in improving the paper.

Open AccessThis 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.

## Publisher's Note

Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.