|Table of Contents|

 Mathematical model and algorithm for shortest path
problem in fuzzy weighted network


Research Field:
Publishing date:


 Mathematical model and algorithm for shortest path
problem in fuzzy weighted network
 SUN Xiaojun
 Institute of Mathematics and Information Science Baoji University of Arts and SciencesBaoji 721013ShaanxiChina
TP 301.6
 The shortest path problem in fuzzy wejghted network is an important network optimization problem.In view of the shortest path problem in the fuzzy weighted network whose weight is triangular fuzzy number, the fuzzy linear programming model is converted into a classical linear programming model by using the weighted ranking of fuzzy number’s structured element, and an improved weight matrix method is proposed to solve the problem. The new algorithm correctness is proved and its effectiveness is illustrated by an example. In addition, the mathematical model and new algorithm in this paper are as effective as other fuzzy weighted network with other fuzzy number.


 [1] BELLMAN R.On a routing problem[J].Quarterly of Apllied Mathmatics,1958,16(1):87-90.
[2] DIJKSTRA E W.A note on two problems in connexion with graphs[J].Numerical Mathematics,1959,1(1):269-271.
[3] PALLOTTINO S.Shortest-path methods:Complexity,interrelations and new propositions [J].Networks,1984,14(14):257-267.
[4] THOURUP M.Undirected single-source shortest paths with positive integer weights in linear time[J].Journal of the ACM,1999,46(3):362-394.
[5] IBRAHIM M S,MACULAN N,MINNOUX M.A strong flow-based formulation for the shortest path problem in digraphs with negative cycles[J].International in Operational Research,2009,16(3):361-369.
[6] JOLAI F,GHANBARI A.Integrating data transformation techniques with Hopfield neural networks for solving travelling salesman problem[J].Expert Systems with Applications,2010,37(7):5331-5335.
[7] CHEN Biyu,LAM William H K,SUMALEE A,et al.Finding reliable shortest paths in road networks under uncertainty[J].Netwoks and Spatial Economics,2013,13(2):123-148.
[8] HAN Duhyun,KIM Yeongdae,LEE Juyong.Multiple-criterion shortest path algorithms for global path planning of unmanned combat vehicles[J].Computers & Industrial Engineering,2014,71(1):57-69.
[9] DUBOIS D,PRADE H.Systems of linear fuzzy constraints[J].Fuzzy Sets and Systems,1980,3(1):37-48.
[10] BORTOLAN G,DEGANI R.A review of some methods for ranking fuzzy subsets[J].Fuzzy Sets and Systems,1985,15(1):1-19.
[11] NAKAMURA K.Preference relations on a set of fuzzy uitilities as a basis for decision making[J].Fuzzy Sets and Systems,1986,20(2):147-162.
[12] LI R J,LEE E S.Ranking fuzzy numbers——A comparison[C]//Proc of NAFIPS Workshop,West Lafayette,1987:169-204.
[13] LEE E S,LI R J.Comparison of fuzzy numbers based on the probability measure of fuzzy events[J].Computers & Mathematics with Applications,1988,15(10):887-896.
[14] CHEN Shanhuo.Ranking fuzzy numbers with maximizing set and minimizing sets[J].Fuzzy Sets and Systems,1985,17(2):113-129.
[15] YUAN Yufei.Criteria for evaluating fuzzy ranking methods[J].Fuzzy Sets and Systems,1991,43(2):139-157.
[16] 郭嗣琮.模糊数比较与排序的结构元方法[J].系统工程理论与实践,2009,29(3):105-111.
GUO Sizong.Comparison and sequencing of fuzzy numbers based on the method of structured element[J].Systems Engineering-Theory& Practice,2009,29(3):105-111.
[17] 刘海涛,郭嗣琮.基于模糊结构元表述的模糊数排序[J].模糊系统与数学,2010,24(5):61-67.
LIU Haitao,GUO Sizong.Fuzzy number sequence based on the expression of fuzyy structured element[J].Fuzzy Systems and Mathematics,2010,24(5):61-67.
[18] 郭嗣琮.基于模糊结构元理论的模糊数学分析原理[M].沈阳:东北大学出版社,2004.
GUO Sizong.Principle of mathematical analysis based on structureed element[M].Shenyang:Northeast University Press,2004.
[19] 赵海坤,郭嗣琮,傅秀峰.证劵组合的模糊规划模型[J].模糊系统与数学,2010,24(6):104-109.
ZHAO Haikun,GUO Sizong,FU Xiufeng.Fuzzy programming model of portfolio investment[J].Fuzzy Systems and Mathematics,2010,24(6):104-109.
[20] 孙小军.基于模糊结构元的最小生成树问题的求解算法[J].小型微型计算机系统,2015,36(4):806-809.
SUN Xiaojun.Algorithm of minimum spanning tree problem based on fuzzy structured element[J].Journal of Chinese Computer Systems,2015,36(4):806-809.


Last Update: 2016-10-08