Generalized Path Optimization Problem for a Weighted Digraph over an Additively Idempotent Semiring


  • Junsheng Duan School of Sciences, Shanghai Institute of Technology, Shanghai, China
  • Dichen Hu School of Sciences, Shanghai Institute of Technology, Shanghai, China



Semiring, Path optimization, Digraph, Incline, Partial order


In this paper, a generalized path optimization problem for a weighted digraph (i.e., directed graph) over an additively idempotent semiring was considered. First, the conditions for power convergence of a matrix over an additively idempotent semiring were investigated. Then we proved that the path optimization problem is associated with powers of the adjacency matrix of the weighted digraph. The classical matrix power method for the shortest path problem on the min-plus algebra was generalized to the generalized path optimization problem. The proposed generalized path optimization model encompasses different path optimization problems, including the longest path problem, the shortest path problem, the maximum reliability path problem, and the maximum capacity path problem. Finally, for the four special cases, we illustrate the pictorial representations of the graphs with example data and the proposed method.


Fan ZT. Fuzzy Matrix Theory and Applications. Science Press, Beijing 2006.

Qiao Z and Yin J. Fuzzy deep medical diagnostic system: gray relation framework and the guiding functionalities for the professional sports club social responsibility. Journal of Medical Imaging and Health Informatics 2020; 10 (5): 1084- 1090.

Singh S and Ganie AH. Applications of picture fuzzy similarity measures in pattern recognition, clustering, and MADM. Expert Systems with Applications 2021; 168: Article No. 114264.

Du GL, Liang YH, Gao BY, Al-Otaibi S and Li D. A cognitive joint angle compensation system based on self-feedback fuzzy neural network with incremental learning. IEEE Transactions on Industrial Informatics 2021; 17 (4): 2928- 2937.

Zeng W, Xi Y, Yin Q and Guo P. Weighted dual hesitant fuzzy set and its application in group decision making. Neurocomputing, Available online 6 Nov. 2020.

Goyal RK and Kaushal S. Deriving crisp and consistent priorities for fuzzy AHP-based multicriteria systems using nonlinear constrained optimization. Fuzzy Optimization and Decision Making 2018; 17: 195-209.

Zhang Z, Zheng W, Lam HK, Wen S, Sun F and Xie P. Stability analysis and output feedback control for stochastic networked systems with multiple communication delays and nonlinearities using fuzzy control technique. Applied Mathematics and Computation 2020; 386: Article No. 125374.

Thomason MG. Convergence of powers of a fuzzy matrix. Journal of Mathematical Analysis and Applications 1977; 57 (2):476-480.

Fan ZT and Cheng QS. A survey on the powers of fuzzy matrices and FBAMs. International Journal of Computational Cognition 2004; 2 (2): 1-25.

Hashimoto H. Convergence of powers of a fuzzy transitive matrix. Fuzzy Sets and Systems 1983; 9 (1-3): 153-160.

Kim KH and Roush FW. Generalized fuzzy matrices. Fuzzy Sets and Systems 1980; 4 (3): 293-315.

Li JX. An upper bound on indices of finite fuzzy relations. Fuzzy Sets and Systems 1992; 49 (3): 317-321.

Cechlarova K. On the powers of matrices in Bottleneck/Fuzzy algebra. Linear Algebra and its Applications 1996; 246: 97- 111.

Tan Y. On the powers of matrices over a distributive lattice. Linear Algebra and its Applications 2001; 336 (1-3): 1-14.

Zhang KL. On the nilpotent matrices over D01-lattice. Fuzzy Sets and Systems 2001; 117 (3): 403-406.

Tan Y. On the eigenproblem of matrices over distributive lattices. Linear Algebra and its Applications. 2003, 374, 87- 106.

Wu Y, Wang J and Yang Y. Lattice-ordered effect algebras and L-algebras. Fuzzy Sets and Systems 2019, 369: 103-113.

Cao ZQ, Kim KH and Roush FW. Incline Algebra and Applications. John Wiley & Sons, New York 1984.

Han SC and Li HX. Indices and periods of incline matrices. Linear Algebra and its Applications 2004; 387: 143-165.

Duan JS. The transitive closure, convergence of powers and adjacency of generalized fuzzy matrices. Fuzzy Sets and Systems 2004; 145 (2): 301-311.

Duan JS. Invertible conditions for matrices over an incline. Advances in Mathematics 2006; 35: 285-288.

Duan JS, Guo AP, Zhao FX, Xu L and Tang WG. Standard bases of a vector space over a linearly ordered incline. Communications in Algebra 2011; 39 (4): 1404-1412,

Han SC and LI HX. Some conditions for matrices over an incline to be invertible and general linear group on an incline. Acta Mathematica Sinica 2005; 21 (5): 1093-1098.

Han SC and Li HX. Invertible incline matrices and Cramer's rule over inclines. Linear Algebra and its Applications 2004; 389:121-138.

Meenakshi A. Regular matrices over an incline. In: Bapat R, Kirkland S, Prasad K and Puntanen S (Eds). Combinatorial Matrix Theory and Generalized Inverses of Matrices. Springer, India 2013, 183-193.

Han SC and Li HX. The semigroup of incline Hall matrices. Linear Algebra and its Applications 2004; 390: 183-196.

