A Greedy Algorithm for Fuzzy Shortest Path Problem using Quasi-Gaussian Fuzzy Weights

Madhushi Verma and K. K. Shukla
Additional contact information
Madhushi Verma: Department of Computer Engineering, IIT(BHU), Varanasi, India
K. K. Shukla: Department of Computer Engineering, IIT(BHU), Varanasi, India

International Journal of Fuzzy System Applications (IJFSA), 2013, vol. 3, issue 2, 55-70

Abstract: Several algorithms exist to determine the shortest path in a network for the crisp case where the weights are real numbers. In the real world, these weights represent parameters like cost, packet arrival time, link capacity etc which are not naturally precise. To model the uncertainty involved, for the first time we use the Gaussian fuzzy numbers as weights and a method has been presented in this paper to determine the fuzzy shortest path. Gaussian membership functions are preferred over other membership functions (triangular and trapezoidal) that are easy to analyze because it is continuous and differentiable enabling efficient gradient based optimization and it is simpler to represent because it requires fewer parameters. The issue of performing fuzzy arithmetic operations to calculate the fuzzy shortest path length and the corresponding fuzzy shortest path in the network has been addressed and to tackle it the concept of decomposed fuzzy numbers has been used. Also, a greedy algorithm which is an extension of Dijkstra’s algorithm for fuzzy shortest path problem has been proposed.

Date: 2013
References: Add references at CitEc
Citations:

Downloads: (external link)
http://services.igi-global.com/resolvedoi/resolve. ... 018/ijfsa.2013040104 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:igg:jfsa00:v:3:y:2013:i:2:p:55-70

Access Statistics for this article

International Journal of Fuzzy System Applications (IJFSA) is currently edited by Deng-Feng Li

More articles in International Journal of Fuzzy System Applications (IJFSA) from IGI Global
Bibliographic data for series maintained by Journal Editor ().