单源最短路径问题并行算法分析实验报告 一、 实验名称 单源最短路径问题并行算法分析。 二、 实验目的 分析单源最短路径Dijkstra 并行算法和MPI 源程序，并分析比较Dijkstra 并行算法和Moore 并行算法的性能。 三、 实验内容 1、分析单源最短路径Dijkstra 并行算法和MPI 源程序。 2、分析单源最短路径问题的Moore 并行算法，比较两种并行算法的性能。 四、 实验步骤 1、问题描述 单源最短路径问题即指：已知一个n 结点有向图G=(V,E)和边的权函数c(e)，求由G 中某指定结点v0 到其他各个结点的最短路径。这里还假定所有的权值都是正的。 2、比较串行Dijkstra 算法和Moore 算法 2.1、Dijkstra 算法基本思想 假定有一个待搜索顶点表VL，初始化时做：dist(s)←0；dist(i)←∞(i≠s)；VL←V。算法执行时，每次从VL（≠Φ ）中选取这样一个顶点u，它的dist(u)值最小。将选出的u 作为搜索顶点，若∈E，而且 dist(u)+w(u,v)∈E) ∧ (v∈VL) do 1 if dist(u)+w(u,v)∈E。若dist(u)+w(u,v)
