随着网络社交的快速普及，在线社交网站逐渐成为人们日常社交活动的主要载体，吸引了众多用户。而根据社交网络中用户间关系和其社交活动所抽取出的社交网络数据，比传统的数据更具有复杂性和多样性，引起了研究者们浓厚的兴趣，主要体现在:一、社交网络拥有规模巨大的用户群体，其节点数量达到数百万甚至千万级别以上，节点间关系的数量更是达到亿万级别;二、社交网络中的数据具有较强的动态性，人们的社交活动具有很强的随机性，时刻都会有新节点的加入和退出以及关系的产生和消亡;三、社交网络中的关系具有多样性，在不同的社交网络中，其关系的类型、强弱程度以及是否具有方向等特点都会有所不同。因此，在处理复杂的社交网络数据时，如何为其选择最佳的数据模型，如何合理地存储数据以及高效、准确地处理查询请求，是相关研究的重点方向，也是推动社交网络服务发展的主要动力。　　本文以社交网络中用户间的好友关系为基础，将其抽象成一张无向无权图，并建立模型。在此基础之上，探讨图数据中节点间最短路径查询的相关算法及优化策略。文章首先介绍了社交网络的相关概念和基础理论，为后续研究工作的展开做理论铺垫;然后对已有的图数据中节点间可达性和最短路径查询算法及其性能进行详细介绍，并在Sketch算法的基础上，对基于最短路径树的节点间最短路径查询算法提出了两个方面的改进:一、在查询时，使用双向多最短路径树联合搜索优化策略;二、在路标节点的选择策略方面，使用随机抽样的方法来寻找覆盖率较高的节点作为路标节点，以提升最短路径树的覆盖率，进而提高查询结果的准确度。该算法属于基于路标估计算法的范畴，但传统的基于路标算法只能得到一个距离的估计值，而使用最短路径树的算法可以在快速求出节点间最短路径估计距离的同时得到真实存在的节点序列，另一个优势在于最短路径树结构支持在运行时以较低的代价来进行节点和关系的实时插入和删除操作，具有较强的适应性和可扩展性。通过在真实社交网络数据集上的实验结果表明，该改进算法在查询的时间、空间复杂度和准确率上都有一定的提高;本文最后还将基于最短路径树的算法用在社交网络的实际应用之中，包括节点间最短路径求解、图和节点的分离指标估算以及基于距离的社交搜索排名等，并通过实验来对比估计结果和真实结果，验证了该算法在实际应用中的准确性和实用性。