Views 
   PDF Download PDF Downloads: 1125

 Open Access -   Download full article: 

I-v Fuzzy Shortest Path in a Multigraph

Siddhartha Sankar Biswas

Department of Computer Science and Engineering Faculty of Engineering and Technology Jamia Hamdard University Hamdard Nagar,  New Delhi – 62,  INDIA.

 

Corresponding Author Email: ssbiswas1984@gmail.com

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

Article Publishing History
Article Received on :
Article Accepted on :
Article Published : 25 Mar 2017
Article Metrics
ABSTRACT:

In this research paper the author introduces the notion of i-v fuzzy multigraph. The classical Dijkstra’s algorithmic rule to search out the shortest path in graphs isn't applicable to fuzzy graph theory. Consequently the author proposes a brand new algorithmic rule referred to as by IVF-Dijkstra's algorithmic rule with the philosophy of the classical Dijkstra's formula to unravel the SPP in an i-v fuzzy multigraph

KEYWORDS: i-v fuzzy number; IVFSPA; IVF-Dijkstra's

Copy the following to cite this article:

Biswas S. S. I-v Fuzzy Shortest Path in a Multigraph. Orient.J. Comp. Sci. and Technol;10(2)


Copy the following to cite this URL:

Biswas S. S. I-v Fuzzy Shortest Path in a Multigraph. Orient.J. Comp. Sci. and Technol;10(2). Available from: http://www.computerscijournal.org/?p=5100


Introduction

The ‘Multigraph’ [3,11-13,15,21-32,39] is a generalized data structure of ‘graph’ where multiple links  might exist between a pair of nodes.  For example, in a data communication model such as in  Adhoc Network or MANET,  the multipath or multiroute features are very common.  Two neighboring routers in a network constellation may share multiple direct connections between them (instead of simply one), therefore as to scale back the bandwidth as compared if one association is employed. Many real world situations of communication network, transportation network, etc. can’t be sculptured into graphs, however are often well sculptured into multigraphs.  In many of these directed multigraphs, the weights of the arcs are not always crisp numbers or fuzzy numbers (FNs) [18] but interval-valued fuzzy numbers (i-v fuzzy numbers) [33-35]  depending upon the choice of the concerned decision makers. In this paper, we’ve considered multigraphs without any loops.

One of the first studies on fuzzy shortest path problem (FSPP) in graphs was done by Dubois and Prade [7]  and then by Klein [14].  However, few additional solutions to FSPP projected in [16, 36-38] are fascinating. although the work of Dubois and Prade [7] was a serious break-through, however that paper lacked any practical interpretation as though fuzzy shortest path is found, however still this might not really be any of the path within the corresponding network for which it had been found. however there’s no work reported within the existing literature on finding a fuzzy shortest path in a multigraph.  In this paper we solve the FSPP problem for a multigraph where the arc-weights are interval valued (i-v) fuzzy numbers [33-35]. We follow the conception of classical Dijkstra’s algorithmic rule that is applicable to graphs with crisp weights, and then extend this idea to directed multigraphs wherever the weights of the arcs are i-v fuzzy numbers [33-35].

Preliminaries

For details of the classical notion of fuzzy set theory of Zadeh [40],  one could see any good book on it.  The conception of i-v fuzzy numbers is of importance for quantifying associate degree ill-known amount. In our work here throughout, we use the basic operations like fuzzy addition ,  fuzzy subtraction Θ and  ‘ranking’ of  fuzzy numbers, etc.  Trivially, any crisp real number can be viewed as a fuzzy number and any fuzzy number can be viewed as an i-v fuzzy number There is no unique method for ranking n number of i-v fuzzy numbers.  But there are methods [1, 2, 5, 8, 17, 19, 20]  in soft computing for ranking fuzzy numbers.  Each technique has some advantages and disadvantages relying upon the properties of the appliance domains and therefore the problem statement  into account. However,  if A1, A2, A3,….,An  be n i-v fuzzy numbers ranked in fuzzy ascending order according to any pre determined technique  i.e.A1∠ A2∠   A3∠ then A1 and An  are known as severally the i-v fuzzy-min and i-v fuzzy-max of those n i-v fuzzy numbers.……. An,

In this section we present basic preliminaries of the  theory of multigraphs [3,11-13,15,21-32, 39]. A multigraph X  is an ordered pair (V, E)  which consists of two sets V and E,   where V or V(X)  is the set of vertices (or, nodes), and E or E(X) is the set of edges (or, arcs). Here, though multiple edges or arcs would possibly exist between any two vertices, however we tend to contemplate that no loop exists.  Multigraphs are basically of two catagories:  undirected  and  directed.  In an undirected multigraph the edge (i, j) and the edge (j, i), if exist, are clearly identical not like within the case of directed multigraph. For a latest algebraic study on the theory of multigraphs, the work [21-32] and also  [3, 11-13, 15, 39] may be seen.  Figure 1 illustrated below a directed multigraph X = (V, E), in which V = {G, H, I, J, K} and E = {GH1, GH2, GI, IG, GJ, IJ, JH, JK, IK, HK, KH}

