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

Siddhartha Sankar Biswas

Department of Computer Science and Engineering Faculty of Engineering and Technology Jamia Hamdard University

Hamdard Nagar,  New Delhi – 110062, India

 

Corresponding author Email: ssbiswas1984@gmail.com

DOI : http://dx.doi.org/10.13005/ojcst/10.01.24

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

Copy the following to cite this article: Biswas S. S. Z-Dijkstra's Algorithm to solve Shortest Path Problem in a Z-Graph. Orient.J. Comp. Sci. and Technol;10(1)

Copy the following to cite this URL: Biswas S. S. Z-Dijkstra's Algorithm to solve Shortest Path Problem in a Z-Graph. Orient.J. Comp. Sci. and Technol;10(1). Available from: http://www.computerscijournal.org/?p=5000

Introduction

In graph theory, the Shortest Path Problem (SPP) is one of the most famous problems studied and being studied by researchers. The SPP is the problem of finding a path between two vertices (or nodes) in a digraph such that the sum of the weights of its constituent edges is minimized. Thus the core problem is to find the shortest path from a source vertex S to a single destination vertex D in a directed graph and to compute the corresponding min cost. Shortest Path problems (SPP) are among the fundamental problems studied in Computational Geometry, Graph Algorithms, Geographical Information Systems (GIS), Network Optimization etc. to list a few only out of many. Sometimes the network of a real life communication or transportation system can not be modeled into a graph but into a multigraph [5-15]. In such a case the standard algorithms of graph theory cannot be applied in SPP too. Biswas et. el. [5-15]  has done rigorous analysis of SPP in multigraphs. However, in this work we consider those networks which can be modeled into graphs.

The concept of crisp graphs is extended to define fuzzy graphs [4, 16] for soft computing using graph theoretic algorithms.  The Fuzzy Shortest Path Problem (FSPP) [18, 23, 25, 33-37,  39-48]  is a  generalization  of the classical SPP for applications in ill-defined environment and has been found important to many applications such as Communication or Transportation Network, Computational Geometry, Graph Algorithms, Geographical Information Systems (GIS), Network Optimization, etc. In traditional shortest path problems, the arc length of the network takes precise numbers, but in the real-world problem, the arc length may represent transportation time or cost which can be known only approximately due to vagueness of information, and hence it can be considered a fuzzy number or an intuitionistic fuzzy number. The nodes are well precise, but the data about the weights(costs) of the links are sometimes not available as crisp numbers, rather fuzzy numbers or intuitionistic fuzzy numbers or Z-numbers. Recently Zadeh has introduced the notion of Z-number [51-53], a new direction in soft-computing number theory. In our work here we use the theory of Z-numbers of Zadeh.

One of the first studies on fuzzy shortest path problem (FSPP) in graphs was done by Dubois and Prade [28]  and then by Klein [34].   Though the work of Dubois and Prade [28]  was a major break-through, but that paper lacked any practical interpretation as 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. 

According to their approach, the shortest path length can be obtained, but the corresponding path in the network may not exist.  This drawback of their method made it difficult for application in network problems. Klein [34] proposed a dynamic programming recursion-based fuzzy algorithm. Lin and Chen [36] found the fuzzy shortest path length in a network by means of a fuzzy linear programming approach. Okada and Soper [39-45] proposed a fuzzy algorithm, which was based on multiple-labelling methods to offer non-dominated paths to a decision maker. Chuang and Kung [20] proposed a fuzzy shortest path length procedure that can find a fuzzy shortest path length among all possible paths in a network. Yao and Lin [49] presented two new types of fuzzy shortest path network problems. The main results obtained from their studies were that the shortest path in the fuzzy sense corresponds to the actual paths in the network, and the fuzzy shortest path problem is an extension of the crisp case.  Nayeem and Pal [38] have proposed an algorithm based on the acceptability index introduced by Sengupta and Pal [46] which gives a single fuzzy shortest path or a guideline for choosing the best fuzzy shortest path according to the decision maker’s viewpoint. Thus, numerous papers have been published in different journals/books on the fuzzy shortest path problem (FSPP). 

