Abstract
Real-life decision-making problem has been demonstrated to cover the indeterminacy through single valued neutrosophic set. It is the extension of interval valued neutrosophic set. Most of the problems of real life involve some sort of uncertainty in it among which, one of the famous problem is finding a shortest path of the network. In this paper, a new score function is proposed for interval valued neutrosophic numbers and SPP is solved using interval valued neutrosophic numbers. Additionally, novel algorithms are proposed to find the neutrosophic shortest path by considering interval valued neutrosophic number, trapezoidal and triangular interval valued neutrosophic numbers for the length of the path in a network with illustrative example. Further, comparative analysis has been done for the proposed algorithm with the existing method with the shortcoming and advantage of the proposed method and it shows the effectiveness of the proposed algorithm.
Similar content being viewed by others
Avoid common mistakes on your manuscript.
Introduction and literature of review
In this part, introduction to the objective of the paper is given by presenting basic concepts and procedure of the shortest path problem (SPP) and the literature of review have been collected to know the recent work related to the presented concept which shows the novelty of the presented work
Introduction
SPP is the ultimate and popular problem in the different areas also it is the heart of the network flows. In conventional problem, the distance between the nodes is considered to be certain and for the uncertain environment fuzzy numbers can be adopted to get an optimized result. Computing the minimum cost of the path from every vertex is called single source SPP. Especially in the process of finding shortest path, finding the path which has minimum number of bends is very important and will give the most optimized result. And the cost is the mapping of length and bends. The conventional SPP is to catch the minimum cost path from initial to end node and the cost is the addition of the costs of the curves on the path [1, 2, 4].
While applying in real time situations the vertices and the edges will be considered as follows. In transmission networks, telephone exchange, communication proficiency, satellites, work stations terminals and computers will be considered as the vertices and cables, wires and fiber optics will be treated as the arcs or paths and it is expected to meet transmission requirements at the minimum cost whereas in traffic control management the cost is due to only the paths with heavy traffic [8]. In the established network every path has a weight which will extend the flow in a recurrence fashion. The fusion of costs and weights proposes different ways of cost minimizing cycles. There may be cycles with negative cost which allow raise to perpetual instances and cost of minimum infinity and weight minimizing cycles which permits rise to a sink in such a way that it is inexpensive to consume a flow in an infinite cycle rather than transit to the station.
SPP plays an essential role in combinatorial optimization due to its elemental aspects and a broad range of applications. Investigating shortest paths is an essential thing in communication, computer networks, manufacturing systems and transportation. The weight of the path will represent the transportation timing from one end to other, i.e., the traveling time from the source to the destination. The efficiency of the transmission can be improved by speed up some of the routes to reduce the traveling time between some of the pairs of sources and terminals by minimizing the weights of the links. One needs some amount to reduce the traveling time by improving the road conditions for the faster traveling and the total cost supposed to be less to face the needs of the speedup [9].
In all the SPP, the source and terminal nodes should satisfy a set of conditions defined over a set of resources which associates to a quantity like the time, pickup of load by the vehicle or the duration of the break. The constraint of the resource will be given in the form of intervals which regulate the values that can be considered by the resources at each node on the path. SPP using complete graph can be encrypted as an assignment problem and is equivalent to an exceptional case of the assignment problem. Providing the shortest path is a necessary thing to the system of transport management, from a particular source node to the terminal node. The arc lengths are stimulated to represent time or cost of the transportation rather the geographical distances [10, 11].
The technique of using fuzzy numbers can be adopted for the environment with uncertainty. Crisp number is obtained from fuzzy number using defuzzification function and it is widely used in an optimization methods. SPP is not restricted to the geometric distance. Even though it is fixed, the traveling time within the cities may be represented by fuzzy variable. Since the weight of the arcs is uncertain in almost all the communication and transportation networks, it cannot be designed into crisp graphs. Dubois and Prade solved fuzzy shortest path problem for the first time. The most crucial combinatorial optimization problem is to find the SP to the directed graph and its primary format unable to represent the situations where the value of the detached function should be found not only by the preference of each single arc [15,16,17,18,19].
Shortest path of the network can be found using neutrosophic set (NS) by considering edge weight as neutrosophic numbers (NNs) and that may be single and interval valued, and bipolar as well [21, 22]. Samarandache described about neutrosophic for the first time in the year 1995 and proposed an important mathematical mechanism called neutrosophic set theory to handle imprecise, uncertain and indeterminate problems which cannot be dealt by fuzzy and its various type. NS is obtained by three autonomous mapping such as truth (T), indeterminacy (I) and falsity (F) and takes values from ]0−, 1+[. It is very difficult to utilize NS directly.
While getting uncertainty in the set of vertices and edge then fuzzy graph can be adopted for SPP, but if there is indeterminacy exist between the relation of nodes and vertices then neutrosophic will be the appropriate concept to deal the real life problems [23]. Since indeterminacy is also treated seriously, NSs can be able to handle uncertainty in a better way [35]. The model of the NS is an important mechanism to deal with real scientific and engineering as it is able to deal uncertain, inconsistent and also indeterminate information [36]. Route maintenance or supply with uncertainty is playing a primary role in intelligent transport systems.
Due to inadequate data, as the stochastic shortest path needs accurate probability distributions, it is unable give the optimized result. Due to accuracy, adoptability and rapport to a system, single valued neutrosophic graph (SVNG) gets more attention and produce optimized solution than other types of fuzzy sets. Application of probabilities in machine learning is done by the score function. These functions play an essential role to find the minimum cost path in SPP and minimum spanning tree (MST) to UIVNGs (undirected interval valued neutrosophic graphs). When the data are in the form of intervals then that can dealt effectively by considering interval valued neutrosophic setting [40, 41]. Many group decision making methods including hybrid methods have been proposed to solve decision making problems such as supplier selection, project selection under triangular and trapezoidal neutrosophic environment [55,56,57,58,59,60,61,62,63,64].
The rest of the paper is arranged as follows. In Sect. 1.2, literature of review has been collected. In Sect. 2, over view of interval valued neutrosophic set is given. In Sect. 3, novel algorithms are proposed to find the neutrosophic shortest path under interval valued neutrosophic environment and interval valued triangular and trapezoidal neutrosophic environments with the help of proposed score function. In Sect. 4, shortcoming of the existing methods, advantages of the proposed method and comparative analysis are presented for the proposed method with the existing method. In Sect. 5, conclusion of the presented work is given.
Literature of review
The authors of, Ahuja et al. [1] proposed a different model redistributive heap as a rapid algorithm to find SP of the network. Yang et al. [2] presented a graph-theoretic strategy of rectilinear paths on bends and lengths. Ibarra and Zheng [3] proved that the single-origin shortest path problem for permutation graphs can be determined by order of the logarithmic of n. Arsham [4] examined the robustness of the shortest path problem. Tzoreff [5] examined the disconnected SPP with group path lengths. Batagelj et al. [6] proposed generalized SPP.
Zhang and Lin [7] introduced the calculation of the reverse SPP. Vasantha and Samaranadache [8] proposed primary neutrosophic algebraic framework. Also their utilization to fuzzy and NEUTROSOPHIC models as well. Roditty and Zwick [9] acquired some results associated with effective forms of the SPP. Irnich and Desaulniers [10] proposed SPP with support force. Buckley and Jowers [11] introduced SPP using the concept of fuzzy logic. Wastlund [12] analyzed the relationship between random assignment and SPP problem on the complete graph. Turner [13] attained strongly polynomial algorithms for a collection of SPP on acyclic and normal digraphs. Deng et al. [14] proposed fuzzy Dijkstra algorithm for SPP for imprecise environment.
Biswas et al. [15] introduced an algorithm for deriving shortest path in intuitionistic fuzzy environment. Arnautovic et al. [16] obtained the complement of the ant colony development for the SPP using open MP and CUDA. Gabrel and Murat [17] presented different models, methods and principle for the stability of the SPP. Grigoryan and Harutyunyan [18] proposed SPP in the Knodel graph. Rostami et al. [19] proposed quadratic SPP. Randour et al. [20] presented algorithms to incorporate the approaches with various securities on the length allocation of the paths instead of decreasing its normal value. Broumi et al. [21] solved SPP under neutrosophic setting using Dijkstra algorithm. Broumi et al. [22] introduced SPP based on triangular fuzzy neutrosophic environment.
Broumi et al. [23] proposed assertive types of SVNGs and examination of properties with validation and examples. Nancy and Harish [24] proposed an improved score function and applied in decision making process. Sahin and Liu [25] maximized method of deviation for neutrosophic decision making problem with a support of incomplete weight. Broumi et al. [26] proposed the measurements for SPP using SV-triangular neutrosophic numbers. Broumi et al. [27] calculated MST in interval valued bipolar neutrosophic (IVBN) setting. Hu and Sotirov [28] proposed amenity of semi definite programming for the quadratic SPP and performed some arithmetic operations to solve the QSPP using branch and bound algorithm. Dragan and Leitert [29] solved SPP on minimal peculiarity. Zhang et al. [30] proposed stable SPP with circulated uncertainty.
Broumi et al. [31] solved SPP using SVNG. Broumi et al. [32] solved SSP under bipolar neutrosophic environment. Peng and Dai [33] proposed interval-based algorithms based on neutrosophic environment for decision making process. Liu and You [34] proposed muirhead mean operators and employed them in decision making problem. Smarandache [35] solved SPP using trapezoidal neutrosophic knowledge. Wang et al. [36] applied SV-trapezoidal neutrosophic preference in decision making problem. Deli and Subas [37] proposed a ranking method of SVNNs and applied in decision making problem. Broumi et al. [38] proposed matrix algorithm for MST in undirected IVNG. Enayattabar et al. [39] applied Dijkstra algorithm to find the shortest path under IV Pythagorean fuzzy setting. Broumi et al. [40] proposed IVN soft graphs. Broumi et al. [41] proposed some notion with respect to neutrosophic set with triangular and trapezoidal concept and primary operations as well. Also done a contingent analysis with the existing concepts and proposed neutrosophic numbers.
Broumi et al. [42] proposed an innovative system and technique for the planning of telephone network using NG. Broumi et al. [43] proposed SPP under interval valued neutrosophic setting. Bolturk and Kahraman [44] presented a novel IVN AHP with cosine similarity measure. Wang et al. [45] proposed interval neutrosophic set and logic in detail. Biswas et al. [46] proposed distance measure using interval trapezoidal neutrosophic numbers. Deli [47] given detailed work on expansion and contraction on conventional neutrosophic soft set. Deli [48] solved a decision making problem using interval valued neutrosophic soft numbers.
Deli [49] proposed theory of npn-soft set and its application. Deli [50] proposed single valued trapezoidal neutrosophic operators and applied them in a decision making problem. Deli and Subas [51] proposed weighted geometric operators under single valued triangular neutrosophic numbers and applied in a decision making problem. Deli et al. [52] solved a decision making problem using neutrosophic soft sets. Basset et al. [53] proposed framework of hybrid neutrosophic group AND-TOPSIS for supplier selection. Chang et al. [54] experimented in detail about framework for the pattern of reuse necessary decision from theoretical perspective to practices.
Basset et al. [55] proposed a hybrid method of neutrosophic sets and method of DEMATEL to develop criteria for supplier selection. Basset et al. [56] proposed a structure based on VIKOR technique for e-government website evaluation. Basset et al. [57] Introduced a framework to evaluate cloud computing services. Basset et al. [58] proposed a hybrid method for project selection under neutrosophic environment. Basset et al. [59] proposed a new method for a neutrosophic linear programming problem. Basset et al. [60] proposed an economic tool for risk quantification for supply chain. Basset et al. [61] proposed a framework for AHP-QFD to solve a supplier selection. Basset et al. [62] proposed neutrosophic AHP-Delphi group decision model under trapezoidal neutrosophic numbers. Basset et al. [63] solved a group decision making problem using neutrosophic analytic hierarchy process. Basset et al. [64] proposed a group decision making problem using triangular neutrosophic numbers. Kumar et al. [65] proposed an algorithm to solve neutrosophic shortest path problem under triangular and trapezoidal neutrosophic environment.
From this literature review, to the best of our knowledge, there is no contribution of research for SPP using interval neutrosophic numbers under triangular and trapezoidal environments. Additionally, this is the first study that SPP is solved by considering interval valued triangular and trapezoidal neutrosophic numbers for the length of the arc for a given network.
Overview on interval valued neutrosophic set
Here, a brief description of some basic concepts on NSs, SVNSs, IVNSs and some existing ranking functions for IVNNs are given.
Definition 2.1 [35]
NS is constructed by \( N = \left\{ { < x;T_{N} \left( x \right),I_{N} \left( x \right),F_{N} \left( x \right) > ,x \in X} \right\}, \) where \( X \) be an universal set of elements \( x \) and \( T_{N} \left( x \right),I_{N} \left( x \right),F_{N} \left( x \right):X \to ]{}^{ - }0,1^{ + } [ \) are the truth, indeterminacy and also falsity membership functions and satisfies the criterion,
Definition 2.2 [36]
SVNS is defined by \( \mathop N\limits^{ \bullet } = \left\{ { < x;T_{{\mathop N\limits^{ \bullet } }} \left( x \right),I_{{\mathop N\limits^{ \bullet } }} \left( x \right),F_{{\mathop N\limits^{ \bullet } }} \left( x \right) > ,x \in X} \right\} \) and for every
and the sum of these three is less than or equal to 3.
Definition 2.3 [45]
An interval valued NS is defined by \( \mathop N\limits^{ \bullet } = \left\{ { < x:\left[ {T_{{\mathop N\limits^{ \bullet } }}^{L} \left( x \right),T_{{\mathop N\limits^{ \bullet } }}^{U} \left( x \right)} \right],\left[ {I_{{\mathop N\limits^{ \bullet } }}^{L} \left( x \right),I_{{\mathop N\limits^{ \bullet } }}^{U} \left( x \right)} \right],\left[ {F_{{\mathop N\limits^{ \bullet } }}^{L} \left( x \right),F_{{\mathop N\limits^{ \bullet } }}^{U} \left( x \right)} \right] > ,x \in X} \right\} \), where \( T_{{\mathop N\limits^{ \bullet } }} \left( x \right) = \left[ {T_{{\mathop N\limits^{ \bullet } }}^{L} \left( x \right),T_{{\mathop N\limits^{ \bullet } }}^{U} \left( x \right)} \right] \subseteq [0,1] \),
Now we assume some mathematical operations on IVNNs (interval valued neutrosophic numbers).
Definition 2.4 [45]
Let \( \mathop {N_{1} }\limits^{ \bullet } = \left\{ { < x:\left[ {T_{{\mathop {N_{1} }\limits^{ \bullet } }}^{L} ,T_{{\mathop {N_{1} }\limits^{ \bullet } }}^{U} } \right],\left[ {I_{{\mathop {N_{1} }\limits^{ \bullet } }}^{L} ,I_{{\mathop {N_{1} }\limits^{ \bullet } }}^{U} } \right],\left[ {F_{{\mathop {N_{1} }\limits^{ \bullet } }}^{L} ,F_{{\mathop {N_{1} }\limits^{ \bullet } }}^{U} } \right] > ,x \in X} \right\} \) and \( \mathop {N_{2} }\limits^{ \bullet } = \left\{ { < x:\left[ {T_{{\mathop {N_{2} }\limits^{ \bullet } }}^{L} ,T_{{\mathop {N_{2} }\limits^{ \bullet } }}^{U} } \right],\left[ {I_{{\mathop {N_{2} }\limits^{ \bullet } }}^{L} ,I_{{\mathop {N_{2} }\limits^{ \bullet } }}^{U} } \right],\left[ {F_{{\mathop {N_{2} }\limits^{ \bullet } }}^{L} ,F_{{\mathop {N_{2} }\limits^{ \bullet } }}^{U} } \right] > ,x \in X} \right\} \) be two IVNNs and \( \delta > 0 \) then we have the following operational laws.
Deneutrosophication formulas for IVNNs: To compare two IVNNs \( \mathop {N_{1} }\limits^{ \bullet } \) and \( \mathop {N_{2} }\limits^{ \bullet } \). We use the score function (SF) which represents a map from [N (R)] into the real line. In the literature there are some deneutrosophication formulas, here paper, we focus on some of types [24, 25, 33, 34, 44] defined as follows:
The ranking of \( \mathop {N_{1} }\limits^{ \bullet } \) and \( \mathop {N_{2} }\limits^{ \bullet } \) by SF is defined as follows:
-
(i)
\( \mathop {N_{1} }\limits^{ \bullet } \prec \mathop {N_{2} }\limits^{ \bullet } \) if \( {\mathbb{S}}\left( {\mathop {N_{1} }\limits^{ \bullet } } \right) \prec {\mathbb{S}}\left( {\mathop {N_{2} }\limits^{ \bullet } } \right) \)
-
(ii)
\( \mathop {N_{1} }\limits^{ \bullet } \succ \mathop {N_{2} }\limits^{ \bullet } \) if \( {\mathbb{S}}\left( {\mathop {N_{1} }\limits^{ \bullet } } \right) \succ {\mathbb{S}}\left( {\mathop {N_{2} }\limits^{ \bullet } } \right) \)
-
(iii)
\( \mathop {N_{1} }\limits^{ \bullet } = \mathop {N_{2} }\limits^{ \bullet } \) if \( {\mathbb{S}}\left( {\mathop {N_{1} }\limits^{ \bullet } } \right) = {\mathbb{S}}\left( {\mathop {N_{2} }\limits^{ \bullet } } \right) \)
Definition 2.5 [36]
Let \( R_{N} = \left\langle {\left[ {R_{T} ,R_{I} ,R_{M} ,R_{E} } \right],\left( {T_{R} ,I_{R} ,F_{R} } \right)} \right\rangle \) and \( S_{N} = \left\langle {\left[ {S_{T} ,S_{I} ,S_{M} ,S_{E} } \right],\left( {T_{S} ,I_{S} ,F_{S} } \right)} \right\rangle \) be two trapezoidal neutrosophic numbers (TpNNs) and \( \theta \ge 0 \), then
Definition 2.6 [36]
Let \( R = \left[ {R_{T} ,R_{I} ,R_{M} ,R_{E} } \right] \) and \( R_{T} \le R_{I} \le R_{M} \le R_{E} \) then the centre of gravity (COG) in \( R \) is
Definition 2.7 [36]
Let \( S_{N} = \left\langle {\left[ {S_{T} ,S_{I} ,S_{M} ,S_{E} } \right],\left( {T_{S} ,I_{S} ,F_{S} } \right)} \right\rangle \) be a TpNN then the score, accuracy and certainty functions are as follows
Definition 2.8 [36]
Let \( R_{N} = \left\langle {\left[ {R_{T} ,R_{I} ,R_{P} } \right],\left( {T_{R} ,I_{R} ,F_{R} } \right)} \right\rangle \) be a triangular neutrosophic number then the score and accuracy function are,
Definition 2.9 [46]
Let N be a trapezoidal neutrosophic number in the set of real numbers with the truth, indeterminacy and falsity membership functions are defined by
where \( t_{N} = [t^{L} ,t^{U} ] \subset [0,1],i_{N} = [i^{L} ,i^{U} ] \subset [0,1] \) and \( f_{N} = [f^{L} ,f^{U} ] \subset [0,1] \) are interval numbers. Then the number \( N \) can be denoted by \( \left( {\left[ {a,b,c,d} \right];[t^{L} ,t^{U} ],[i^{L} ,i^{U} ],[f^{L} ,f^{U} ]} \right) \) and is called interval valued trapezoidal neutrosophic number.
-
If \( b = c \) in interval valued trapezoidal neutrosophic number then it becomes interval valued triangular neutrosophic number.
Proposed improved algorithm and score function
To find the length of the arc, the following algorithm and score function are proposed as follows.
Improved algorithm to solve SPP under interval valued neutrosophic number
- Step 1::
-
Determine the source node (SN) arc length \( l_{1} = \left\langle {\left[ {1,1} \right],\left[ {0,0} \right],\left[ {0,0} \right]} \right\rangle \) and classify SN, node 1 by
$$ \left[ {l_{1} = \left\langle {\left[ {1,1} \right],\left[ {0,0} \right],\left[ {0,0} \right]} \right\rangle , - } \right] $$ - Step 2::
-
Find the minimum of the length of \( n_{1} \) with its acquaintance node using \( l_{i} = \hbox{min} \left\{ {l_{i} \oplus l_{ij} } \right\},\quad j = 2,3, \ldots ,r . \)
- Step 3::
-
If there is a minimum in the node and equating to the singular measure of \( i \) (i.e., \( i = k \)), then classify that node j as \( [l_{j} ,k] \).
- Step 4::
-
If the minimum value exists in the node matching to more values from \( i \) then it can be concluded that there are more IVN paths between SN (\( i \)) and DN (\( \,j \)) and select any value of \( i \).
- Step 5::
-
Classify the destination node (DN) (node \( r \)) by \( [l_{r} ,1] \). Then the interval valued neutrosophic distance (IVND) among SN \( l_{r} \).
- Step 6::
-
Find the IVNSP between initial and terminal node according to \( [l_{r} ,1] \) and check the label of \( n_{1} \) and is denoted by \( [l_{a} ,d] \). Classify node \( a \) and so on. Rerun the process until get \( n_{1} \).
- Step 7::
-
By connecting all the nodes acquired by repeating the process in step 4, IVNSP can be found.
Note: If \( {\mathbb{S}}\left( {N_{i} } \right) < {\mathbb{S}}\left( {N_{p} } \right) \) then the interval valued neutrosophic number (IVNN) is the minimum of \( N_{p} \), where \( N_{i} ,i = 1,2, \ldots ,r \) is the set of IVNN and \( {\mathbb{S}} \) is the score function.
Proposed score function
The novel SF for finding the minimum cost path under interval valued neutrosophic shortest path (IVNSP) problem is provided as follows
Numerical example:
For the edge 1–2: \( S_{\text{Nagarajan}} (\dddot A_{1} ) = \frac{1}{2}\left[ {\left( {0.1 + 0.2} \right) - \left( {0.2} \right)\left( {0.3} \right) + \left( {0.3 - 1} \right)^{2} + \left( {0.5} \right)} \right] = 0.125 \)
For the edge 1–3: \( S_{\text{Nagarajan}} (\dddot A_{1} ) = \frac{1}{2}\left[ {\left( {0.2 + 0.4} \right) - \left( {0.3} \right)\left( {0.5} \right) + \left( {0.5 - 1} \right)^{2} + \left( {0.2} \right)} \right] = 0.2. \)
Similarly for other edges.
Note: Formulas used in the proposed algorithms.
Score function used in the proposed algorithm under IVN environment and COG for TFN are
Computation of shortest path using IVNNs
Illustrate to the basic process of the improved algorithm, one simple example is shown.
Illustrative example
This section is based on a numerical problem adapted from Broumi et al. [40] to show the potential application of the proposed algorithm and score function.
Consider a network Fig. 1 with six nodes and eight edges with SN, node 1 and DN, node 6. The interval valued neutrosophic distance is given in Table 1.
In this situation, we need to evaluate the shortest distance from SN, i.e., node 1 to DN, i.e., node 6.
Calculating the shortest path using proposed algorithm of interval valued neutrosophic path problem is given as follows.
Here \( r = 6 \), since there are totally 6 nodes.
Let, \( l_{1} = \left\langle {\left[ {1,1} \right],\left[ {0,0} \right],\left[ {0,0} \right]} \right\rangle \) and classify the SN \( n_{1} = \left[ {\left\langle {\left[ {1,1} \right],\left[ {0,0} \right],\left[ {0,0} \right]} \right\rangle , - } \right] \).
To find the value of \( l_{j} ,\quad j = 2,3,4,5,6 \).
Iteration no. 1:
Since \( n_{2} \) has only \( n_{1} \) as the predecessor, let \( i = 1,\quad j = 2 \) in step 2.
To find \( l_{2} \):
Since, minimum occurs for \( i = 1 \), classify the node \( n_{2} = \left[ {\left\langle {\left[ {0.1,0.2} \right],\left[ {0.2,0.3} \right],\left[ {0.4,0.5} \right]} \right\rangle ,1} \right] \).
Iteration no. 2:
Since \( n_{3} \) has two predecessors \( n_{1} \) and \( n_{2} \), let \(i = 1,2\,\& \,j = 3\) in step 2.
To find \( l_{3} \):
Since the score function values are,
and the minimum occurs for \( i = 2 \), then classify the node \( n_{3} = \left[ {\left\langle {\left[ {0.37,0.52} \right],\left[ {0.02,0.06} \right],\left[ {0.12,0.25} \right]} \right\rangle ,2} \right] \).
Iteration no. 3:
Since \( n_{4} \) has one predecessors \( n_{3} \), let \(i = 3\, \& \,j = 4 \) in step 2.
To find the value of \( l_{4} \):
Since, minimum occurs for \( i = 3 \), hence classify the node \( n_{4} = \left[ {\left\langle {\left[ {0.6,0.67} \right],\left[ {0.004,0.018} \right],\left[ {0.048,0.125} \right]} \right\rangle ,3} \right] \).
Iteration no. 4:
Since \( n_{5} \) has two predecessors \( n_{2} \) and \( n_{3} \), let \( i = 2,3\& j = 5 \) in step 2.
To find the value of \( l_{5} \):
Since the score function values are,
and the minimum occurs for \( i = 2 \), hence classify the node \( n_{5} = \left[ {\left\langle {\left[ {0.19,0.47} \right],\left[ {0.06,0.12} \right],\left[ {0.08,0.15} \right]} \right\rangle ,2} \right] \)
Iteration no. 5:
Since \( n_{6} \) has two predecessors \( n_{4} \) and \( n_{5} \), let \( i = 4,5\, \,\& \,\,j = 6 \) in step 2.
To find the value of \( l_{6} \):
Since the score function values are,
and the minimum occurs for \( i = 5 \) hence classify \( n_{6} = \left[ {\left\langle {\left[ {0.35,0.63} \right],\left[ {0.018,0.048} \right],\left[ {0.008,0.075} \right]} \right\rangle ,5} \right] \).
Since \( n_{6} \) is the DN of the given network, IVNSP between \( n_{1} \) and \( n_{6} \) is \( \left\langle {\left[ {0.35,0.63} \right],\left[ {0.018,0.048} \right],\left[ {0.008,0.075} \right]} \right\rangle \).
Now, IVNSP from \( n_{1} \) and \( n_{6} \) is obtained as follows.
Since, \( n_{6} = \left[ {\left\langle {\left[ {0.35,0.63} \right],\left[ {0.018,0.048} \right],\left[ {0.008,0.075} \right]} \right\rangle ,5} \right] \Rightarrow \) a person is coming from \( 5 \to 6 \)\( n_{5} = \left[ {\left\langle {\left[ {0.19,0.47} \right],\left[ {0.06,0.12} \right],\left[ {0.08,0.15} \right]} \right\rangle ,2} \right] \Rightarrow \) a person is coming from \( 2 \to 5 \)\( n_{2} = \left[ {\left\langle {\left[ {0.1,0.2} \right],\left[ {0.2,0.3} \right],\left[ {0.4,0.5} \right]} \right\rangle ,1} \right] \Rightarrow \) a person is coming from \( 1 \to 2 \).
By joining all the acquired nodes, interval valued neutrosophic shortest path from \( n_{1} \) and \( n_{6} \) is obtained.
Hence IVNSP of the given network is \( 1 \to 2 \to 5 \to 6 . \)
The IVNS distance and IVNSP of all the nodes from SN node 1 in the below Table 2 and the classification of all the nodes are shown in Fig. 2.
The following table is formed using different deneutrosophic functions called score functions for all the possible edges and using proposed improved score function in the last column (Table 3).
According to the improved score function proposed in Sect. 3, the shortest path from node one to node six can be computed as follows (Table 4).
Therefore, the path \( P:1 \to 2 \to 5 \to 6 . \) is identified as the neutrosophic shortest path.
Algorithm: a new approach to find SPP using TpIVNN and TIVNN
Consider a directed and noncyclic graph, where the length of the arcs is represented by IVNN. The introduced algorithm determines the shortest path from the initial node to the terminal node. The algorithm is described as follows.
- Step 1::
-
Let \( n \) be the total number of paths from the initial node to terminal one. Find the score function of every arc length for the given network using Eqs. (18), (19) and (24), (25).
- Step 2::
-
Find all the available paths \( P_{i} ,\quad i = 1,2, \ldots ,n \) and the corresponding path length. Also every n paths can be dealt as an arc which are represented by IVNN.
- Step 3::
-
Find the sum of all score functions \( {\mathbb{S}}\left( {\theta_{i} } \right) \) of each available path.
- Step 4::
-
The path which have minimum score value will represent an optimized interval valued shortest path by ranking in ascending order.
End
Note: TpIVNN-Trapezoidal interval valued neutrosophic number.
TIVNN-Triangular interval valued neutrosophic number.
Illustrative example to find the shortest path using TpIVNN
For the validation of the proposed algorithm, a network is adopted from Broumi et al. [43] and Kumar et al. [65].
Consider a network with six nodes and eight edges. The TpIVN cost is given below (Tables 5, 6).
Applying steps 1–4 of the proposed algorithm, it if found that \( 1 \to 2 \to 5 \to 6 \) is IVNP with lowest cost 4.18 and the IVNP is \( \left\langle {\left( {4,11,15,20} \right);\,\left[ {0.35,0.608} \right],\left[ {0.018,0.048} \right],\left[ {0.008,0.075} \right]} \right\rangle \).
Illustrative example to find the shortest path using TIVNN
For the validation of the proposed algorithm, an example network is adopted from Broumi et al. [26, 35].
Consider a network with six nodes and eight edges. The TIVN cost is given below (Tables 7, 8).
Applying steps 1–4 of the proposed algorithm, it if found that \( 1 \to 2 \to 5 \to 6 \) is IVNP with lowest cost 4.18 and the IVNP is \( \left\langle {\left( {4,11,15} \right);\,\left[ {0.35,0.61} \right],\left[ {0.02,0.05} \right],\left[ {0.01,0.08} \right]} \right\rangle \).
Comparative study of the proposed algorithm
In this section, a comparative study is carried out with the shortcomings and advantage of the proposed algorithm and it shows the effectiveness of the proposed algorithm
Shortcoming of the existing method
The compared existing method is unable to handle the interval-based information about the length of the arc and shortest path cannot be obtained for interval-based neutrosophic network.
Advantage of the proposed algorithm
If the length of the path is interval-based one then the shortest path of the given network can be obtained by interval valued neutrosophic numbers for an optimized path. Since triangular and trapezoidal numbers are widely used in many of the real world applications for their simplicity of computation, interval valued triangular and trapezoidal neutrosophic numbers have been used to find the neutrosophic shortest path. This is the advantage of the proposed algorithm.
Comparative study of algorithm
This section provides a comparative study of the proposed algorithm with the existing method of for neutrosophic shortest path problems.
A comparison of the results between existing and new techniques is shown in Table 9.
The result shows that the proposed algorithm provides sequence of visited nodes which shown to be similar with neutrosophic shortest path.
The neutrosophic shortest path (abbr.NSP) remains the same namely \( 1 \to 2 \to 5 \to 6 \), but the crisp shortest path length (CSPL) differs namely \( \left\langle {\left[ {0.35,0.60} \right],\left[ {0.01,0.04} \right],\left[ {0.008,0.075} \right]} \right\rangle \), respectively. From here we come to the conclusion that there exists no unique method for comparing neutrosophic numbers and different methods may satisfy different desirable criteria (Table 10).
Conclusion and future implication
The heart of the network community is nothing but the SPP. The objective of this problem is finding the minimum cost path among all other paths. This issue has been solved using many methods starts from conventional SPP with crisp weights. As many of the real world applications have uncertain vertices and edges fuzzy environment was useful to handle this problem. But still fuzzy setting cannot handle indeterminacy of the information, neutrosophic sets are found to be the best choice to handle this issue and has applied successfully. In this paper, neutrosophic SPP has been solved under interval valued neutrosophic, trapezoidal and triangular interval valued neutrosophic environments as it handles interval values. Also an improved score function and center of gravity has been proposed and applied to find the minimum cost of the path. Our proposed score function is without having the lower membership of falsity and which saves the time naturally. Further comparative analysis is done for Broumi’s algorithm with different deneutrosophication function and proposed one. It is found that minimum cost is less compare than other existing method using proposed algorithms and score function. Also the proposed algorithm and improved score function have less computational complexity and saves the time. In future, the SPP would be extended to neutrosophic soft and rough set environments for interval-based path lengths. Also the proposed concept will be extended to complex neutrosophic environment.
References
Ahuja RK, Mehlhrn K, Orlin JB, Tarjan RE (1990) Faster algorithms for the shortest path problem. J ACM 37:213–223
Yang CD, Lee DT, Wong CK (1992) On bends and lengths of rectilinear paths: a graph theoretic approach. Int J Comput Geom Appl 2(1):61–74
Ibarra OH, Zheng Q (1993) On the shortest path problem for permutation groups. In: Proceedings of 7th international conference on parallel processing symposium. https://doi.org/10.1109/ipps.1993.262881
Arsham H (1998) Stability analysis for the shortest path problem. Conf J Numer Themes 133:171–210
Tzoreff TE (1998) The disjoint shortest path problem. Discrete Appl Math 85(2):113–138
Batagelj V, Brandenburg FJ, Mendez PO, Sen A (2000) The generalized shortest path problem. Part of the project: unclassified. 1–11
Zhang J, Lin Y (2003) Computation of the reverse shortest-path problem. J Glob Optim 25:243–261
Vasantha WBK, Samaranadache F (2004) Basic neutrosophic structures and their application to fuzzy and neutrosophic models. Book in general mathematics. Hexis, Phoenix, pp 1–149
Roditty L, Zwick U (2004) On dynamic shortest paths problems. Algorithmica 61:389–401 (12th Annual European Symposium on Algorithms)
Irnich S, Desaulniers G (2005) Shortest path problems with resource constraints. In: Desaulniers G, Desrosiers J, Solomon MM (eds) Column generation. Springer, Boston, MA, pp 33–65
Buckley J, Jowers LJ (2007) Fuzzy shortest path problem. Monte Carlo methods in fuzzy optimization. Stud Fuzziness Soft Comput 222:191–193
Wastlund J (2009) Random assignment and shortest path problem. Discrete Math Theor Comput Sci 1–12
Turner L (2011) Variants of shortest path problems. Algorithmic Oper Res 6(2):91–104
Deng Y, Chen Y, Zhang Y, Mahadevan S (2012) Fuzzy Dijkstra algorithm for shortest path problem under uncertain environment. Appl Soft Comput 12(2012):1231–1237
Biswas SS, Alam B, Doja MN (2013) An algorithm for extracting intuitionistic fuzzy shortest path in a graph. Appl Comput Intell Soft Comput 2013:1–6
Arnautovic M, Curic M, Dolamic E, Nosovic N (2013) Parallelization of the ant colony optimization for the shortest path problem using open MP and CUDA. In: 36th International conference on information and communication technology electronics and microelectronics
Gabrel V, Murat C (2014) Robust shortest path problems. In book: Paradigms of combinatorial optimization. Project: robustness
Grigoryan H, Harutyunyan H (2014) The shortest path problem in the Knodel graph. J Discrete Algorithms 31:40
Rostami B, Malucelli F, Frey D, Buchheim C (2015) On the quadratic shortest path problem. Lect Notes Comput Sci 9125:379–390
Randour M, Raskin JC, Sankur O (2015) Variations on the stochastic shortest path problem. In: 16th International conference on verification, model checking, and abstract interpretation, LNCS 8931, pp 1–9
Broumi S, Bakal A, Talea M, Smarandache F, Vladareanu L (2016) Applying Dijkstra algorithm for solving neutrosophic shortest path problem. In: International conference on advanced mechatronic systems (ICAMechS) 2016
Broumi S, Bakali A, Mohamed T, Smarandache F, Vladareanu L (2016) Shortest path problem under triangular fuzzy neutrosophic information. In: 10th International conference on software, knowledge, information management and applications (SKIMA), pp 169–174
Broumi S, Mohamed T, Bakali A, Smarandache F (2016) Single valued neutrosophic graphs. J New Theory 10:86–101
Nancy Harish G (2016) An improved score function for ranking neutrosophic sets and its application to decision making process. Int J Uncertain Quantif 6(5):377–385
Şahin R, Liu P (2016) Maximizing deviation method for neutrosophic multiple attribute decision making with incomplete weight information. Neural Comput Appl 27(7):2017–2029. https://doi.org/10.1007/s00521-015-1995-8
Broumi S, Bakali A, Mohamed T, Smarandache F (2017) Computation of shortest path problem in a network with SV-triangular neutrosophic numbers. In: IEEE conference in innovations in intelligent systems and applications, Poland, pp 426–431
Broumi S, Bakali A, Mohamed T, Smarandache F, Verma R, Rajkumar S (2017) Computing minimum spanning tree in interval valued bipolar neutrosophic environment. Int J Model Optim 7(5):300–304
Hu H, Sotirov R (2018) On solving the quadratic shortest path problem. INFORMS J Comput 1–30
Dragan FF, Leitert A (2017) On the minimum eccentricity shortest path problem. Theor Comput Sci. https://doi.org/10.1016/j.tcs.2017.07.004
Zhang Y, Song S, Shen JM, Wu C (2017) Robust shortest path problem with distributional uncertainty. In: IEEE transactions on intelligent transportation systems, pp 1–12
Broumi S, Mohamed T, Bakali A, Smarandache F, Krishnan KK (2017) Shortest path problem on single valued neutrosophic graphs. In: International symposium on networks, computers and communications
Broumi S, Bakali A, Talea M, Smarandache F, Ali M (2017) Shortest path problem under bipolar neutrosophic setting. Appl Mech Mater 859(24):33
Peng X, Dai J (2017) Algorithms for interval neutrosophic multiple attribute decision-making based on MABAC, similarity measure, and EDAS. Int J Uncertain Quantif 7(5):395–421
Liu P, You X (2017) Interval neutrosophic muirhead mean operators and their applications in multiple-attribute group decision making. Int J Uncertain Quantif 7:303–334
Smarandache F (2005) A unifying field in logic. Neutrosophy: neutrosophic probability, set, logic, 4th edn. American Research Press, Rehoboth
Wang H, Smarandache F, Zhang Y, Sunderraman R (2010) Single valued neutrosophic sets. Multisp Multistruct 4:410–413
Deli I, Şubaş Y (2017) A ranking method of single valued neutrosophic numbers and its applications to multi-attribute decision making problems. Int J Mach Learn Cybern 8(2017):1309–1322
Broumi S, Bakali A, Mohamed T, Samarandache F, Son LH, Kumar PKK (2018) New matrix algorithm for minimum spanning tree with undirected interval valued neutrosophic graph neutrosophic. Oper Res Int J 2:54–69
Enayattabar M, Ebrahimnejad A, Motameni H (2018) Dijkstra algorithm for shortest path problem under interval-valued Pythagorean fuzzy environment. Complex Intell Syst 1–8
Broumi S, Bakali A, Talea M, Smarandache F, Karaaslan F (2018) Interval valued neutrosophic soft graphs. Proj New Trends Neutrosophic Theory Appl 2:218–251
Broumi S, Bakali A, Talea M, Smarandache F, Ulucay V, Sahin M, Dey A, Dhar M, Tan RP, Bahnasse A, Pramanik S (2018) Neutrosophic sets: on overview. Proj New Trends Neutrosophic Theory Appl 2:403–434
Broumi S, Ullah K, Bakali A, Talea M, Singh PK, Mahmood T, Samarandache F, Bahnasse A, Patro SK, Oliveira AD (2018) Novel system and method for telephone network planing based on neutrosophic graph. Glob J Comput Sci Technol E Netw Web Secur 18(2):1–11
Broumi S, Bakali A, Talea M, Smarandache F, Kishore KK, Şahin R (2018) Shortest path problem under interval valued neutrosophic setting. J Fundam Appl Sci 10(4S):168–174
Bolturk E, Kahraman C (2018) A novel interval-valued neutrosophic AHP with cosine similarity measure. Soft Comput 22(15):4941–4958
Wang H, Smarandache F, Zhang YQ, Sunderraman R (2005) Interval neutrosophic sets and logic: theory and applications in computing. Hexis, Phoenix
Biswas P, Pramanik S, Giri BC (2018) Distance measure based MADM strategy with interval trapezoidal neutrosophic numbers. Neutrosophic Sets Syst 19:40–46
Deli I (2018) Expansions and reductions on neutrosophic classical soft set. Süleyman Demirel Univ J Nat Appl Sci 22(2018):478–486
Deli I (2017) Interval-valued neutrosophic soft sets and its decision making. Int J Mach Learn Cybern 8(2):665–676
Deli I (2015) npn-Soft sets theory and applications. Ann Fuzzy Math Inf 10(6):847–862
Deli I (2018) Operators on single valued trapezoidal neutrosophic numbers and SVTN-group decision making. Neutrosophic Sets Syst 22:131–151
Deli I, Şubaş Y (2017) Some weighted geometric operators with SVTrN-numbers and their application to multi-criteria decision making problems. J Intell Fuzzy Syst 32(1):291–301
Deli I, Eraslan S, Çağman N (2018) ivnpiv-Neutrosophic soft sets and their decision making based on similarity measure. Neural Comput Appl 29(1):187–203. https://doi.org/10.1007/s00521-016-2428-z
Basset MA, Mohamed M, Smarandache F (2018) A hybrid neutrosophic group ANP-TOPSIS framework for supplier selection problems. Symmetry 10(226):1–21
Chang V, Basset MA, Ramachandran M (2018) Towards a reuse strategic decision pattern framework-from theories to practices. Inf Syst Front 1–18
Basset MA, Manogaran G, Gamal A, Smarandache F (2018) A hybrid approach of neutrosophic sets and DEMATEL method for developing supplier selection criteria. Des Autom Embedded Syst 1–22
Basset MA, Zhou Y, Mohamed M, Chang C (2018) A group decision making framework based on neutrosophic VIKOR approach for e-government website evaluation. J Intell Fuzzy Syst 34(6):4213–4224
Basset MA, Mohamed M, Chang C (2018) NMCDA: a framework for evaluating cloud computing services. Fut Gener Comput Syst 86:12–29
Basset MA, Atef A, Smarandache F (2018) A hybrid neutrosophic multiple criteria group decision making approach for project selection. Cogn Syst Res. https://doi.org/10.1016/j.cogsys.2018.10.023
Basset MA, Gunasekaran M, Mohamed M, Smarandache F (2018) A novel method for solving the fully neutrosophic linear programming problems. Neural Comput Appl. https://doi.org/10.1007/s00521-018-3404-6
Basset MA, Gunasekaran M, Mohamed M, Chilamkurti N (2018) A framework for risk assessment, management and evaluation: economic tool for quantifying risks in supply chain. Fut Gener Comput Syst 90:489–502
Basset MA, Gunasekaran M, Mohamed M, Chilamkurti N (2018) Three-way decisions based on neutrosophic sets and AHP-QFD framework for supplier selection problem. Fut Gener Comput Syst. https://doi.org/10.1016/j.future.2018.06.024
Basset MA, Mohamed M, Kumar A (2017) Neutrosophic AHP-Delphi Group decision making model based on trapezoidal neutrosophic numbers. J Ambient Intell Hum Comput 9(5):1627–1443
Basset MA, Mohamed M, Zhou Y, Hezam IM (2017) Multi-criteria group decision making based on neutrosophic analytic hierarchy process. J Intell Fuzzy Syst 33(6):4055–4066
Basset MA, Mohamed M, Hussien AN, Sangaiah AK (2017) A novel group decision-making model based on triangular neutrosophic numbers. Soft Comput 22(20):6629–6643
Kumar R, Edaltpanah SA, Jha S, Broumi S, Dey A (2018) Neutrosophic shortest path problem. Neutrosophic Sets Syst 23:5–15
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., Nagarajan, D., Bakali, A. et al. The shortest path problem in interval valued trapezoidal and triangular neutrosophic environment. Complex Intell. Syst. 5, 391–402 (2019). https://doi.org/10.1007/s40747-019-0092-5
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s40747-019-0092-5