Figure 1 :   A  directed multigraph  X

Figure 1: A directed multigraph  X

 

Click here to View figure

 

Any  multigraph  Y  =  (W, F)   is   referred as an  submultigraph  of  the multigraph X = (V, E)   iff 

W ⊆ V and F ⊆  E.   The Figure 2 illustrated below is a submultigraph H of the given multigraph G

shown in Figure 1. 

Figure 2 :   A submultigraph H  of the  directed multigraph G

Figure 2: A submultigraph H  of the  directed multigraph G



Click here to View figure

 

In many of the real world issues of networks, be it during a communication model or transportation model, the weights of the arcs aren’t invariably crisp but fuzzy numbers [18]. for instance, the Figure-3 below shows a public road transportation model for a somebody wherever the value parameter for traveling every arc are obtainable to him as an i-v fuzzy number.

Figure 3:   A directed multigraph G with i-v fuzzy weights of arcs.

Figure 3: A directed multigraph G with i-v fuzzy weights of arcs.



Click here to View figure

 

In this paper  we consider such type of real situations in directed multigraphs of communication systems or transportation systems and  develop a method to find an i-v fuzzy shortest path from a source node to a destination node. 

i-v Fuzzy Shortest Path  in a Directed Multigraph

The FSPP has been solved by various authors for graphs, but for a directed multigraph there is no attempt made so far in the literature for searching a fuzzy shortest path.  In our technique here, we tend to solve this FSPP for multigraphs wherever we tend to conjointly use the notion of Dijkstra’s algorithmic rule however with simple soft-computations.  We call our proposed algorithm by the name IVF-Dijkstra’s Algorithm.

For developing the IVF-Dijkstra’s Algorithm, first of all we need to define the terms :  i-v Fuzzy-Min-Weight arc-set,  i-v Fuzzy shortest path estimate (d[v])  of a vertex,  i-v Fuzzy relaxation of an arc, etc.  in the context of the multigraphs,  and  develop few subalgorithms.

i-v Fuzzy-Min Weight Arc-set  of a  Directed Multigraph

Consider a directed multigraph G where the arcs are of i-v fuzzy weights. Suppose that there are n number of arcs from the vertex u to the vertex v in G, where n is a non-negative integer. Let Wuv be the set whose elements are the arcs between vertex u and vertex v, but keyed & sorted in non-descending order by the value of their respective i-v fuzzy weights, using a suitable pre-decided ranking method of i-v fuzzy numbers.

∴      Wuv   =     {  (uv1 , w1uv),   (uv2 , w2uv),   (uv3 , w3uv), ….. , (uvn , wnuv)  }

where,   uvi is the arc-i  from vertex u  to  vertex v  and  wi is the i-v fuzzy weight of it,   for   i  =  1, 2, 3,..…., n.    If  two or more number of  i-v fuzzy weights are equal then they may appear at random at the corresponding place of non-descending array  with no loss of generality in our discussion.

If there is no confusion,  let us denote the multiset  { w1uv,   w2uv,  w3uv, ..….. ,wnuv }  also by the same name Wuv.   Let   wuv  be the  i-v fuzzy-min value of the multiset  Wuv = { w1uv,   w2uv,  w3uv, ..….. ,wnuv }.  Clearly,  wuv   =  w1uv  ,  as the multiset Wuv  is already sorted.

Then the set  W  =   { < (u,v), wuv > :  (u,v)  E }  is called the i-v fuzzy-min-weight arc-set of the multigraph G.   Suppose that  the subalgorithm   FMWA (G)  returns the i-v fuzzy-min-weight arc-set W.

v fuzzy Shortest path estimate d[v]  of a vertex v in a directed multigraph

Suppose that node s is that the source vertex and the presently traversed vertex is node u. There is no single value of weight for arc between vertex u and a neighbor vertex v, rather there are multiple value of weights as there are multiple arcs between vertex u and vertex v. Using the value of wuv  from the  i-v fuzzy-min weight multiset  w  of a  directed multigraph,   we can now find the  i-v fuzzy shortest path estimate   i.e.  d[v]   of any vertex v,  in a directed multigraph  as below :-

(i-v fuzzy shortest path estimate of vertex v)   =   (i-v fuzzy shortest path estimate of vertex u)  ( i-v fuzzy-min of all the i-v fuzzy weights corresponding to the arcs from the vertex u to the vertex v).

