Dijkstra for MapReduce (1)

<math xmlns="http://www.w3.org/1998/Math/MathML">

  <mi>x</mi>

  <mo>,</mo>

  <mi>y</mi>

  <mo>&#x2208;<!-- ∈ --></mo>

  <mi>X</mi>

</math>

Dijkstra 최 단 경로 알고리즘 Hadoop 에서 MapReduce 로 실현 하 는 과정 을 연구 해 보 겠 습 니 다.우선 일반 Dijkstra 알고리즘 을 복습 해 보 세 요.
1) 데이터 구조 준비: 그래프, 정점 클래스 Vex 포함, 우선 대기 열 PQ:

package com.wlu.graph;



import java.io.BufferedReader;

import java.io.FileInputStream;

import java.io.IOException;

import java.io.InputStreamReader;

import java.util.HashMap;

import java.util.Map;

import java.util.Set;



public class Graph {



	private Map<Vex, Map<Vex, Integer>> Vlist;



	public Graph(Map<Vex, Map<Vex, Integer>> vvv) {

		Vlist = vvv;

	}



	public static Graph CreateFromFile(String fileName) throws IOException {

		BufferedReader br = new BufferedReader(new InputStreamReader(

				new FileInputStream(fileName)));



		Map<Vex, Map<Vex, Integer>> _Vlist = new HashMap<Vex, Map<Vex, Integer>>();

		Map<String, Vex> name2Vex = new HashMap<String, Vex>();



		for (String line = br.readLine(); line != null; line = br.readLine()) {

			String[] vs = line.split(" ");

			// 3 parts in the line

			String vsrc = vs[0];

			String vdes = vs[1];

			int wsd = Integer.parseInt(vs[2]);



			// add to the look up table

			Vex src = null;

			Vex dest = null;

			if (name2Vex.containsKey(vsrc)) {

				src = name2Vex.get(vsrc);

			} else {

				src = new Vex(vsrc);

				name2Vex.put(vsrc, src);

			}



			if (name2Vex.containsKey(vdes)) {

				dest = name2Vex.get(vdes);

			} else {

				dest = new Vex(vdes);

				name2Vex.put(vdes, dest);

			}



			// add the new dest node information

			// System.err.println(src.getName() + "  " + dest.getName() + "  " +

			// wsd);

			if (_Vlist.get(src) == null) {

				HashMap<Vex, Integer> DestMap = new HashMap<Vex, Integer>();

				DestMap.put(dest, wsd);

				_Vlist.put(src, DestMap);

			} else {

				_Vlist.get(src).put(dest, wsd);

			}

		}

		br.close();

		return new Graph(_Vlist);

	}



	public String toString() {

		String s = "";

		for (Vex src : Vlist.keySet()) {

			s += src.getName() + ": {";

			for (Vex des : Vlist.get(src).keySet()) {

				s += des.getName() + " (" + getw(src, des) + ")} {";

			}

			s = s.substring(0, s.length() - 1) + "
";

		}

		return s;

	}



	public int getw(Vex u, Vex v) {

		return Vlist.get(u).get(v);

	}



	public int getVexNum() {

		return Vlist.keySet().size();

	}



	public Set<Vex> getVexs() {

		return Vlist.keySet();

	}



	// get AdjacencyList of Vex u

	public Map<Vex, Integer> AdjacencyList(Vex u) {

		return Vlist.get(u);

	}



	public static void main(String args[]) throws IOException {

		Graph g = Graph.CreateFromFile("C:/tmp/test.txt");

		System.out.print(g.getVexNum() + "
" + g);

	}



}

package com.wlu.graph;



public class Vex {

	private String name;

	private int value;



	public Vex(String n, int v) {

		name = n;

		value = v;

	}



	public Vex(String n) {

		name = n;

		value = 0;

	}

	

	@Override

	public int hashCode(){

		return name.hashCode();

	}

	

	@Override

	public boolean equals(Object v){

		return name.compareTo(((Vex)v).name) == 0;

	}



	public String getName() {

		return name;

	}



	public void setName(String name) {

		this.name = name;

	}



	public int getValue() {

		return value;

	}



	public void setValue(int value) {

		this.value = value;

	}



}

 

package com.wlu.graph;



import java.util.ArrayList;

import java.util.List;



public class PQ {

	List<Vex> vlist = new ArrayList<Vex>();



	public void add(Vex v) {

		// remove the Vex if has exit

		for(int i = 0; i < vlist.size(); i++){

			if(vlist.get(i).getName().compareTo(v.getName()) == 0){

				vlist.remove(i);

				break;

			}

		}

		int i = 0;

		for (; i < vlist.size(); i++) {

			if (v.getValue() < vlist.get(i).getValue()) {

				break;

			}

		}

		// insert v to ith position

		List<Vex> vlist2 = new ArrayList<Vex>();

		int j = 0;

		for (; j < i; j++) {

			vlist2.add(vlist.get(j));

		}

		vlist2.add(v);

		for (int k = i; k < vlist.size(); k++) {

			vlist2.add(vlist.get(k));

		}



		vlist = vlist2;

	}



	public Vex pop() {

		if (vlist.size() == 0) {

			return null;

		}

		Vex v = vlist.get(0);

		vlist.remove(0);

		return v;

	}



	public boolean empty() {

		return vlist.size() == 0;

	}



	public void printPQ() {

		for (Vex v : vlist) {

			System.out.print(v.getName() + " (" + v.getValue() + ") ");

		}

		System.out.println();

	}



	public static void main(String args[]) {

		PQ pq = new PQ();

		pq.add(new Vex("a", 12));

		pq.add(new Vex("b", 2));

		pq.add(new Vex("c", 1));

		pq.add(new Vex("d", 123));

		pq.add(new Vex("e", 33));

		pq.add(new Vex("f", 4));

		pq.add(new Vex("g", 0));

		pq.add(new Vex("h", 21));

		pq.add(new Vex("i", 5));

		pq.add(new Vex("j", 3));

		pq.printPQ();

		System.out.println(pq.pop().getName());

		pq.printPQ();

	}



}

 2) Dijkstra 알고리즘

package com.wlu.dijkstra;



import java.io.IOException;

import java.util.HashMap;

import java.util.Map;



import com.wlu.graph.Graph;

import com.wlu.graph.PQ;

import com.wlu.graph.Vex;



public class DijkstraSeq {

	public Graph MST(Graph G, Vex s) {

		Map<Vex, Integer> d = new HashMap<Vex, Integer>();

		d.put(s, 0);

		PQ pq = new PQ();

		pq.add(s);



		for (Vex v : G.getVexs()) {

			if (!v.equals(s)) {

				d.put(v, Integer.MAX_VALUE);

			}

		}

		

		while(!pq.empty()){

			Vex u = pq.pop(); // ExtractMin

			for(Vex v : G.AdjacencyList(u).keySet()){

				if(d.get(v) > d.get(u) + G.getw(u, v)){

					d.put(v, d.get(u) + G.getw(u, v));

					v.setValue(d.get(u) + G.getw(u, v));

					pq.add(v);

				}

			}

		}

		

		for(Vex vv : d.keySet()){

			System.out.println(vv.getName() + "  " + vv.getValue());

		}

		return null;

	}

	

	public static void main(String args[]) throws IOException{

		Graph g = Graph.CreateFromFile("C:/tmp/test.txt");

		DijkstraSeq dijk = new DijkstraSeq();

		dijk.MST(g, new Vex("1"));

	}



}