In this work the authors introduces Z-graph and solves the SPP in a Z-graph by developing a new algorithm in the style of the famous Dijkstra’s Algorithm to make it applicable in much wider domains.

Preliminaries of Z-numbers

The Z-number is a new fuzzy-theoretic concept introduced by Prof. Zadeh [51-53] in 2011.  There are not much work reported so far in the literature about the theory of Z-numbers because of its recent birth and baby stage. But owing to its strong modeling it will surely take a huge role to the scientists and engineers of all the fields in the world.

In this section we reproduce this new concept of Zadeh from It extends the basic philosophy of Computing With Words (CWW) to include the perception of uncertainty of the information conveyed by a natural language statement. The Z-number thus, serves as a model of linguistic summarization of natural language statements, a technique to merge human-affective perspectives with CWW, and consequently can be envisaged to play a radical role in the domain of CWW-based system design and Natural Language Processing (NLP).

Z-number 

Decisions are based on information. To be useful, information must be reliable. Basically, the concept of a Z-number relates to the issue of reliability of information.

A Z-number Z is an ordered pair, having two components and hence can be expressed using the expression Z = (A, B). The first component, A, is a restriction (generalized constraint) on the values which a real-valued uncertain variable, X, is allowed to take. The second component, B, is a measure of reliability (certainty) of the first component. Typically, A and B are described in a natural language.

Thus a Z-number can be expressed as an ordered pair of fuzzy numbers denoted as  Z = (A, B). For simplicity,  in our work here A and B are assumed as triangular fuzzy numbers. Clearly Z-numbers can be used to model uncertain information in real world. For example, in risk analysis, the loss of severity of the fifth component is very low, with a confidence of very likely, which can be written as a Z-number as follows Z = (very low; very likely). Example of another type of Z-numbers are :

Z1  =  (about 45 minutes, very sure),   Z2  =  (about 30 minutes, sure).  

A Z-number Z = (A, B) is called to be a null Z-number denoted by 0z,  if both A and B are null fuzzy numbers.

Some Operation on Z-numbers 

Consider two Z-numbers Z1 and Z2 given by

Z1  =  (A1, B1)   and   Z2  =  (A2, B2)

where Ai and Bi are triangular fuzzy numbers.  

There are a number of methods (viz. [1], [2], [21], [29])  for ranking triangular fuzzy numbers. We follow the Centroid Method because of its simplicity and appropriateness in the philosophy of soft computing.

We say that Z1 is strongly greater than Z2 if  A1 > A2 and B1 > B2. Otherwise, We say that Z1 is weakly greater than Z2 if  A1 > A2.

Addition ⊕ of two Z-numbers Z1 and Z2  yields another Z-number Z3 given by

Z3  =  Z1 ⊕ Z2  =   (A1 + A2,  B1 + B2).

As mentioned by Zadeh, it is fact that computation with Z-numbers is an important generalization of computation with real numbers. In particular, the generality of Z-numbers opens the door to construction of better models of reality, especially in fields such as decision analysis, planning, risk assessment, economics and biomedicine.

Z-weighted graph  or  Z-graph

In this section we define Z-graph.  A Z-graph is basically a generalized concept of fuzzy graph. Consider the following graph (see Figure 1) where at least one of the weights is Z-number. This type of graph is called a Z-weighted graph or Z-graph (in short).

Figure 1: A transportation network as a Z-graph G.   Click here to View figure

 

In this Z-graph in Figure 1, the edge AB has the Z-weight the Z-number (Approx. 67 km, sure), the edge AC has the Z-weight the Z-number (Approx. 49 km, very sure), etc.  The z-number weight of an edge is also called the Z-distance between the corresponding two nodes.

Z-Dijkstra’s Algorithm  for SPP in a Z-graph

The Classical  Dijkstra’s algorithm [27] solves the single-source shortest path problems in a simple graph. In this section we develop a new algorithm called by  Z-Dijkstra’s Algorithm  (of the style of the classical famous Dijkstra’s algorithm)  to solve a SPP in a Z-graph.

