import java.util.ArrayList; import java.util.HashMap; import java.util.List; import java.util.Map; /** * * @author reap.as.i.sow@gmail.com * */ public class Main { private static class DijkstraAlgorithm { /////////////////////////////////////////////////////////////// MyGraph graph; Map<Integer, Boolean> processedVertices; Map<Integer, Integer> distanceFromStartVertice; Map<Integer, Integer> parentVertice; //////////////////////////////////////////////////////////////// public DijkstraAlgorithm() { } public void init(MyGraph graph) { this.graph = graph; processedVertices = new HashMap<Integer, Boolean>(); distanceFromStartVertice = new HashMap<Integer, Integer>(); parentVertice = new HashMap<Integer, Integer>(); } //////////////////////////////////////////////////////////////// public void run(int start) { int curVerticeIndex = start; distanceFromStartVertice.put(start, 0); while (true) { if (curVerticeIndex == -1) { break; } processedVertices.put(curVerticeIndex, true); List<Edge> edges = graph.getEdges(curVerticeIndex); for (Edge edge : edges) { Integer endVertex = edge.end; Integer weight = edge.weight; boolean needUpdate = false; if (distanceFromStartVertice.get(endVertex) == null) { needUpdate = true; } else { if (distanceFromStartVertice.get(endVertex) > distanceFromStartVertice.get(curVerticeIndex) + weight) { needUpdate = true; } } if (needUpdate) { distanceFromStartVertice.put(endVertex, distanceFromStartVertice.get(curVerticeIndex) + weight); parentVertice.put(endVertex, curVerticeIndex); } } curVerticeIndex = findNextProcessVertice(); } printResult(start); } private int findNextProcessVertice() { int shortestDistance = 10000; int nextVertice = -1; for (int i = 0; i < graph.vertices.size(); i++){ // between not processed vertices if (processedVertices.get(i) == null) { if (distanceFromStartVertice.get(i) == null) { continue; } else if (shortestDistance > distanceFromStartVertice.get(i)){ shortestDistance = distanceFromStartVertice.get(i); nextVertice = i; } } } return nextVertice; } public void printResult(int start) { System.out.println("###Distance From Start###"); for (Map.Entry<Integer, Integer> itr : distanceFromStartVertice.entrySet()) { System.out.println(itr.getKey() + " " + itr.getValue()); } System.out.println("###Path End Index to " + start + " ###"); Integer endIndex = graph.getVerticeNum() -1; while (endIndex != start) { System.out.println(endIndex + " -> " + parentVertice.get(endIndex)); endIndex = parentVertice.get(endIndex); if (endIndex == null) break; } } } private static class Vertice { int index; public Vertice(int index) { this.index = index; } } private static class Edge { public Edge(int start, int end, int weight) { this.start = start; this.end = end; this.weight = weight; } int start; int end; int weight; } private static class MyGraph { List<Vertice> vertices; List<Edge> edges; public MyGraph(int numVertice) { vertices = new ArrayList<Vertice>(); for (int i = 0; i < numVertice; i++) { vertices.add(new Vertice(i)); } edges= new ArrayList<Edge>(); } public int getVerticeNum() { return vertices.size(); } public void addEdge(Edge edge) { edges.add(edge); } public List<Edge> getEdges(int startVecticeIndex) { List<Edge> results = new ArrayList<Edge>(); for (Edge edge : edges) { if (edge.start == startVecticeIndex) { results.add(edge); } } return results; } } public static void main(String[] args) { MyGraph myGraph = new MyGraph(12); myGraph.addEdge(new Edge(0, 1, 5)); myGraph.addEdge(new Edge(0, 2, 8)); myGraph.addEdge(new Edge(0, 3, 3)); myGraph.addEdge(new Edge(1, 4, 3)); myGraph.addEdge(new Edge(2, 5, 6)); myGraph.addEdge(new Edge(3, 4, 2)); myGraph.addEdge(new Edge(3, 5, 7)); myGraph.addEdge(new Edge(4, 6, 3)); myGraph.addEdge(new Edge(4, 7, 4)); myGraph.addEdge(new Edge(5, 8, 2)); myGraph.addEdge(new Edge(6, 9, 4)); myGraph.addEdge(new Edge(7, 9, 2)); myGraph.addEdge(new Edge(8, 10, 1)); myGraph.addEdge(new Edge(9, 11, 7)); DijkstraAlgorithm algo = new DijkstraAlgorithm(); algo.init(myGraph); algo.run(0); } }
2016년 4월 7일 목요일
Dijkstra Algorithm By OOP Java
I upload OOP based Dijkstra algorithm source code written in Java.
피드 구독하기:
댓글 (Atom)
댓글 없음:
댓글 쓰기