Oriental Journal of Computer Science and Technology

Open Access Open Access  Restricted Access Subscription Access

Z-Dijkstra’s Algorithm to solve Shortest Path Problem in a Z-Graph


Affiliations
1 Department of Computer Science and Engineering, Jamia Hamdard University Hamdard Nagar, New Delhi – 110062, India
 

In this paper the author introduces the notion of Z-weighted graph or Z-graph in Graph Theory, considers the Shortest Path Problem (SPP) in a Z-graph. The classical Dijkstra’s algorithm to find the shortest path in graphs  is not applicable to Z-graphs. Consequently the author proposes a new algorithm called by Z-Dijkstra's Algorithm with the philosophy of the classical Dijkstra's Algorithm to solve the SPP in a Z-graph.


Keywords

Z-Number, Z-Distance, Z-Weighted Graph, Z-Graph, Z-Dijkstra's.
User
Notifications
Font Size

  • Abbasbandy, Saeid, Ranking of fuzzy numbers, some recent and new formulas, IFSA-EUSFLAT, 2009, Page 642- 646.

  • Abbasbandy, Saeid., Allahviranloo, T. and Saneifard, R., A Method for Ranking of Fuzzy Numbers using New Weighted Distance, Mathematical and Computational Applications, 16(2), Page 359-369, 2011.

  • Balakrishnan, V. K.; Graph Theory, McGraw-Hill; 1997.

  • Bhutani,K.R. and Rosenfeld,A., Fuzzy End Nodes in Fuzzy Graphs, Information Sciences, 152, 323-326, (2003).

  • Biswas, S. S., Alam, B. and Doja, M. N., A Generalized Real Time Multigraphs For Communication Networks : An Intuitionistic Fuzzy Theoretical Model, 17th International Conference on IFS, Sofia, Bulgaria, Proceedings published in Notes on Intuitionistic Fuzzy Sets (Bulgarian Journal) 19(3) 2013: pp 90-98, ISSN : 1310-4926

  • Biswas, S. S., Alam, B. and Doja, M. N., GRT-Multigraphs For Communication Networks : A Fuzzy Theoretical Model, International Symposium on System Engineering and Computer Simulation (SECS-2013), Held in Danang, Vietnam. Published at Advanced in Computer Science and its Applications, Series Title : Lecture Notes in Electrical Engineering (Springer Berlin Heidelberg Publications) , 279, Pages 633-641, 2014, Print ISBN : 978-3-642-41673-6 , Online ISBN : 978-3-642-41674-3, doi: 10.1007/978-3-642-41674-3_91.

  • Biswas, S. S., Alam, B. and Doja, M. N., A Refinement of Dijkstra’s Algorithm For Extraction of Shortest Paths in GRT-Multigraphs, Journal of Computer Science, 10(4) 2013: pp 593-603, ISSN 1549-3636, doi: 10.3844/jcssp.2014.593.603.

  • Biswas, S. S., Alam, B. and Doja, M. N., Real Time Multigraphs For Communication Networks : An Intuitionistic Fuzzy Mathematical Model, Journal of Computer Science, 9 (7): pp 847-855, 2013, ISSN 1549-3636, doi: 10.3844/jcssp.2013.847.855.

  • Biswas, S. S., Alam, B. and Doja, M. N., Intuitionistic Fuzzy Real Time Multigraphs For Communication Networks : A Theoretical Model, AASRI Conference on Parallel and Distributed Computing and Systems (DCS 2013), Held in Singapore, Published by AASRI Proceedings (Elsevier Publications), 5, Pages 114–119, 2013, doi: 10.1016/j.aasri.2013.10.066.

  • Biswas, S. S., Alam, B. and Doja, M. N., Real Time Graphs For Communication Networks: A Fuzzy Mathematical Model, Sadhana - Academy Proceedings in Engineering Sciences (Springer Publications) , ISSN (print version) : 0256-2499 ISSN(electronic version) : 0973-7677 , Journal no.: 12046.

  • Biswas, S. S., Alam, B. and Doja, M. N., A Slight Adjustment of Dijkstra’s Algorithm for Solving SPP in Real Time Environment, Third International Conference on Computational Intelligence and Information Technology – CIIT 2013, Held in Mumbai, India., Published at International Conference on ComNet CIIT & ITC 2013 Proceedings (Elsevier Publication), pp: 256-259 ISBN: 978-81-910691-6-3.

  • Biswas, S. S., Alam, B. and Doja, M. N., An Algorithm For Extracting Intuitionistic Fuzzy Shortest Path in A Graph, Applied Computational Intelligence and Soft Computing, 2(2) 2012 (Hindawi Publishing Corporation), Article ID 970197, ISSN: 1687-9724 e-ISSN: 1687-9732, http://dx.doi.org/10.1155/2013/970197.

  • Biswas, S. S., Alam, B. and Doja, M. N., Fuzzy Shortest Path in A Directed Multigraph, European Journal of Scientific Research, 101(3) 2013: pp 333-339, ISSN 1450-216X / 1450-202X.

  • Biswas, S. S., Alam, B. and Doja, M. N., Generalization of Dijkstra’s Algorithm For Extraction of Shortest Paths in Directed Multigraphs, Journal of Computer Science, 9(3) 2013: pp 377-382, ISSN 1549-3636, doi: 10.3844/jcssp.2013.377.382.

  • Biswas, S. S., Alam, B. and Doja, M. N., A Theoretical Characterization of The Data Structure ‘Multigraph’ , Journal of Contemporary Applied Mathematics , 2(2) 2012, pp 88-106 (Institute of Mathematics and Mechanics NAS of Azerbaijan) , ISSN: 2222-5498.

  • Blue,M., Bush,B. and Puckett,J., Unified approach to fuzzy graph problems, Fuzzy Sets and Systems,125 (2002) 355–368.

  • Bollobas, Bela. ; Modern Graph Theory, Springer; 2002.

  • Boulmakoul, A., Generalized Path-Finding Algorithms on Semi rings and the Fuzzy Shortest Path Problem, Journal of Computational and Applied Mathematics, 162 (2004) 263-272.

  • Chris Cornelis, Peter De Kesel, Etienne E. Kerre, Shortest Paths in Fuzzy Weighted Graphs, International Journal Of Intelligent Systems, 19(2004) 1051–1068.

  • Chuang T.N, Kung J.Y, The fuzzy shortest path length and the corresponding shortest path in a network, Computers and Operations Research 32(2005), 1409–1428.

  • Chu, T.C. and Tsao,C.T., Ranking fuzzy numbers with an area between the centroid point and original point, Comput. Math. Appl. 43 (2002) 111–117.

  • Chuang, T.N. and Kung,J.Y., The fuzzy shortest path length and the corresponding shortest path in a network, Computers and Operations Research, 32(2005) 1409–1428.

  • Chuang, T.N. and Kung,J.Y., A new algorithm for the discrete fuzzy shortest path problem in a network, Appl. Math. Comput. 174 (2006) 1660–1668.

  • Cormen, Thomas H.; Leiserson, Charles E.; Rivest, Ronald L.; Stein, Clifford, Introduction to Algorithms, McGraw-Hill. 2001

  • Deng, Yong., Chen, Yuxin., Zhang, Yazuman., and Mahadevan, Sankaran., Fuzzy Dijkstra Algorithm for Shortest Path Problem under uncertain environment, Applied Soft Computing, 12(3) 2012, pp. 1231-1237.

  • Diestel, R., Graph Theory, Springer, 2000.

  • Dijkstra, E. W., A note on two problems in connexion with graphs, Numerische Mathematik, 1 (1959) 269–271.

  • Dubois,D. and Prade,H., Fuzzy Sets and Systems: Theory and Applications, Academic Press, New York, USA, 1980.

  • Dubois,D. and Prade,H., Ranking fuzzy numbers in the setting of possibility theory, Inform. Sci. 30 (1983) 183–224.

  • Dubois,D. and Prade,H., Operations on fuzzy numbers, International Journal of Systems Science, 9(6),pp.613-626,1978.

  • Dubois,D. and Prade,H., Additions of interactive fuzzy numbers, IEEE Transactions on Automatic Control, AC-26(4), 1981, 926-936.

  • Dubois, D. and Prade, H., “Fuzzy Numbers: An Overview”, in: J. Bezdek (ed.) Analysis of Fuzzy Information, CRC Press, Boca Raton, 2, pp. 3-39, 1988.

  • Elizabeth, S. and Sujatha, L., Fuzzy Shortest Path Problem Based on Level -Triangular LR Fuzzy Numbers, Advances in Fuzzy Systems, 2012 (2012), Article ID 646248, 6 pages doi: 10.1155/2012/646248

  • Klein, C.M., Fuzzy shortest paths, Fuzzy Sets and Systems, 39(1991), pp. 27–41.

  • Li,Y., Gen,M. and Ida,K., Solving fuzzy shortest path problems by neural networks, Computers and Industrial Engineering, 31 (1996), 861–865.

  • Lin,K. and Chen,M., The fuzzy shortest path problem and its most vital arcs, Fuzzy Sets and Systems, 58(3) (1994), 343–353.

  • Mahdavi, I., Tajdin, A., Nourifar, R., Hasanzade, R. and Amiri, N.M., Designing a new algorithm for the fuzzy shortest path problem in a network. Proceeding of the 37th International Conference on Computers and Industrial Engineering, 20(23), 2007, Alexandria, Egypt,2385-2392.

  • Nayeem,S.M.A. and Pal, M., Shortest path problem on a network with imprecise edge weight, Fuzzy Optim. Decis. Making 4 (2005) 293–312.

  • Okada,S. and Soper, T., A method for solving shortest path problem on the network with fuzzy arc lengths, Proc. 7th Internat. Fuzzy Systems Association World Congress, 3, 1997, pp. 189–194.

  • Okada,S. and Soper, T., A shortest path problem on a network with fuzzy arc lengths, Fuzzy Sets and Systems, 109(1)2000, pp. 129–140.

  • Okada,S., Fuzzy shortest path problems incorporating interactivity among paths, Fuzzy Sets and Systems, 142(3)2004, PP 335–357.

  • Okada, S. and Gen, M., Fuzzy shortest path problem, Computers and Industrial Engineering 27, (1994) 465–468.

  • Okada, S. and Gen, M., Order relation between intervals and its applications to shortest path problem, in: Proc. 15th Annual Conf. on Computers and Industrial Engineering, 25, 1993.

  • Okada, S. and Gen, M., Fuzzy shortest path problem, in: Proc. 16th Ann. Conf. on Computers and Industrial Engineering, 27, 1994.

  • Okada,S., Interactions among paths in fuzzy shortest path problems, Proceedings of the 9th International Fuzzy Systems Association World Congress (2001), 41-46.

  • Sengupta, A and Pal, T. K., Solving the shortest path problem with intervals arcs, Fuzzy Optim. Decis. Making, 5,(2006) 71–89.

  • Sujatha,L. and Sattanathan,R., Fuzzy shortest path problem based on triangular LR type fuzzy number using acceptability index, International Journal of Engineering and Technology, 6, pp. 575–578, 2009.

  • Sujatha,L. and Elizabeth,S., Fuzzy Shortest Path Problem Based on Similarity Degree, Applied Mathematical Sciences, 5, 2011, no. 66, 3263 – 3276.

  • Yao, J.S. and Lin, F.T., Fuzzy shortest-path network problems with uncertain edge weights, Journal of Information Science and Engineering, 19 (2003) 321–351.

  • Zadeh,L.A., Fuzzy sets, Information and Control, 8(1965) 338-353.

  • Zadeh, L.A. (2011). A Note on Z-numbers, Information Sciences. 181 pp 2923–2932.

  • Zadeh, L.A., Z-Numbers — a New Direction in the Analysis of Uncertain and Complex Systems, 7th IEEE International Conference on Digital Ecosystems and Technologies, July 24, 2013, Menlo Park.

  • Zadeh, L.A., The Concept of a Z-Number — a New Direction in Uncertain Computation, Lecture Note of Prof. Lotfi A. Zadeh in IRI 2011 on Aug 3, 2011, Las Vegas.


Abstract Views: 271

PDF Views: 3




  • Z-Dijkstra’s Algorithm to solve Shortest Path Problem in a Z-Graph

Abstract Views: 271  |  PDF Views: 3

Authors

Siddhartha Sankar Biswas
Department of Computer Science and Engineering, Jamia Hamdard University Hamdard Nagar, New Delhi – 110062, India

Abstract


In this paper the author introduces the notion of Z-weighted graph or Z-graph in Graph Theory, considers the Shortest Path Problem (SPP) in a Z-graph. The classical Dijkstra’s algorithm to find the shortest path in graphs  is not applicable to Z-graphs. Consequently the author proposes a new algorithm called by Z-Dijkstra's Algorithm with the philosophy of the classical Dijkstra's Algorithm to solve the SPP in a Z-graph.


Keywords


Z-Number, Z-Distance, Z-Weighted Graph, Z-Graph, Z-Dijkstra's.

References





DOI: https://doi.org/10.13005/ojcst%2F10.01.24