Shortest path estimate of a vertex in a directed Z-graph

Consider a Z-weighted directed graph G = (V, E).  Z-shortest path estimate d[v] of any vertex v, where vertex v  is one of the neighboring vertices of the currently traversed vertex u , is the Z-distance between the vertex v   and   vertex u ,  added with the shortest Z-distance between the starting vertex  s  and vertex u , where s, u, v ∈ V[G].

d [v]   =    (shortest Z-distance between  s and  u ) ⊕  (Z-weight of  arc between  v and u ) This is shown below in Figure 2.

Figure 2:  d[v] in a Z-graph.  Click here to View figure

 

Relaxation of an arc  in  our proposed Z-Dijkstra’s Algorithm

For the relaxation process of an arc to happen, we must first initialize the graph along with its starting vertex s  and Z-shortest path estimate for each vertices of the graph G.

INITIALIZE-SINGLE-SOURCE(G, s)

FOR each vertex  v  ∈  V[G

d[v]  =  ∞

v.π   =   NIL

d[s]  =  0z

(Note :   We store  all predecessor nodes  of u  in the attribute  uπ.   Thus  s. is always Nil,  because sπ is the source node).

Now on the basis of this initialization process, Z-Dijkstra’s algorithm proceeds further and the process of relaxation of each arc begins. The sub-algorithm RELAX, plays the vital role to update d[v]  i.e. the Z-shortest distance value between the starting vertex s  and the vertex v   (which is neighbor of the current traversed vertex u, ∀ u, v ∈  V[G] )

The RELAX algorithm runs as shown below :

RELAX(u, v,  w)

IF  d[v]  >  d[u]   ⊕  w(u,v)

THEN  d[v] ← d[u] ⊕ w(u, v)

v.π←u

where,  w(u, v)  is the Z-weight of the arc from  vertex u  and vertex v,   and  v.π  denotes  the parent node of a vertex v,  ∀ v, v ∈  V[G].  This is shown below in the Figure 3.

Figure 3: Diagram showing how RELAX  algorithm works.   Click here to View figure

 

Z-Dijkstra’s algorithm solves the single-source shortest-path on a Z-weighted directed Z-graph   G = (V, E)  for the case in which all edge Z-weights are non-negative.  Z-Dijkstra’s algorithm maintains  a  set S  of vertices whose final Z-shortest path weights from the source vertex s has already been determined. The algorithm repeatedly selects the vertex   u ∈ V – S  with the minimum Z-shortest- path estimate, adds  u to S,  and relaxes all edges leaving  u.  Our proposed  algorithm is as follows:

Z-Dijkstra (G, W, S)

Initialize-Single-Source (G, s)

S←∅

Q←V[G]

While   Q ≠ ∅

Do   U ← Extract-Min(Q)

S ← S ∪ {U}

For   Each Vertex V ∈ Adj[U]

Do   Relax(U, V,  W)

Conclusion

Z-graph is a generalization of fuzzy graph. There are many real life problems of networks in communication systems,  transportation, circuit systems, etc.  which cannot be modeled into graphs but into fuzzy graphs or Z-graphs only.  The classical  Dijkstra’s algorithm [27] to find the shortest path in graphs  is not applicable to Z-graphs.  In this paper we have done slight adjustment in the classical famous Dijkstra’s algorithm to make it applicable to Z-graphs to find the Z-shortest path from a source vertex to a destination vertex. The modified algorithm is called as Z-Dijkstra’s algorithm.  The networks where the classical  Dijkstra’s algorithm fails  can now be dealt with the Z-Dijkstra’s algorithm for performing efficient and optimal communication/transportation in many cases.

References

1. Abbasbandy, Saeid, Ranking of fuzzy numbers, some recent and new formulas, IFSA-EUSFLAT, 2009, Page 642- 646.
2.  Abbasbandy, Saeid., Allahviranloo, T. and Saneifard, R., A Method for Ranking of Fuzzy Numbers using New Weighted Distance, Mathematical and Computational Applications, Vol. 16, No. 2, Page 359-369, 2011.
3.  Balakrishnan, V. K.; Graph Theory, McGraw-Hill; 1997.
4.  Bhutani,K.R.  and Rosenfeld,A.,  Fuzzy End Nodes in Fuzzy Graphs,  Information Sciences, Vol. 152 (2003) 323-326.
   CrossRef
5.  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) Vol.19 (3) 2013: pp 90-98, ISSN : 1310-4926
6.  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) , Vol. 279 2014, Pages 633-641, Print ISBN : 978-3-642-41673-6 , Online ISBN : 978-3-642-41674-3, doi: 10.1007/978-3-642-41674-3_91.
   CrossRef