Meenakshi AR and Banu PS. On regularity of incline matrices. International Journal of Algebra 2011; 5 (19): 909-924. .7013

Zhang LM, Qiao LS and Li Y. Invertible incline matrices and ranks of incline matrices. Journal of Shandong University (Natural Science) 2007; 42 (9): 122-126.

Meenakshi AR and Anbalagan S. On regular elements in an incline. International Journal of Mathematics and Mathematical Sciences 2010; 2010: 1-12.

Kim KH and Roush FW. Inclines and incline matrices: a survey. Linear Algebra and its Applications 2004; 379: 457- 473.

Kendziorra A and Zumbragel J. Finite simple additively idempotent semirings. Journal of Algebra 2013; 388: 43-64.

Gaubert S and Plus M. Methods and applications of (max,+) linear algebra. In: Reischuk R and Morvan M (Eds). STACS 1997, Lecture Notes in Computer Science, Vol. 1200. Springer, Berlin, Heidelberg 1997, 261-282.

Watanabe S, Fukuda A, Segawa E and Sato I. A walk on maxplus algebra. Linear Algebra and its Applications 2020; 598: 29-48.

Tan Y. On invertible matrices over antirings. Linear Algebra and its Applications 2007; 423 (2-3): 428-444.

Sergeev S. Max algebraic powers of irreducible matrices in the periodic regime: An application of cyclic classes. Linear Algebra and its Applications 2009; 431 (8): 1325-1339.

Mohindru P and Pereira R. Orderings on semirings and completely positive matrices. Linear & Multilinear Algebra 2016; 64 (5): 818-833.

Demetrescu C and Italiano GF. Dynamic shortest paths and transitive closure: Algorithmic techniques and data structures. Journal of Discrete Algorithms 2006; 4 (3): 353-383.

Demetrescu C and Italiano GF. Fully dynamic all pairs shortest paths with real edge weights. Journal of Computer and System Sciences 2006; 72 (5): 813-837.

Giudicianni C, Herrera M, Nardo AD, Oliva G and Scala A. The faster the better: On the shortest paths role for near real-time decision making of water utilities. Reliability Engineering & System Safety 2021; 212: Article No. 107589.

Likaj R, Shala A, Mehmetaj M, Hyseni P and Bajrami X. Application of graph theory to find optimal paths for the transportation problem. IFAC Proceedings Volumes 2013; 46 (8): 235-240.

Rusakov VA. Matrices, shortest paths, minimal cuts and Euclidian metric for undirected graphs. Procedia Computer Science 2018; 145: 444-447.

Rodriguez-Velazquez JA, Kamisalic A and Domingo-Ferrer J. On reliability indices of communication networks. Computers & Mathematics with Applications 2009; 58 (7): 1433-1440.

Asghari S and Azadi K. A reliable path between target users and clients in social networks using an inverted ant colony optimization algorithm. Karbala International Journal of Modern Science 2017; 3 (3): 143-152.

Keshavarz E and Khorram E. A fuzzy shortest path with the highest reliability. Journal of Computational and Applied Mathematics 2009; 230 (1): 204-212.

Lin MS and Ting CC. Computing the K-terminal reliability of directed path graphs. Information Processing Letters 2015; 115 (10): 773-778.

Zimmermann U. Linear and Combinatorial Optimization in Ordered Algebraic Structures, Annals of Discrete Mathematics 10. Elsevier, Netherlands 1981.

Gondran M and Minoux M. Graphs, Dioids and Semirings. Springer, New York 2008.

Abu-Bekr J, Chikalov I, Hussain S and Moshkov M. Sequential optimization of paths in directed graphs relative to different cost functions. Procedia Computer Science 2011; 4: 1272- 1277.

Li J, Sun P and Hu Y. Traffic modeling and optimization in datacenters with graph neural network. Computer Networks 2020; 181: Article No. 107528.

Gould V, Johnson M and Naz M. Matrix semigroups over semirings. International Journal of Algebra and Computation. 2020; 30 (2): 267-337.

Araujo J, Campos VA, Maia AK, Sau I and Silva A. On the complexity of finding internally vertex-disjoint long directed paths. Algorithmica 2020; 82 (6): 1616-1639.

Liu XJ, Machado RA and Milenkovic O. Directed intersection representations and the information content of digraphs. IEEE Transactions on Information Theory 2021; 67 (1): 347-357.

Woods BD and Punnen AP. A class of exponential neighbourhoods for the quadratic travelling salesman problem. Journal of Combinatorial Optimization 2020; 40: 303- 332.

Magnouche Y and Martin S. Most vital vertices for the shortest s-t path problem: complexity and Branch-and-Cut algorithm. Optimization Letters 2020; 14 (8): 2039-2053.

Brinzei N and Aubry JF. Graphs models and algorithms for reliability assessment of coherent and non-coherent systems. Proceedings of the Institution of Mechanical Engineers, Part O: Journal of Risk and Reliability 2018; 232 (2): 201-215.

Kuperman O and Vardi G. Flow logic. Logical Methods in Computer Science 2019; 15 (4): Article No. 9.




How to Cite

Duan, J., & Hu, D. . (2020). Generalized Path Optimization Problem for a Weighted Digraph over an Additively Idempotent Semiring. Journal of Advances in Applied &Amp; Computational Mathematics, 7(1), 25–31.