2016년 4월 7일 목요일

Dijkstra Algorithm By OOP Java

I upload OOP based Dijkstra algorithm source code written in Java.
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);
 }
}

댓글 없음:

댓글 쓰기