7.  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, Vol.10 (4) 2013: pp 593-603, ISSN 1549-3636, doi: 10.3844/jcssp.2014.593.603.
   CrossRef
8.  Biswas, S. S., Alam, B. and Doja, M. N.,  Real Time Multigraphs For Communication Networks : An Intuitionistic Fuzzy Mathematical Model, Journal of Computer Science, Vol. 9 (7) 2013: pp 847-855, ISSN 1549-3636, doi: 10.3844/jcssp.2013.847.855.
   CrossRef
9.  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), Vol.5, 2013, Pages 114–119, doi: 10.1016/j.aasri.2013.10.066.
   CrossRef
10.  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.
11.  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.
12.  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 ,  Vol.2(2)  2012 (Hindawi Publishing Corporation), Article ID 970197,  ISSN: 1687-9724 e-ISSN: 1687-9732,  http://dx.doi.org/10.1155/2013/970197.
    CrossRef
13.  Biswas, S. S., Alam, B. and Doja, M. N.,  Fuzzy Shortest Path in A Directed Multigraph, European Journal of Scientific Research, Vol.101 (3) 2013: pp 333-339, ISSN 1450-216X / 1450-202X.
14.  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, Vol.9 (3) 2013: pp 377-382, ISSN 1549-3636, doi: 10.3844/jcssp.2013.377.382.
    CrossRef
15.  Biswas, S. S., Alam, B. and Doja, M. N.,  A Theoretical  Characterization of The Data Structure ‘Multigraph’ , Journal of Contemporary Applied Mathematics , Vol.2(2)  2012, pp 88-106  (Institute of Mathematics and Mechanics NAS of  Azerbaijan) , ISSN: 2222-5498.
16.  Blue,M.,  Bush,B. and  Puckett,J.,  Unified approach to fuzzy graph problems, Fuzzy Sets and Systems, Vol.125 (2002) 355–368.
    CrossRef
17.  Bollobas, Bela. ; Modern Graph Theory, Springer; 2002.
18.  Boulmakoul, A., Generalized Path-Finding Algorithms on Semi rings and the Fuzzy Shortest Path Problem, Journal of Computational and Applied Mathematics, Vol. 162 (2004) 263-272.
    CrossRef
19. Chris Cornelis, Peter De Kesel, Etienne E. Kerre,  Shortest Paths in Fuzzy Weighted Graphs, International Journal Of Intelligent Systems, Vol. 19 (2004) 1051–1068.
    CrossRef
20. Chuang T.N, Kung J.Y, The fuzzy shortest path length and the corresponding shortest path in a network, Computers and Operations Research  Vol.32(2005), 1409–1428.
    CrossRef
21. Chu, T.C.  and  Tsao,C.T.,  Ranking fuzzy numbers with an area between the centroid point and original point, Comput. Math. Appl. Vol.43 (2002)    111–117.
    CrossRef
22. 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.
    CrossRef
23. 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.
    CrossRef
24. Cormen, Thomas H.; Leiserson, Charles E.; Rivest, Ronald L.; Stein, Clifford, Introduction to Algorithms, McGraw-Hill. 2001
25.  Deng, Yong., Chen, Yuxin., Zhang, Yazuman., and Mahadevan, Sankaran., Fuzzy Dijkstra Algorithm for Shortest Path Problem under uncertain environment, Applied Soft Computing, Vol.12(3) 2012, pp. 1231-1237.
    CrossRef
