# 基于map-reduce的并行最短路径算法

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)

n1为起始点。首先标记它到自已的距离为0，然后算法把所有节点(n2~n5)加入到优先队列Q中，并标记n1到这些点的距离为∞。

Dijkstra算法关键的一点是优先队列Q（实际实现可以用数组），它保存了全局的从源点出发最近的结点。而map-reduce则无法做到这一点（其实也不是做不到，就是比较麻烦，需要用distributed cache）。

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]

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)

n1 --> 0 | n2: 6, n3: 15, n4:20

n2 --> ∞ | n3: 5, n4:8

n3 --> ∞ | n4:2

n4 -> ∞ |

Map：

n1 --> 0 | n2: 6, n3: 15, n4:20

n2 --> ∞ | n3: 5, n4:8

n3 --> ∞ | n4:2

n4 -> ∞ |

n2 --> 6
n3 --> 15

n4 --> 20

Reduce：

n1 --> 0 | n2: 6, n3: 15, n4:20

n2 --> 6 | n3: 5, n4:8

n3 --> 15 | n4:2

n4 --> 20 |

Map：

n1 --> 0 | n2: 6, n3: 15, n4:20

n2 --> 6 | n3: 5, n4:8

n3 --> 15 | n4:2

n4 --> 20 |

n3 --> 11
n4 --> 14

Reduce：

n1 --> 0 | n2: 6, n3: 15, n4:20

n2 --> 6 | n3: 5, n4:8

n3 --> 11 | n4:2

n4 --> 14 |

Map：

n1 --> 0 | n2: 6, n3: 15, n4:20

n2 --> 6 | n3: 5, n4:8

n3 --> 11 | n4:2

n4 --> 14 |

n4 --> 13
Reduce：

n1 --> 0 | n2: 6, n3: 15, n4:20

n2 --> 6 | n3: 5, n4:8

n3 --> 11 | n4:2

n4 --> 13 |

Map：

n1 --> 0 | n2: 6, n3: 15, n4:20

n2 --> 6 | n3: 5, n4:8

n3 --> 11 | n4:2

n4 --> 13 |

Reduce：

n1 --> 0 | n2: 6, n3: 15, n4:20

n2 --> 6 | n3: 5, n4:8

n3 --> 11 | n4:2

n4 --> 13 |

• 0

开心

• 0

板砖

• 0

感动

• 0

有用

• 0

疑问

• 0

难过

• 0

无聊

• 0

震惊