TY -非盟的杨Yajun AU - Li Zhongfei AU -王,鑫盟——胡,清华PY - 2019 DA - 2019/02/19 TI -发现与顶点的最短路径约束大图表SP - 8728245六世- 2019 AB -图是一个重要的复杂网络模型来描述各种实体之间的关系在现实应用中,包括知识图,社交网络和交通网络。最短路径查询是图上的一个重要问题，已经得到了很好的研究。本文研究了最短路径问题的一个特殊情况，即通过用户指定的一组顶点找到最短路径，这是NP-hard问题。现有的方法大多是计算给定顶点的所有排列，然后从这些排列中找出最短的一个。然而，当图的大小或给定的顶点集很大时，计算代价非常昂贵。本文首先提出了一种新的基于最佳优先搜索的精确启发式算法，然后给出了两种优化技术以提高算法的效率。此外，我们提出了一种多项式时间的近似启发式算法来解决大图上的这个问题。我们证明了我们的近似算法的比值界是3。在实际数据集上进行了大量的实验，验证了算法的有效性。 The experimental results validate that our algorithms always outperform the existing methods even though the size of graph or given set of vertices is large. SN - 1076-2787 UR - https://doi.org/10.1155/2019/8728245 DO - 10.1155/2019/8728245 JF - Complexity PB - Hindawi KW - ER -