26. Diestel, R., Graph Theory, Springer, 2000.
27. Dijkstra, E. W., A note on two problems in connexion with graphs, Numerische Mathematik, Vol.1 (1959) 269–271. 
    CrossRef
28. Dubois,D. and Prade,H.,   Fuzzy Sets and Systems: Theory and Applications, Academic Press, New York, USA, 1980.
    CrossRef
29. Dubois,D. and Prade,H.,   Ranking fuzzy numbers in the setting of possibility theory, Inform. Sci. 30 (1983) 183–224.
    CrossRef
30. Dubois,D. and Prade,H.,   Operations on fuzzy numbers,  International Journal of Systems Science, vol.9, no.6,pp.613-626,1978.
    CrossRef
31. Dubois,D. and Prade,H.,   Additions of interactive fuzzy numbers, IEEE Transactions on Automatic Control, Vol. AC-26, No.4 1981, 926-936.
32. Dubois, D. and Prade, H.,  “Fuzzy Numbers: An Overview”,  in: J. Bezdek (ed.) Analysis of Fuzzy Information, CRC Press, Boca Raton, 1988, Vol.2,  pp. 3-39.
33. Elizabeth, S. and Sujatha, L.,  Fuzzy Shortest Path Problem Based on Level -Triangular LR Fuzzy Numbers, Advances in Fuzzy Systems, Volume 2012 (2012), Article ID 646248, 6 pages   doi: 10.1155/2012/646248
    CrossRef
34. Klein, C.M., Fuzzy shortest paths, Fuzzy Sets and Systems, 39 (1991), pp. 27–41.
    CrossRef
35. Li,Y., Gen,M. and Ida,K., Solving fuzzy shortest path problems by neural networks, Computers and Industrial Engineering 31 (1996)861–865.
    CrossRef
36. Lin,K. and Chen,M.,  The fuzzy shortest path problem and its most vital arcs, Fuzzy Sets and Systems, 58(3) (1994), 343–353.
    CrossRef
37. 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, October 20-23, 2007, Alexandria, Egypt,2385-2392.
38. 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.
    CrossRef
39. 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, vol. 3, 1997, pp. 189–194.
40. 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.
    CrossRef
41. Okada,S., Fuzzy shortest path problems incorporating interactivity among paths, Fuzzy Sets and Systems, Vol.142(3)2004, PP 335–357.
42. Okada, S.  and Gen, M., Fuzzy shortest path problem, Computers and Industrial Engineering 27 (1994) 465–468.
    CrossRef
43. 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, Vol. 25, 1993.
    CrossRef
44. Okada, S.  and  Gen, M., Fuzzy shortest path problem, in: Proc. 16th Ann. Conf. on Computers and Industrial Engineering, Vol. 27, 1994.
    CrossRef
45. Okada,S., Interactions among paths in fuzzy shortest path problems, Proceedings of the 9th International Fuzzy Systems Association World Congress (2001), 41-46.
    CrossRef
46. Sengupta, A and Pal, T. K., Solving the shortest path problem with intervals arcs, Fuzzy Optim. Decis. Making (5) (2006) 71–89.
    CrossRef
47. Sujatha,L. and Sattanathan,R.,  Fuzzy shortest path problem based             on
48. triangular LR type fuzzy number using acceptability index, International Journal of Engineering and Technology, Vol. 6, pp. 575–578, 2009.
49. Sujatha,L. and Elizabeth,S.,  Fuzzy Shortest Path Problem Based on Similarity Degree, Applied Mathematical Sciences, Vol. 5, 2011, no. 66, 3263 – 3276.
50. Yao, J.S. and  Lin, F.T., Fuzzy shortest-path network problems with uncertain edge weights, Journal of Information Science and Engineering Vol.19 (2003) 321–351.
51. Zadeh,L.A.,  Fuzzy sets, Information and Control, 8(1965) 338-353.
    CrossRef
52. Zadeh, L.A.  (2011).  A Note on Z-numbers, Information Sciences.  Vol.181  pp  2923–2932.
    CrossRef
53. 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.
54. 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.

---

This work is licensed under a Creative Commons Attribution 4.0 International License.