or,        d[v]   =   d[u] ⊕  wuv 

Figure 4 :  i-v fuzzy estimation procedure for d[v]

Figure 4:  i-v fuzzy estimation procedure for d[v]

 

Click here to View figure

 

i-v fuzzy Relaxation of an Arc

We extend the classical notion of relaxation to the case of i-v fuzzy weighted arcs.  By i-v fuzzy relaxation we shall mean here the relaxation process of an arc  whose weight is an i-v fuzzy number.  For this, first of all we initialize the multigraph  along with its starting vertex and i-v fuzzy shortest path estimate for each vertices of the multigraph G.   The following ‘I-V FUZZY-INITIALIZATION-SINGLE-SOURCE’ algorithm will do :

Fuzzy-Initialization-Single-Source (G, s)

  1. For each vertex  v  ∈  V[G]    
  2. d[v]  =  221Efdsa
  3. v.π   =   NIL
  4. d[s]  =  0

After the i-v fuzzy initialization, the process of i-v fuzzy relaxation of each arc begins. The concerned sub-algorithm I-V FUZZY-RELAX, plays the very important role to update d[v] .  i.e.   the  i-v fuzzy shortest traversed cost between the starting node s  and the node v (which is the neighbor of the presently traversed vertex u)

Fuzzy-Relax (u, v, W)

  1. IF  d[v]    d[u]   wuv
  2. THEN  d[v] ←  d[u]   wuv
  3. v.π ← u

where,  wuv∈ W  is the i-v fuzzy-min weight of the arcs from  vertex u  to vertex v,   and  v.π  denotes  the parent node of  vertex v.

Figure  5 :   Diagram showing how the I-V FUZZY-RELAX  algorithm works.

Figure 5: Diagram showing how the I-V FUZZY-RELAX  algorithm works

 
Click here to View figure

 

i-v fuzzy Shortest Path Algorithm (IVFSPA)  

In this section we now present our main algorithm to find single source i-v fuzzy shortest path in a directed multigraph. We name this I-v fuzzy Shortest Path Algorithm by the title IVFSPA.  In this algorithmic rule we tend to use the above subalgorithms, and additionally the subalgorithm EXTRACT-I-V FUZZY-MIN(Q)   that extracts the node u with minimum key by exploiting i-v fuzzy ranking technique and updates Q.

IVFSPA (G, s)

  1.  I-V FUZZY-INITIALIZATION-SINGLE-SOURCE (G, s)
  2. W ←  FMWA (G)
  3. S ← ∅
  4. Q ← V[G]
  5. WHILE   Q  ≠  ∅
  6. DO   u ← EXTRACT-I-V FUZZY-MIN (Q)
  7. S ← S ∪ {u}
  8. FOR   each vertex  v  ∈  Adj[u]
  9. DO  I-V FUZZYRELAX (u, v, W)

Example

Consider the following directed Multigraph G with i-v fuzzy weights of its arcs. We want to resolve the single-source i-v fuzzy shortest paths problem taking the vertex A as the source node and the vertex D as the destination node.

Figure 6 :  A directed multigraph G with i-v fuzzy weighted arcs.

Figure 6: A directed multigraph G with i-v fuzzy weighted arcs.



Click here to View figure

 

Formula

Conclusion

‘Multigraph’ is an important generalization of the mathematical model ‘graph’. There are many real life problems of network, transportation, communication, circuit systems, etc. which cannot be modeled into graphs but into multigraphs only [21-32]. In many of these directed multigraphs, the weights of the arcs are not always crisp or ordinary fuzzy but i-v fuzzy [33-35]. The FSPP has been solved for graph by several authors, but not for multigraphs. In this paper we consider the FSPP have developed a method to find i-v fuzzy shortest path from a source vertex to a destination vertex of a directed multigraph. It is expected that our proposed method and the algorithms for FSPP on multigraphs can play a vital role in many application areas of computer science, communication network, transportation systems, etc. in particular in those networks that can’t be sculptured into graphs however into multigraphs.

