单源最短路径问题并行算法分析实验报告 一、 实验名称 单源最短路径问题并行算法分析
二、 实验目的 分析单源最短路径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)
