头歌 MapReduce 最优路径的算法。

最新推荐文章于 2026-01-04 19:40:08 发布

原创

最新推荐文章于 2026-01-04 19:40:08 发布 · 1.1k 阅读

18 ·

CC 4.0 BY-SA版权

文章标签：

#算法

任务描述
本关任务：根据相关知识内容实现 MapReduce 最优路径的算法。

相关知识
为了完成本关任务，你需要掌握：

最优路径概述；
Dijkstra 算法描述；
算法原理；
最优路径分析。
最优路径概述
最优路径算法是用于计算一个节点到其他所有节点的最短路径。主要特点是以起始点为中心向外层层扩展，直到扩展到终点为止。最优路径算法问题分为单源点最短路径和多源点最短路径:

单源点最短路径：指给定一个确定的源点，计算该点到其他顶点的最短距离;

多源点最短路径：指计算图中的所有顶点的到其他顶点的最短路径。

Dijkstra 算法描述
Dijkstra 算法（迪杰斯特拉算法）是由荷兰计算机科学家狄克斯特拉于 1959 年提出的，因此又叫狄克斯特拉算法。是从一个顶点到其余各顶点的最短路径算法，解决的是有向图中最短路径问题。

Dijkstra 采用路径长度递增的关系进行最短路径的计算。主要算法思想如下:

把顶点集合 V 分成两组: 1)S: 已求出的顶点的集合 (初始时只含有源点 VO); 2)V-S=T: 尚未确定的顶点集合。
将 T 中顶点按递增的次序加入到 S 中，保证:
从源点 VO 到 S 中其他各顶点的长度都不大于从 VO 到 T 中任何顶点的最短路径长度;
每个顶点对应一个距离值。
注意：
S 中顶点: 从 VO 到此顶点的长度；
T 中顶点: 从 VO 到此顶点的只包括 S 中顶点作中间顶点的最短路径长度。

算法原理
Dijkstra 算法伪代码如下：

Dijkstra(G,w, s)
d[s] ← 0
for all vertex v ∈ V do
d[v] ← ∞
Q ← {V }
while Q != ∅ do
u ←ExtractMin(Q)
for all vertex v ∈ u.AdjacencyList do
if d[v] > d[u] + w(u, v) then
d[v] ← d[u] + w(u, v)
Dijkstra 算法关键的一点是优先队列 Q，它保存了全局的从源点出发最近的结点。而 map-reduce 则无法做到这一点。

基于 map-reduce 的并行算法跟 Dijkstra 算法有点类似，它也基于 Dijkstra 的迭代思想，伪代码如下：

# Mapper类
class Mapper
method Map(nid n, node N)
d ← N.Distance
Emit(nid n,N) //Pass along graph
structure [1]
for all nodeid m ∈ N.AdjacencyList do
Emit(nid m, d+w) //Emit distances to
reachable nodes [2]
# Reducer类
class Reducer
method Reduce(nid m, [d1, d2, . . .])
dmin←∞
M ← ∅
for all d ∈ counts [d1, d2, . . .] do
if IsNode(d) then
M ← d //Recover graph
structure
else if d < dmin then //Look for shorter
distance
dmin ← d
M.Distance← dmin //Update shortest
distance
Emit(nid m, node M)
它每次迭代执行一个map-reduce job，并且只遍历一个节点。在 Map 中，它先输出这个节点的完整邻接节点数据，即 [1]。然后遍历该节点的邻接节点，并输出该节点 ID 及权重。在 Reduce 中，对当前节点 m，遍历 map 的输出权重，若比当前的路径值小，则更新。最后输出该节点的路径值及完整邻接节点数据，作为下一次迭代的输入。