Finding the Shortest Path: Intuition
- We can define the solution to this problem inductively:
- DistanceTo(startNode) = 0
- For all nodes n directly reachable from startNode, DistanceTo(n) = 1
- For all nodes n reachable from some other set of nodes S,
- DistanceTo(n) = 1 + min(DistanceTo(m), m ∈ S)
From Intuition to Algorithm
- A map task receives a node n as a key, and (D, points-to) as its value
- D is the distance to the node from the start
- points-to is a list of nodes reachable from n
∀p ∈ points-to, emit (p, D+1)
- Reduce task gathers possible distances to a given p
and selects the minimum one
According to above-mentioned idea, A map task receives a node n as a key, and (D, points-to) as its value. It means that an "input" is a set of all reachable path from 'start' to each key.
Updated: My mis-understand. It doesn't need an set of all reachable path. See page 9 - "Adjacency Matrices".
- Another classic graph representation.
M[i][j]= '1' implies a link from node i to j.
- Naturally encapsulates iteration over nodes
| 1 2 3 4
--+----------
1 | 0 1 0 1
2 | 1 0 1 1
3 | 0 1 0 0
4 | 1 0 1 0
So, It can be represented as below:
1 (2, 4)
2 (1, 3, 4)
3 (2)
4 (1, 3)
Then, MR job will iterate 'hop' times(= maximum distance). Let's assume the start node is "1".
First MR job:
1 D=0, points-to=(2, 4)
2 D=inf, points-to=(1, 3, 4)
3 D=inf, points-to=(2)
4 D=inf, points-to=(1, 3)
Result: (2,1), (4,1)
Second MR job:
1 D=0, points-to=(2, 4)
2 D=1, points-to=(1, 3, 4)
3 D=inf, points-to=(2)
4 D=1, points-to=(1, 3)
Result: (2,1), (3,2), (4,1)
Here's my test code:
public class BFS {
static Map<String, ArrayList<String>> collect = new HashMap<String, ArrayList<String>>();
public static void main(String[] args) {
String[] value = {
// key | distance | points-to
"1|0|2;4",
"2|"+Integer.MAX_VALUE+"|1;3;4",
"3|"+Integer.MAX_VALUE+"|2",
"4|"+Integer.MAX_VALUE+"|1;3",
};
mapper(value);
reducer(collect.entrySet());
}
private static void mapper(String[] value) {
for (int i = 0; i < value.length; i++) {
String line = value[i].toString();
String[] keyVal = line.split("[|]");
String Key = keyVal[0];
String sDist = keyVal[1];
String[] links = null;
if (keyVal.length > 2) {
links = keyVal[2].split(";");
int Dist = Integer.parseInt(sDist);
if (Dist != Integer.MAX_VALUE)
Dist++;
for (int x = 0; x < links.length; x++) {
if (links[x] != "") {
ArrayList<String> list;
if (collect.containsKey(links[x])) {
list = collect.get(links[x]);
} else {
list = new ArrayList<String>();
}
list.add(Dist + "|");
collect.put(links[x], list);
}
}
ArrayList<String> list;
if (collect.containsKey(Key)) {
list = collect.get(Key);
} else {
list = new ArrayList<String>();
}
list.add(sDist + "|" + keyVal[2]);
collect.put(Key, list);
}
}
}
private static void reducer(Set<Entry<String, ArrayList<String>>> entrySet) {
for (Map.Entry<String, ArrayList<String>> e : entrySet) {
Iterator<String> values = e.getValue().iterator();
int minDist = Integer.MAX_VALUE;
String link_list = "";
while (values.hasNext()) {
String[] dist_links = values.next().toString().split("[|]");
if (dist_links.length > 1)
link_list = dist_links[1];
int dist = Integer.parseInt(dist_links[0]);
minDist = Math.min(minDist, dist);
}
System.out.println(e.getKey() + " - D " + (minDist + " | " + link_list));
}
}
}