13 results on '"Shortest path problem"'
Search Results
2. Employing the Bellman-Ford Algorithm with Score Functions to Address the Linear Diophantine Fuzzy Shortest Path Problem in Network Analysis.
- Author
-
Kannan, Vidhya and Appasamy, Saraswathi
- Subjects
FUZZY numbers ,FUZZY graphs ,ALGORITHMS - Abstract
The realms of Intuitionistic Fuzzy Sets (IFSs), Pythagorean Fuzzy Sets (PFS), and qrung Orthopair Fuzzy Sets (q-ROFSs) have found extensive applications across various disciplines, notably in resolving real-world problems. However, limitations concerning membership and non-membership grades pose challenges to these theories. Efforts to mitigate these constraints have led to the introduction of a new concept, the Linear Diophantine Fuzzy Set (LDFS), with reference parameters. This study advances the shortest path (SP) problem for Linear Diophantine Fuzzy graphs. An innovative method for constructing direct network graphs within a Linear Diophantine Fuzzy (LDF) context is proposed. Distances or costs between nodes are encapsulated by Linear Diophantine Fuzzy numbers. The principal contribution of this investigation lies in proposing a novel approach to solving the Linear Fuzzy Diophantine Fuzzy shortest path problem using the Bellman-Ford algorithm for optimal solution attainment. Usage of the score function enables the comparison and identification of the minimum arc value between nodes. The proposed algorithm's validity is demonstrated through a numerical example, and a comparison with existing methodologies underscores the benefits of the proposed algorithm. [ABSTRACT FROM AUTHOR]
- Published
- 2023
- Full Text
- View/download PDF
3. Calculation of Fuzzy shortest path problem using Multi-valued Neutrosophic number under fuzzy environment.
- Author
-
Raut, Prasanta Kumar, Behera, Siva Prasad, Broumi, Said, and Mishra, Debdas
- Subjects
- *
GRAPH theory , *GRAPH connectivity , *DIRECTED graphs , *FIRE stations , *TELECOMMUNICATION systems , *SERVICE stations , *FUZZY numbers - Abstract
The most well-known subject in graph theory is the shortest path problem (SPP), which has real-world applications in several different fields of study, including transportation, emergency services, network communications, fire station services, etc. The arc weights of the applicable SP problems are typically represented by fuzzy numbers in real-world applications. In this paper, we discussed the process of finding the shortest distance in a connected graph network in which the arc weights are multi-valued neutrosophic numbers (MNNs). Moreover, here we compare our method with some of the existing results and illustrate one implementation of our method with the help of one numerical example. [ABSTRACT FROM AUTHOR]
- Published
- 2023
4. Bellman–Ford algorithm for solving shortest path problem of a network under picture fuzzy environment.
- Author
-
Parimala, Mani, Broumi, Said, Prakash, Karthikeyan, and Topal, Selçuk
- Subjects
FUZZY numbers ,SET theory ,PICTURES ,FUZZY graphs ,RESEARCH methodology - Abstract
An elongation of the novel intuitionistic fuzzy set is a picture fuzzy set theory. The demonstration of this has been used to deal with the abstinence criteria in a decision-making problem. The uncertainty in nature occurs sometimes in real-world problems and amidst them, the prominent one is the shortest path problem (SPP) solving. In the last few years, one of the best algorithms on the network for finding SPP is Bellman–Ford. Due to uncertainty in the decision-making process, it becomes difficult for decision-makers for communicating their point of view and judgment with certainty. We conceive of SPP in this contribution via Bellman's algorithm (BA) for a network with trapezoidal picture fuzzy numbers (TPFNs). We introduce a new algorithm to stand the shortest picture fuzzy path between each pair of nodes. A TPFN is considered for the length of all edges. A numerical example for the validation of the presented algorithm has also been proposed. There has also been relative research with existing techniques showing the benefits of the new algorithm. [ABSTRACT FROM AUTHOR]
- Published
- 2021
- Full Text
- View/download PDF
5. Modified artificial bee colony algorithm for solving mixed interval-valued fuzzy shortest path problem.
- Author
-
Ebrahimnejad, Ali, Enayattabr, Mohammad, Motameni, Homayun, and Garg, Harish
- Subjects
BEES algorithm ,WIRELESS sensor networks ,PARTICLE swarm optimization ,FUZZY numbers ,MEMBERSHIP functions (Fuzzy logic) - Abstract
In recent years, numerous researchers examined and analyzed several different types of uncertainty in shortest path (SP) problems. However, those SP problems in which the costs of arcs are expressed in terms of mixed interval-valued fuzzy numbers are less addressed. Here, for solving such uncertain SP problems, first a new procedure is extended to approximate the summation of mixed interval-valued fuzzy numbers using alpha cuts. Then, an extended distance function is introduced for comparing the path weights. Finally, we intend to use a modified artificial bee colony (MABC) algorithm to find the interval-valued membership function of SP in such mixed interval-valued fuzzy network. The proposed algorithm is illustrated via two applications of SP problems in wireless sensor networks and then the results are compared with those derived from genetic and particle swarm optimization (PSO) algorithms, based on three indexes convergence iteration, convergence time and run time. The obtained results confirm that the MABC algorithm has less convergence iteration, convergence time and implementation time compared to GA and PSO algorithm. [ABSTRACT FROM AUTHOR]
- Published
- 2021
- Full Text
- View/download PDF
6. Fuzzy Constrained Shortest Path Problem for Location-Based Online Services.
- Author
-
Sori, Ali Abbaszadeh, Ebrahimnejad, Ali, Motameni, Homayun, and Verdegay, Jose Luis
- Subjects
- *
LOCATION-based services , *ENVIRONMENTAL economics , *WEATHER , *FUZZY numbers , *DYNAMIC programming - Abstract
One of the important issues under discussion connected with traffic on the roads is improving transportation. In this regard, spatial information, including the shortest path, is of particular importance due to the reduction of economic and environmental costs. Here, the constrained shortest path (CSP) problem which has an important application in location-based online services is considered. The aim of this problem is to find a path with the lowest cost where the traversal time of the path does not exceed from a predetermined time bound. Since precise prediction of cost and time of the paths is not possible due to traffic and weather conditions, this paper discusses the CSP problems with fuzzy cost and fuzzy time. After formulating the CSP problem an efficient algorithm for finding the constrained optimal path is designed. The application of the proposed model is presented on a location-based online service called Snap. [ABSTRACT FROM AUTHOR]
- Published
- 2021
- Full Text
- View/download PDF
7. Solving fuzzy multi-objective shortest path problem based on data envelopment analysis approach.
- Author
-
Bagheri, M., Ebrahimnejad, Ali, Razavyan, S., Lotfi, F. Hosseinzadeh, and Malekmohammadi, N.
- Subjects
DATA envelopment analysis ,LINEAR programming ,FUZZY graphs ,QUALITY of service - Abstract
The shortest path problem (SPP) is a special network structured linear programming problem that appears in a wide range of applications. Classical SPPs consider only one objective in the networks while some or all of the multiple, conflicting and incommensurate objectives such as optimization of cost, profit, time, distance, risk, and quality of service may arise together in real-world applications. These types of SPPs are known as the multi-objective shortest path problem (MOSPP) and can be solved with the existing various approaches. This paper develops a Data Envelopment Analysis (DEA)-based approach to solve the MOSPP with fuzzy parameters (FMOSPP) to account for real situations where input–output data include uncertainty of triangular membership form. This approach to make a connection between the MOSPP and DEA is more flexible to deal with real practical applications. To this end, each arc in a FMOSPP is considered as a decision-making unit with multiple fuzzy inputs and outputs. Then two fuzzy efficiency scores are obtained corresponding to each arc. These fuzzy efficiency scores are combined to define a unique fuzzy relative efficiency. Hence, the FMOSPP is converted into a single objective Fuzzy Shortest Path Problem (FSPP) that can be solved using existing FSPP algorithms. [ABSTRACT FROM AUTHOR]
- Published
- 2021
- Full Text
- View/download PDF
8. Dijkstra algorithm for shortest path problem under interval-valued Pythagorean fuzzy environment.
- Author
-
Enayattabar, Mohammad, Ebrahimnejad, Ali, and Motameni, Homayun
- Subjects
FUZZY numbers ,ALGORITHMS ,FUZZY graphs ,FUZZY sets ,FUZZY mathematics - Abstract
Pythagorean fuzzy set as an extension of fuzzy set has been presented to handle the uncertainty in real-world decision-making problems. In this work, we formulate a shortest path (SP) problem in an interval-valued Pythagorean fuzzy environment. Here, the costs related to arcs are taken in the form of interval-valued Pythagorean fuzzy numbers (IVPFNs). The main contributions of this paper are fourfold: (1) the interval-valued Pythagorean fuzzy optimality conditions in directed networks are described to design of solution algorithm. (2) To do this, an improved score function is used to compare the costs between different paths with their arc costs represented by IVPFNs. (3) Based on these optimality conditions and the improved score function, the traditional Dijkstra algorithm is extended to find the cost of interval-valued Pythagorean fuzzy SP (IVPFSP) and corresponding IVPFSP. (4) Finally, a small sized telecommunication network is provided to illustrate the potential application of the proposed method. [ABSTRACT FROM AUTHOR]
- Published
- 2019
- Full Text
- View/download PDF
9. Neutrosophic Shortest Path Problem.
- Author
-
Kumar, Ranjan, Edaltpanah, S. A., Jha, Sripati, Broumi, Said, and Dey, Arindam
- Subjects
- *
NEUTROSOPHIC logic , *FUZZY numbers , *MATHEMATICAL optimization , *GEOGRAPHIC information systems , *GENETIC algorithms - Abstract
Neutrosophic set theory provides a new tool to handle the uncertainties in shortest path problem (SPP). This paper introduces the SPP from a source node to a destination node on a neutrosophic graph in which a positive neutrosophic number is assigned to each edge as its edge cost. We define this problem as neutrosophic shortest path problem (NSSPP). A simple algorithm is also introduced to solve the NSSPP. The proposed algorithm finds the neutrosophic shortest path (NSSP) and its corresponding neutrosophic shortest path length (NSSPL) between source node and destination node. Our proposed algorithm is also capable to find crisp shortest path length (CrSPL) of the corresponding neutrosophic shortest path length (NSSPL) which helps the decision maker to choose the shortest path easily. We also compare our proposed algorithm with some existing methods to show efficiency of our proposed algorithm. Finally, some numerical experiments are given to show the effectiveness and robustness of the new model. Numerical and graphical results demonstrate that the novel methods are superior to the existing method. [ABSTRACT FROM AUTHOR]
- Published
- 2018
10. The attitude of MCDM approaches versus the optimization model in finding the safest shortest path on a fuzzy network.
- Author
-
Özçelik, Gökhan
- Subjects
- *
MULTIPLE criteria decision making , *FUZZY sets , *COMPUTATIONAL complexity , *FUZZY numbers - Abstract
• An auxiliary algorithm is proposed to construct initial stage of the MCDM methods. • A multi-objective fuzzy optimization model is formulated. • An extensive comparative analysis is conducted in terms of the addressed methods. • The stability and validity of the results are tested and discussed. • Key findings and managerial insights are provided. This paper examines the performances of the multi-criteria decision-making (MCDM) methods and optimization model in solving multi-attribute shortest path problems such as the safest shortest path under a fuzzy environment. To the best of the knowledge of the authors, this is the first study performing comparative analysis on finding the multi-attribute shortest path by employing well-known techniques in terms of computational effort and results in a fuzzy environment. To this end, the safest shortest path problem, where the risk and distance values concerning arcs on a directed network are defined as triangular fuzzy numbers, is handled. The solution process is carried out under two main headings: (i) To start the solution with MCDM methods, an auxiliary algorithm that constructs a fuzzy decision matrix is proposed. Then, Fuzzy-Technique for Order Preference by Similarity to Ideal Solution (F-TOPSIS), Fuzzy Simple Additive Weighting (F-SAW), and Fuzzy Evaluation Based on Distance from Average Solution (F-EDAS), that are fuzzy-based MCDM methods, are employed to rank the alternative paths. (ii) A multi-objective fuzzy optimization model is formulated, and the most reasonable paths are obtained considering different α-cut levels. Following that, comparative analysis is performed through a set of scenarios considering the different weights of the criteria to see the variability in the rankings. Besides, the addressed fuzzy-based MCDM methods are compared in terms of computational complexity. Overall, the main findings and managerial insights regarding the effectiveness and performance of the methods discussed in the solution process are provided. [ABSTRACT FROM AUTHOR]
- Published
- 2022
- Full Text
- View/download PDF
11. Fuzzy Dijkstra algorithm for shortest path problem under uncertain environment.
- Author
-
Deng, Yong, Chen, Yuxin, Zhang, Yajuan, and Mahadevan, Sankaran
- Subjects
FUZZY algorithms ,PROBLEM solving ,GENERALIZATION ,FUZZY numbers ,NUMERICAL analysis ,PATHS & cycles in graph theory - Abstract
Abstract: A common algorithm to solve the shortest path problem (SPP) is the Dijkstra algorithm. In this paper, a generalized Dijkstra algorithm is proposed to handle SPP in an uncertain environment. Two key issues need to be addressed in SPP with fuzzy parameters. One is how to determine the addition of two edges. The other is how to compare the distance between two different paths with their edge lengths represented by fuzzy numbers. To solve these problems, the graded mean integration representation of fuzzy numbers is adopted to improve the classical Dijkstra algorithm. A numerical example of a transportation network is used to illustrate the efficiency of the proposed method. [Copyright &y& Elsevier]
- Published
- 2012
- Full Text
- View/download PDF
12. Applying the Dijkstra Algorithm to Solve a Linear Diophantine Fuzzy Environment.
- Author
-
Parimala, Mani, Jafari, Saeid, Riaz, Muhamad, and Aslam, Muhammad
- Subjects
- *
FUZZY numbers , *ALGORITHMS , *DIRECTED graphs , *FUZZY sets , *TELECOMMUNICATION systems , *FUZZY graphs - Abstract
Linear Diophantine fuzzy set (LDFS) theory expands Intuitionistic fuzzy set (IFS) and Pythagorean fuzzy set (PyFS) theories, widening the space of vague and uncertain information via reference parameters owing to its magnificent feature of a broad depiction area for permissible doublets. We codify the shortest path (SP) problem for linear Diophantine fuzzy graphs. Linear Diophantine fuzzy numbers (LDFNs) are used to represent the weights associated with arcs. The main goal of the presented work is to create a solution technique for directed network graphs by introducing linear Diophantine fuzzy (LDF) optimality constraints. The weights of distinct routes are calculated using an improved score function (SF) with the arc values represented by LDFNs. The conventional Dijkstra method is further modified to find the arc weights of the linear Diophantine fuzzy shortest path (LDFSP) and coterminal LDFSP based on these enhanced score functions and optimality requirements. A comparative analysis was carried out with the current approaches demonstrating the benefits of the new algorithm. Finally, to validate the possible use of the proposed technique, a small-sized telecommunication network is presented. [ABSTRACT FROM AUTHOR]
- Published
- 2021
- Full Text
- View/download PDF
13. Shortest Path Solution of Trapezoidal Fuzzy Neutrosophic Graph Based on Circle-Breaking Algorithm.
- Author
-
Yang, Lehua, Li, Dongmei, and Tan, Ruipu
- Subjects
- *
ALGORITHMS , *FUZZY graphs , *FUZZY numbers - Abstract
The shortest path problem is a topic of increasing interest in various scientific fields. The damage to roads and bridges caused by disasters makes traffic routes that can be accurately expressed become indeterminate. A neutrosophic set is a collection of the truth membership, indeterminacy membership, and falsity membership of the constituent elements. It has a symmetric form and indeterminacy membership is their axis of symmetry. In uncertain environments, the neutrosophic number can more effectively express the edge distance. The objectives in this study are to solve the shortest path problem of the neutrosophic graph with an edge distance expressed using trapezoidal fuzzy neutrosophic numbers (TrFNN) and resolve the edge distance according to the score and exact functions based on the TrFNN. Accordingly, the use of a circle-breaking algorithm is proposed to solve the shortest path problem and estimate the shortest distance. The feasibility of this method is verified based on two examples, and the rationality and effectiveness of the approach are evaluated by comparing it with the Dijkstra and Bellman algorithms. [ABSTRACT FROM AUTHOR]
- Published
- 2020
- Full Text
- View/download PDF
Catalog
Discovery Service for Jio Institute Digital Library
For full access to our library's resources, please sign in.