References

  1. Abbasbandy, Saeid, Ranking of fuzzy numbers, some recent and new formulas, IFSA-EUSFLAT, 2009, Page 642- 646.
  2. Allahviranloo, T., Abbasbandy, S. 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.
    CrossRef
  3. Balakrishnan, V. K.,   Graph Theory,  McGraw-Hill; 1997.
  4. Bollobas, Bela.,  Modern Graph Theory, Springer; 2002
  5. Dat, Luu Quoc, Yu, Vincent F. and Chou, Shuo-Yan, An Improved Ranking Method for Fuzzy Numbers Using Left and Right Indices, 2nd International Conference on Computer Design and Engineering, IPCSIT Vol 49, 2012, Page 89-94.
  6. Diestel, Reinhard.,   Graph Theory, Springer 2000
  7. Dubois,D. and Prade,H. , Fuzzy Sets and Systems, Academic Press, New York, 1980.
  8. Farhadinia, B.,  Ranking Fuzzy Numbers based on Lexicoograhical Ordering, World Academy of Science, Engineering and Technology, 2009, Page 1029-1032.
  9. Harary, Frank.,   Graph Theory, Addison Wesley Publishing Company, 1995
  10. Jenson P. and Barnes J.,  Network Flow Programming,  John Wiley & Sons,  New York,   1980
  11. J. Ivančo,  Decompositions of multigraphs into parts  with the same size, Discussiones Mathematicae Graph Theory 30(2)(2010), 335-347.
    CrossRef
  12. J. Ivančo, M. Meszka, Z. Skupień, Decompositions of multigraphs into parts with two edges, Discussiones Mathematicae Graph Theory 22(1)(2002), 113-121
    CrossRef
  13. K. Bryś, M. Kouider, Z. Lonc, M. Maheo, Decomposition of multigraphs, Discussiones Mathematicae Graph Theory 18(2)(1998), 225-232
    CrossRef
  14. Klein, Cerry M., Fuzzy Shortest Paths, Fuzzy Sets and Systems 39 (1991) 27-41.
    CrossRef
  15. Mariusz Meszka and Zdzislaw Skupien,  Decomposition of a Complete Multigraph into Almost Arbitrary Paths, Discussiones Mathematicae Graph Theory  32(2)(2012) 357–372.
    CrossRef
  16. Okada, S. and T. Soper.,  A Shortest Path Problem on a Network with Fuzzy Arc Lengths, Fuzzy Sets and Systems 109 (2000), 129–140.
    CrossRef
  17. Parandin,N. and Araghi, M.A. Fariborzi, Ranking of Fuzzy Numbers by Distance Method, Journal of Applied Mathematics, Islamic Azad University of Lahijan, Vol.5, No.19, 2008, Page 47-55.
  18. Ranjit Biswas,  Fuzzy Numbers Redefined,  Information,  Vol.15(4)(2012) 1369-1380.
  19. Rao, P. Phani Bushan, and  Shankar, N. Ravi,   Ranking Fuzzy Numbers with a Distance Method using Circumcenter of Centroids and an Index of Modality,  Advances in Fuzzy Systems, Volume 2011, Article ID 178308, page 1-7.
  20. Saneifard, R. and Ezzati, R., A New Approach for Ranking Fuzzy numbers with Continuous Weighted Quasi-Arithmatic Means, Mathematical sciences, Vol. 4, No. 2(2010), Page 143-158.
  21. Biswas, S. S., Alam, B. and Doja, M. N.,  A Theoretical Characterization of the Data Structure  ‘Multigraphs’,  Journal of Contemporary Applied Mathematics, Vol.2(2) December’2012, page 88-106.
  22. 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
  23. 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
  24. 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
  25. 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
  26. 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
  27. 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.
    CrossRef
  28. 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.
  29. 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.
  30. 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.
  31. 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
  32. 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.
  33. Biswas, R., On I-v fuzzy subgroups , Fundamenta Informatica, Vol. 26(1) (1996) 1-9.
  34. Biswas, R.,  Rosenfeld’s fuzzy subgroups with interval-valued membership functions, Fuzzy Sets  and  Systems :  An International Journal”,  Vol.63 (1994) 87-90.
  35. Biswas, R., I-v fuzzy relations and Sanchez’s approach for medical diagnosis, Fuzzy Sets  and  Systems :  An International Journal ”,  Vol.47 (1992) 35-38.
  36. Sujatha, L. and Elizabeth, Fuzzy Shortest Path Problem Based on Similarity Degree, Applied Mathematical Sciences, Vol. 5(66) 2011, Page 3263 – 3276.
  37. Yao, Jing-Shing and Lin, Feng-Tse,  Fuzzy Shortest-Path Network Problems With Uncertain Edge Weights,  Journal of Information Science and Engineering 19(2003), Page 329-351.
  38. Yu, Jing-Rung and Wei, Tzu-Hao, 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).
    CrossRef
  39. Zdzislaw Skupien, On Distance edge Coloring of a Cyclic Multigraph, Discussiones Mathematicae Graph Theory 19(1999) 251–252.
    CrossRef
  40. Zadeh, L.A.,  Fuzzy Sets, Inform. And Control, Vol.8(1965) 338-353.
    CrossRef

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