Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- import java.util.ArrayList;
- import java.util.Arrays;
- import java.util.Iterator;
- import java.util.List;
- /**
- * Computes shortest paths using Dijksta's algorithm modified for MapReduce.
- */
- public class Dijkstra {
- /**
- * Finds the shortest paths from the specified node to all other nodes.
- *
- * @param adjacencyMatrix the graph represented as an adjacency matrix
- * @param startNode the start node
- * @return an array containing the lengths of the shortest paths from
- * startNode to the node corresponding to the index
- */
- public static int[] findShortestPaths(final int[][] adjacencyMatrix, final int startNode) {
- Mapper mapper = new Mapper() {
- @Override
- public List<Pair> map(Object node, Object shortestPath) {
- List<Pair> list = new ArrayList<>();
- for (int i = 0; i <adjacencyMatrix.length ; i++) {
- int j = (int) node;
- list.add(new Pair(i,(int) shortestPath + adjacencyMatrix[i][j]));
- }
- return list;
- }
- };
- Reducer reducer = new Reducer() {
- @Override
- public List<Pair> reduce(Object o, List list) {
- int tmp = (int) list.get(0);
- for (int i = 1; i < list.size(); i++) {
- if(tmp > (int) list.get(i)){
- tmp = (int) list.get(i);
- }
- }
- List res = new ArrayList();
- res.add(new Pair(o,tmp));
- return res;
- }
- };
- //init
- SequentialMapReduce seq = new SequentialMapReduce(mapper,reducer);
- // ParallelMapReduce par = new ParallelMapReduce(mapper,reducer,4);
- List<Pair> list = new ArrayList<>();
- int shortestDistance = 99999;
- int shortestNode = startNode;
- int key = startNode;
- //init startlist
- for (int i = 0; i < adjacencyMatrix.length; i++) {
- list.add(new Pair(i,adjacencyMatrix[startNode][i]));
- }
- while(shortestNode != key || shortestNode == startNode ){
- shortestNode = key;
- //Compute the distance from startNode
- Iterable seqIt = seq.submit(list);
- Iterator it = seqIt.iterator();
- // Iterable parIt = par.submit(list);
- // Iterator it = parIt.iterator();
- //Retrieve node with shortest distance to startNode
- while (it.hasNext()) {
- Pair<Integer, Integer> pair = (Pair) it.next();
- if (pair.getValue() < shortestDistance) {
- shortestDistance = pair.getValue();
- key = pair.getKey();
- }
- }
- list.clear();
- for (int i = 0; i < adjacencyMatrix.length; i++) {
- list.add(new Pair(i, adjacencyMatrix[key][i]));
- }
- }
- int[] res = new int[list.size()];
- for (int r = 0; r < list.size(); r++) {
- res[r] = (int) list.get(r).getValue();
- }
- return res;
- }
- public static void main(final String[] args) {
- final int[][] adjacencyMatrix = {
- {0, 10, 1, 8, -1, -1},
- {10, 0, 7, -1, -1, 2},
- {1, 7, 0, 4, -1, 6},
- {8, -1, 4, 0, 6, -1},
- {-1, -1, -1, 6, 0, 3},
- {-1, 2, 6, -1, 3, 0}
- };
- final int[] shortest = findShortestPaths(adjacencyMatrix, 0);
- System.out.println(Arrays.toString(shortest));
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement