8 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. Floyd-Warshall Algorithm Based on Picture Fuzzy Information.
- Author
-
Habib, Shaista, Majeed, Aqsa, Akram, Muhammad, and Ali Al-Shamiri, Mohammed M.
- Subjects
ALGORITHMS ,FUZZY algorithms ,COMPUTER networks ,PICTURES ,FUZZY numbers ,FUZZY sets - Abstract
The Floyd-Warshall algorithm is frequently used to determine the shortest path between any pair of nodes. It works well for crisp weights, but the problem arises when weights are vague and uncertain. Let us take an example of computer networks, where the chosen path might no longer be appropriate due to rapid changes in network conditions. The optimal path from among all possible courses is chosen in computer networks based on a variety of parameters. In this paper, we design a new variant of the Floyd-Warshall algorithm that identifies an All-Pair Shortest Path (APSP) in an uncertain situation of a network. In the proposed methodology, multiple criteria and their mutual association may involve the selection of any suitable path between any two node points, and the values of these criteria may change due to an uncertain environment. We use trapezoidal picture fuzzy addition, score, and accuracy functions to find APSP. We compute the time complexity of this algorithm and contrast it with the traditional Floyd-Warshall algorithm and fuzzy Floyd-Warshall algorithm. [ABSTRACT FROM AUTHOR]
- Published
- 2023
- Full Text
- View/download PDF
5. Admissible Orders on Fuzzy Numbers.
- Author
-
Zumelzu, Nicolas, Bedregal, Benjamin, Mansilla, Edmundo, Bustince, Humberto, and Diaz, Roberto
- Subjects
WEIGHTED graphs ,FUZZY graphs ,FUZZY numbers ,LINEAR orderings ,FUZZY sets - Abstract
From the more than two hundred partial orders for fuzzy numbers proposed in the literature, only a few are total. In this article, we introduce the notion of admissible order for fuzzy numbers equipped with a partial order, i.e., a total order which refines the partial order. In particular, it is given special attention to the partial order proposed by Klir and Yuan in 1995. Moreover, we propose a method to construct admissible orders on fuzzy numbers in terms of linear orders defined for intervals considering a strictly increasing upper dense sequence, proving that this order is admissible for a given partial order. Finally, we use admissible orders to ranking the path costs in fuzzy weighted graphs. [ABSTRACT FROM AUTHOR]
- Published
- 2022
- Full Text
- View/download PDF
6. 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
7. 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
8. 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
Catalog
Discovery Service for Jio Institute Digital Library
For full access to our library's resources, please sign in.