作为一种重要的且具有代表性的数据结构,图通常可以用来描述不同领域的事物之间的繁杂关系。在信息化时代,快速增长的数据中的不确定性越来越普遍。如何对具有不确定性的图数据进行有效的处理,是一项巨大的工程。对于不确定图的研究,有很多想法都来源于确定图,因为确定图可以看作是边的存在概率为1的特殊不确定图。关于图的研究,在很多情况下都无法避开距离问题,但是由于不确定图自身的特性,使得其距离的计算变得更加复杂。在本文的研究中,主要以距离与效率问题作为切入点,对相关问题进行了研究。首先,对现有的关于距离的研究进行分析,指出在不确定图上进行相关研究所遇到的主要问题,其一是精确计算是NP难问题,其二是最短距离相同的路径之间在很多情况下都是不独立的。其次,在结合已有的关于距离的相关计算方法的基础上,提出了不确定图上可达距离的一种计算方法。当不确定图中给定的两点之间可达的概率超过0.5的时候,就用期望最短距离来度量它们之间的可达距离;相反,虽然它们之间不可达的概率比较大,但是只要最短距离不是无穷,说明他们之间是存在可达路径的,这时就用最大可能路径的长度来度量它们之间的可达距离。在现有的关于不确定图的距离的研究中,大都使用采样法作为核心处理方法,但是取样次数对结果的影响很大,而且结果也不一定固定。为了避开采样,提出了两种近似方法,分别是基于算术平均的近似方法与基于加权平均的近似方法。在算法复杂度方面,通过理论与实验相结合的方式验证了在可能世界中寻找可达的最短距离的时候,与最受欢迎的Dijsktra方法相比较而言,BFS方法的优势更加突出。最后,在将可达距离应用于kNN查询处理的时候,基本算法中仅考虑到了距离,而忽略了不确定图重要的特性,距离存在的几率。为了充分利用距离与概率的相互关系,引入了指数函数,巧妙地将两者融合在一起。在此基础上,加入侧重因子,使得那些可达距离与可达概率都非常相近的节点更易于区分。为了在大规模图上能加快算法的执行效率,节点剪裁的方法被用来缩减待查询的图的规模。最后的实验结果表明该方法具有较强的可操作性。