A novel approach for calculating single-source shortest paths of weighted digraphs based on rough sets theory

Mingfeng Hua; Taihua Xu; Xibei Yang; Jianjun Chen; Jie Yang; Mingfeng Hua; Taihua Xu; Xibei Yang; Jianjun Chen; Jie Yang

doi:10.3934/mbe.2024116

Mathematical Biosciences and Engineering

2024, Volume 21, Issue 2: 2626-2645. doi: 10.3934/mbe.2024116

Previous Article Next Article

Research article

A novel approach for calculating single-source shortest paths of weighted digraphs based on rough sets theory

1.
School of Computer, Jiangsu University of Science and Technology, Zhenjiang 212100, China
2.
Key Laboratory of Oceanographic Big Data Mining & Application of Zhejiang Province, Zhejiang Ocean University, Zhoushan 316022, China
3.
School of Physics and Electronic Science, Zunyi Normal University, Zunyi 563002, China

Academic Editor: Haiyan Wang

Received: 21 December 2023 Revised: 04 January 2024 Accepted: 17 January 2024 Published: 19 January 2024

Calculating single-source shortest paths (SSSPs) rapidly and precisely from weighted digraphs is a crucial problem in graph theory. As a mathematical model of processing uncertain tasks, rough sets theory (RST) has been proven to possess the ability of investigating graph theory problems. Recently, some efficient RST approaches for discovering different subgraphs (e.g. strongly connected components) have been presented. This work was devoted to discovering SSSPs of weighted digraphs by aid of RST. First, SSSPs problem was probed by RST, which aimed at supporting the fundamental theory for taking RST approach to calculate SSSPs from weighted digraphs. Second, a heuristic search strategy was designed. The weights of edges can be served as heuristic information to optimize the search way of $ k $-step $ R $-related set, which is an RST operator. By using heuristic search strategy, some invalid searches can be avoided, thereby the efficiency of discovering SSSPs was promoted. Finally, the W3SP@R algorithm based on RST was presented to calculate SSSPs of weighted digraphs. Related experiments were implemented to verify the W3SP@R algorithm. The result exhibited that W3SP@R can precisely calculate SSSPs with competitive efficiency.
- rough sets theory,
- graph theory,
- single-source shortest paths,
- weighted digraphs,
- heuristic search strategy
Citation: Mingfeng Hua, Taihua Xu, Xibei Yang, Jianjun Chen, Jie Yang. A novel approach for calculating single-source shortest paths of weighted digraphs based on rough sets theory[J]. Mathematical Biosciences and Engineering, 2024, 21(2): 2626-2645. doi: 10.3934/mbe.2024116

Related Papers:

Abstract

Calculating single-source shortest paths (SSSPs) rapidly and precisely from weighted digraphs is a crucial problem in graph theory. As a mathematical model of processing uncertain tasks, rough sets theory (RST) has been proven to possess the ability of investigating graph theory problems. Recently, some efficient RST approaches for discovering different subgraphs (e.g. strongly connected components) have been presented. This work was devoted to discovering SSSPs of weighted digraphs by aid of RST. First, SSSPs problem was probed by RST, which aimed at supporting the fundamental theory for taking RST approach to calculate SSSPs from weighted digraphs. Second, a heuristic search strategy was designed. The weights of edges can be served as heuristic information to optimize the search way of $ k $-step $ R $-related set, which is an RST operator. By using heuristic search strategy, some invalid searches can be avoided, thereby the efficiency of discovering SSSPs was promoted. Finally, the W3SP@R algorithm based on RST was presented to calculate SSSPs of weighted digraphs. Related experiments were implemented to verify the W3SP@R algorithm. The result exhibited that W3SP@R can precisely calculate SSSPs with competitive efficiency.

References

