<![CDATA[The top-k shortest path problem is a fundamental topic in graph theory and pathfinding applications. Traditional approaches focus solely on finding k paths with the least total cost or distance, often resulting in highly similar paths that offer limited flexibility for user selection. Moreover, real-world navigation demands often involve additional user preferences, such as specific points of interest or required amenities along the route. Motivated by this observation, this paper proposes an efficient framework for answering top-k diverse path search queries incorporating user-specified tag preferences. Specifically, given a source and destination node, a set of user-defined tags, and a similarity threshold, our method retrieves k shortest paths that not only satisfy the user's tag constraints but also maintain diversity by ensuring that the similarity among the retrieved paths remains below a given threshold. The proposed solution employs a two-phase approach: (1) preprocessing the graph structure to generate a tag-based matrix and shortest path data for efficient query processing, and (2) a hybrid search strategy that combines a modified Dijkstra’s algorithm and depth-first search with pruning based on tag satisfaction and diversity checking. Extensive experiments on synthetic road network datasets demonstrate that our method achieves significant improvements in query processing efficiency and provides a higher degree of path diversity compared to conventional approaches. Our contributions include the formal definition of the top-k diverse path search with tag preferences, the development of an efficient search framework, and comprehensive experimental validations. The results suggest that the proposed framework effectively balances path optimality, tag satisfaction, and diversity, enabling a more flexible and user-centric pathfinding system.]]>
Copyrights © 2025
