在现实世界中，许多领域中的数据都可以用“图”来表示。与传统的关系数据相比，图数据有着更大的灵活性。而由于数据本身的不精确、获取数据的实验手段的局限等因素的影响，不确定性是广泛存在的，例如：蛋白质交互网络和社交网络等。以蛋白质交互网络为例，由于对蛋白质之间交互的检测不够精确，在蛋白质网络中通常认为交互是以一定概率存在的。本文研究了不确定图上的最短距离问题，提出了期望最短距离的概念，证明了该问题不存在多项式时间的算法。而为了解决该问题，本文使用了随机采样技术获取不确定图的一些可能世界，在每个可能世界上计算给定两个顶点有穷的最短距离，最后根据多次随机采样的结果计算出平均值作为期望最短距离的估计值。为提高计算效率，本文使用了过滤条件来加快随机采样。在此基础上，又提出了一种基于对称变量随机采样的近似算法，并证明了与直接随机采样相比，该方法在不增加时间开销的同时能减小采样方差。通过真实数据上的实验表明，本文提出的算法在时间开销和采样方差上均明显好于直接随机采样。最后，本文将期望最短距离应用到蛋白质复合体的补全和不确定图上的聚类两个现实应用中，并通过实验验证了使用期望最短距离的方法解决上述现实应用的有效性。