[1]	R. M. Murekatete, T. Shirabe, An experimental analysis of least-cost path models on ordinal-scaled raster surfaces, Int. J. Geogr. Inf. Sci., 35 (2021), 1545–1569. https://doi.org/10.1080/13658816.2020.1753204 doi: 10.1080/13658816.2020.1753204
[2]	J. Y. Dong, J. Y. Zhang, Z. Chen, Autowave-competition neural network and its application to the single source shortest paths problem, Acta Phys. Sin., 56 (2007), 5013–5020. https://doi.org/10.7498/aps.56.5013 doi: 10.7498/aps.56.5013
[3]	M. Eshaghnezhad, F. Rahbarnia, S. Effati, A. Mansoori, An artificial neural network model to solve the fuzzy shortest path problem, Neural Process. Lett., 50 (2019), 1527–1548. https://doi.org/10.1007/s11063-018-9945-y doi: 10.1007/s11063-018-9945-y
[4]	Z. L. Xu, W. Huang, J. S. Wang, A wave time-varying neural network for solving the time-varying shortest path problem, Appl. Intell., 52 (2022), 8018–8037. https://doi.org/10.1007/s10489-021-02866-6 doi: 10.1007/s10489-021-02866-6
[5]	L. H. Lin, C. Z. Wu, L. Ma, A genetic algorithm for the fuzzy shortest path problem in a fuzzy network, Complex. Intell. Syst., 7 (2020), 225–234. https://doi.org/10.1007/s40747-020-00195-8 doi: 10.1007/s40747-020-00195-8
[6]	Y. L. Yang, D. D. Yan, J. H. Zhao, Optimal path selection approach for fuzzy reliable shortest path problem, J. Intell. Fuzzy Syst., 32 (2017), 197–205. https://doi.org/10.3233/JIFS-151393 doi: 10.3233/JIFS-151393
[7]	L. Zhang, J. M. Liu, B. Yu, G. Chen, A dynamic traffic assignment method based on connected transportation system, IEEE Access., 7 (2019), 65679–65692. https://doi.org/10.1109/ACCESS.2019.2915993 doi: 10.1109/ACCESS.2019.2915993
[8]	J. P. Liu, X. C. Kang, C. Dong, F. H. Zhang, Simulation of real-time path planning for large-scale transportation network using parallel computation, Intell. Autom. Soft Comput., 25 (2019), 65–77. https://doi.org/10.31209/2018.100000013 doi: 10.31209/2018.100000013
[9]	Q. Wei, G. M. Hu, C. Shen, Y. F. Yin, A fast method for shortest path cover identification in large complex networks, CMC-Comput. Mat. Contin., 63 (2020), 705–724.
[10]	G. Chen, G. H. Wen, X. H. Yu, Performance analysis of distributed short-path set based routing in complex networks, IEEE Trans. Circuits Syst. II-Express Briefs., 66 (2019), 1426–1430. https://doi.org/10.1109/TCSII.2018.2882515 doi: 10.1109/TCSII.2018.2882515
[11]	E. W. Dijkstra, A note on two problems in connexion with graphs, Numer. Math., 1 (1959), 269–271. https://doi.org/10.1007/BF01386390 doi: 10.1007/BF01386390
[12]	M. L. Fredman, R. E. Tarjan, Fibonacci heaps and their uses in improved network optimization algorithms, in Proceedings of the 25th Annual Symposium on Foundations of Computer Science, (1984), 338–346. https://doi.org/10.1109/SFCS.1984.715934
[13]	H. Arslan, M. Manguoglu, A hybrid single-source shortest path algorithm, Turk. J. Electr. Eng. Comput. Sci., 27 (2019), 2636–2647. https://doi.org/10.3906/elk-1901-23 doi: 10.3906/elk-1901-23
[14]	Sunita, D. Garg, Dynamizing Dijkstra: a solution to dynamic shortest path problem through retroactive priority queue, J. King Saud Univ.-Comput. Inf. Sci., 33 (2021), 364–373. https://doi.org/10.1016/j.jksuci.2018.03.003 doi: 10.1016/j.jksuci.2018.03.003
[15]	Z. Pawlak, Rough sets, Int. J. Comput. Inf. Sci., 11 (1982), 341–356. https://doi.org/10.1007/BF01001956 doi: 10.1007/BF01001956
[16]	G. Q. Wang, T. R. Li, P. F. Zhang, Q. Q. Huang, H. M. Chen, Double-local rough sets for efficient data mining, Inf. Sci., 571 (2021), 475–498. https://doi.org/10.1016/j.ins.2021.05.007 doi: 10.1016/j.ins.2021.05.007
[17]	X. B. Yang, S. C. Liang, H. L. Yu, S. Gao, Y. H. Qian, Pseudo-label neighborhood rough set: measures and attribute reductions, Int. J. Approx. Reason., 105 (2019), 112–129. https://doi.org/10.1016/j.ijar.2018.11.010 doi: 10.1016/j.ijar.2018.11.010
[18]	W. W. Yan, J. Ba, T. H. Xu, H. L. Yu, J. L. Shi, B. Han, Beam-influenced attribute selector for producing stable reduct, Mathematics, 10 (2022), 553. https://doi.org/10.3390/math10040553 doi: 10.3390/math10040553
[19]	J. Yang, G. Y. Wang, Q. H. Zhang, Y. H. Chen, T. H. Xu, Optimal granularity selection based on cost-sensitive sequential three-way decisions with rough fuzzy sets, Knowl.-Based Syst., 163 (2019), 131–144. https://doi.org/10.1016/j.knosys.2018.08.019 doi: 10.1016/j.knosys.2018.08.019
[20]	J. L. Yang, X. Y. Zhang, K. Y. Qin, Constructing robust fuzzy rough set models based on three-way decisions, Cogn. Comput., 14 (2022), 1955–1977. https://doi.org/10.1007/s12559-021-09863-4 doi: 10.1007/s12559-021-09863-4
[21]	J. Qian, X. Han, Y. Yu, C. H. Liu, Multi-granularity decision-theoretic rough sets based on the fuzzy T-equivalence relation with new strategies, J. Intell. Fuzzy Syst., 44 (2023), 5617–5631. https://doi.org/10.3233/JIFS-222910 doi: 10.3233/JIFS-222910
[22]	J. K. Chen, J. J. Li, Y. J. Lin, Computing connected components of simple undirected graphs based on generalized rough sets, Knowl.-Based Syst., 37 (2013), 80–85. https://doi.org/10.1016/j.knosys.2012.07.013 doi: 10.1016/j.knosys.2012.07.013
[23]	T. H. Xu, G. Y. Wang, Finding strongly connected components of simple digraphs based on generalized rough sets theory, Knowl.-Based Syst., 149 (2018), 88–98. https://doi.org/10.1016/j.knosys.2018.02.038 doi: 10.1016/j.knosys.2018.02.038
[24]	T. H. Xu, G. Y. Wang, J. Yang, Finding strongly connected components of simple digraphs based on granulation strategy, Int. J. Approx. Reason., 118 (2019), 64–78. https://doi.org/10.1016/j.ijar.2019.12.001 doi: 10.1016/j.ijar.2019.12.001
[25]	L. H. Guan, H. Wang, A heuristic approximation algorithm of minimum dominating set based on rough set theory, J. Comb. Optim., 44 (2022), 752–769. https://doi.org/10.1007/s10878-021-00834-x doi: 10.1007/s10878-021-00834-x
[26]	Q. Chen, T. H. Xu, J. J. Chen, Attribute reduction based on Lift and random sampling, Symmetry, 14 (2022), 1828. https://doi.org/10.3390/sym14091828 doi: 10.3390/sym14091828
[27]	Z. C. Gong, Y. X. Liu, T. H. Xu, P. X. Wang, X. B. Yang, Unsupervised attribute reduction: improving effectiveness and efficiency, Int. J. Mach. Learn. Cybern., 13 (2022), 3645–3662. https://doi.org/10.1007/s13042-022-01618-3 doi: 10.1007/s13042-022-01618-3
[28]	L. M. Fang, X. Y. Yun, C. C. Yin, W. P. Ding, L. Zhou, Z. Liu, et al., ANCS: automatic NXDomain classification system based on incremental fuzzy rough sets machine learning, IEEE Trans. Fuzzy Syst., 29 (2021), 742–756. https://doi.org/10.1109/TFUZZ.2020.2965872 doi: 10.1109/TFUZZ.2020.2965872
[29]	S. Vluymans, P. N. Mac, C. Cornelis, Y. Saeys, Weight selection strategies for ordered weighted average based fuzzy rough sets, Inf. Sci., 501 (2019), 155–171. https://doi.org/10.1016/j.ins.2019.05.085 doi: 10.1016/j.ins.2019.05.085
[30]	S. S. Zhang, K. Y. Liu, T. H. Xu, X. B. Yang, A. Zhang, A meta-heuristic feature selection algorithm combining random sampling accelerator and ensemble using data perturbation, Appl. Intell., 53 (2023), 29781–29798. https://doi.org/10.1007/s10489-023-05123-0 doi: 10.1007/s10489-023-05123-0
[31]	T. Y. Yin, H. M. Chen, Z. Yuan, J. H. Wan, K. Y. Liu, S. J. Horng, et al., A robust multilabel feature selection approach based on graph structure considering fuzzy dependency and feature interaction, IEEE Trans. Fuzzy Syst., 31 (2023), 4516–4528. https://doi.org/10.1109/TFUZZ.2023.3287193 doi: 10.1109/TFUZZ.2023.3287193
[32]	T. Y. Yin, H. M. Chen, J. H. Wan, P. F. Zhang, S. J. Horng, T. R. Li, Exploiting feature multi-correlations for multilabel feature selection in robust multi-neighborhood fuzzy $\beta$ covering space, Inf. Fusion., 104 (2024), 102150. https://doi.org/10.1016/j.inffus.2023.102150 doi: 10.1016/j.inffus.2023.102150
[33]	J. Bang-Jensen, G. Z. Gutin, Digraphs: Theory, Algorithms and Applications, 2nd edition, Springer Science & Business Media, London, 2009. https://doi.org/10.1007/978-1-84800-998-1
[34]	R. Tarjan, Depth-first search and linear graph algorithms, SIAM J. Comput., 1 (1972), 146–160. https://doi.org/10.1109/SWAT.1971.10 doi: 10.1109/SWAT.1971.10
[35]	Z. Gotthilf, M. Lewenstein, Improved algorithms for the k simple shortest paths and the replacement paths problems, Inf. Process. Lett., 109 (2009), 352–355. https://doi.org/10.1016/j.ipl.2008.12.015 doi: 10.1016/j.ipl.2008.12.015
[36]	T. A. Davis, Y. F. Hu, University of florida sparse matrix collection, ACM Trans. Math. Softw., 38 (2011), 734–747. https://doi.org/10.1145/2049662.2049663 doi: 10.1145/2049662.2049663

Reader Comments

Your name:*

Email:*
© 2024 the Author(s), licensee AIMS Press. This is an open access article distributed under the terms of the Creative Commons Attribution License (http://creativecommons.org/licenses/by/4.0)