We consider an intuitionistic fuzzy shortest path problem (IFSPP) in a directed graph where the weights of the links are intuitionistic fuzzy numbers. We develop a method to search for an intuitionistic fuzzy shortest path from a source node to a destination node. We coin the concept of classical Dijkstra’s algorithm which is applicable to graphs with crisp weights and then extend this concept to graphs where the weights of the arcs are intuitionistic fuzzy numbers. It is claimed that the method may play a major role in many application areas of computer science, communication network, transportation systems, and so forth. in particular to those networks for which the link weights (costs) are ill defined. 1. Introduction Graphs [1–4] are a very important model of networks. There are many real-life problems of network of transportation, communication, circuit systems, and so forth, which are modeled into graphs and hence solved. Graph theory has wide varieties of applications in several branches of engineering, science, social science, medical science, economics, and so forth, to list a few only out of many. Many real-life situations of communication network, transportation network, and so forth cannot be modeled into crisp graphs because of the reason that few or all of the arcs/links have the cost/weight which is ill defined. The weights of the arcs are not always crisp but intuitionistic fuzzy (or fuzzy). One of the first studies on fuzzy shortest path problem (FSPP) in graphs was done by Dubois and Prade [5] and then by Klein [6]. However, few more solutions to FSPP proposed in [7–10] are also interesting. Though the work of Dubois and Prade [5] was a major breakthrough, that paper lacked any practical interpretation even if fuzzy shortest path is found, but still this may not actually be any of the path in the corresponding network for which it was found. There are very few works reported in the literature on finding an intuitionistic fuzzy shortest path in a graph. Mukherjee [11] used a heuristic methodology for solving the IF shortest path problem using the intuitionistic fuzzy hybrid geometric (IFHG) operator, with the philosophy of Dijkstra’s algorithm. In [12], Karunambigai et al. in a team work with Atanassov, present a model based on dynamic programming to find the shortest paths in intuitionistic fuzzy graphs. Nagoor Gani and Mohammed Jabarulla in [13] also developed a method on searching intuitionistic fuzzy shortest path in a network. But all these algorithms have both merits and demerits (none is absolutely the best), as all these are
References
[1]
V. K. Balakrishnan, Graph Theory, McGraw-Hill, New York, NY, USA, 1997.
[2]
B. Bollobas, Modern Graph Theory, Springer, New York, NY, USA, 2002.
[3]
R. Diestel, Graph Theory, Springer, 2000.
[4]
F. Harary, Graph Theory, Addison Wesley, Boston, Mass, USA, 1995.
[5]
D. Dubois and H. Prade, Fuzzy Sets and Systems, Academic Press, New York, NY, USA, 1980.
[6]
C. M. Klein, “Fuzzy shortest paths,” Fuzzy Sets and Systems, vol. 39, no. 1, pp. 27–41, 1991.
[7]
S. Okada and T. Soper, “A shortest path problem on a network with fuzzy arc lengths,” Fuzzy Sets and Systems, vol. 109, no. 1, pp. 129–140, 2000.
[8]
L. Sujatha and S. Elizabeth, “Fuzzy shortest path problem based on similarity degree,” Applied Mathematical Sciences, vol. 5, no. 66, pp. 3263–3276, 2011.
[9]
J.-S. Yao and F.-T. Lin, “Fuzzy shortest-path network problems with uncertain edge weights,” Journal of Information Science and Engineering, vol. 19, no. 2, pp. 329–351, 2003.
[10]
J.-R. Yu and T.-H. Wei, “Solving the fuzzy shortest path problem by using a linear multiple objective programming,” Journal of the Chinese Institute of Industrial Engineers, vol. 24, no. 5, pp. 360–365, 2007.
[11]
S. Mukherjee, “Dijkstra’s algorithm for solving the shortest path problem on networks under intuitionistic fuzzy environment,” Journal of Mathematical Modelling and Algorithms, vol. 11, no. 4, pp. 345–359, 2012.
[12]
M. G. Karunambigai, P. Rangasamy, K. Atanassov, and N. Palaniappan, “An intuitionistic fuzzy graph method for finding the shortest paths in networks,” Advances in Soft Computing, vol. 42, pp. 3–10, 2007.
[13]
A. Nagoor Gani and M. Mohammed Jabarulla, “On searching intuitionistic fuzzy shortest path in a network,” Applied Mathematical Sciences, vol. 4, no. 69, pp. 3447–3454, 2010.
[14]
K. T. Atanassov, “Intuitionistic fuzzy sets,” Fuzzy Sets and Systems, vol. 20, no. 1, pp. 87–96, 1986.
[15]
K. Atanassov, Intuitionistic Fuzzy Sets:Theory and Applications, Physica, 1999.
[16]
K. T. Atanassov, “More on intuitionistic fuzzy sets,” Fuzzy Sets and Systems, vol. 33, no. 1, pp. 37–45, 1989.
[17]
D.-F. Li, “A ratio ranking method of triangular intuitionistic fuzzy numbers and its application to MADM problems,” Computers and Mathematics with Applications, vol. 60, no. 6, pp. 1557–1570, 2010.
[18]
D. F. Li, J. X. Nan, and M. J. Zhang, “A ranking method of triangular intuitionistic fuzzy numbers and application to decision making,” International Journal of Computational Intelligence Systems, vol. 3, no. 5, pp. 522–530, 2010.
[19]
H. B. Mitchell, “Ranking-intuitionistic fuzzy numbers,” International Journal of Uncertainty, Fuzziness and Knowlege-Based Systems, vol. 12, no. 3, pp. 377–386, 2004.
[20]
S. Abbasbandy, “Ranking of fuzzy numbers, some recent and new formulas,” in Proceedings of the IFSA-EUSFLAT, pp. 642–646, Lisbon, Portugal, July 2009.
[21]
T. Allahviranloo, S. Abbasbandy, and R. Saneifard, “A method for ranking of fuzzy numbers using new weighted distance,” Mathematical and Computational Applications, vol. 16, no. 2, pp. 359–369, 2011.
[22]
L. Q. Dat, V. F. Yu, and S. Y. Chou, “An improved ranking method for fuzzy numbers using left and right indices,” in Proceedings of the 2nd International Conference on Computer Design and Engineering (IPCSIT '12), vol. 49, pp. 89–94, 2012.
[23]
B. Farhadinia, “Ranking fuzzy numbers on lexicographical ordering,” International Journal of Applied Mathematics and Computer Sciences, vol. 5, no. 4, pp. 248–251, 2009.
[24]
N. Parandin, Araghi, and M. A. Fariborzi, “Ranking of fuzzy numbers by distance method,” Journal of Applied Mathematics, vol. 5, no. 19, pp. 47–55, 2008.
[25]
N. R. Shankar and P. P. B. Rao, “Ranking fuzzy numbers with a distance method using circumcenter of centroids and an index of modality,” Advances in Fuzzy Systems, vol. 2011, Article ID 178308, 7 pages, 2011.
[26]
R. Saneifard and R. Ezzati, “A new approach for ranking fuzzy numbers with continuous weighted quasi-arithmatic means,” Mathematical Sciences, vol. 4, no. 2, pp. 143–158, 2010.
[27]
R. Biswas, “Fuzzy numbers redefined,” Information, vol. 15, no. 4, pp. 1369–1380, 2012.
