Advertisement
Guest User

Untitled

a guest
Apr 29th, 2017
57
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Java 1.64 KB | None | 0 0
  1.     public static void WikiDijkstras(Graph g, ArrayList<Vertex> targets, Vertex start){
  2.         Vertex initialNode = start;
  3.  
  4.         // Assign every node a distance value of infinity
  5.         Map<Vertex, Integer> tenativeDistance = new HashMap<>();
  6.         for(Vertex v : g.getTargets()){
  7.             tenativeDistance.put(v,Integer.MAX_VALUE);
  8.         }
  9.  
  10.         // Update start to 0
  11.         tenativeDistance.replace(start,0);
  12.  
  13.         // Mark all nodes except for start as unvisited
  14.         Set<Vertex> unvisitedNodes = new HashSet<>();
  15.         unvisitedNodes.addAll(g.getTargets());
  16.         unvisitedNodes.remove(start);
  17.         Vertex currentNode = initialNode;
  18.  
  19.         while(!unvisitedNodes.isEmpty()){
  20.             //Vertex currentNode = unvisitedNodes.iterator().next();
  21.             Iterator<Edge> edgeIterator = currentNode.edgeIterator();
  22.  
  23.             while(edgeIterator.hasNext()) {
  24.                 Edge edgeToUnvisitedNode = edgeIterator.next();
  25.                 if (unvisitedNodes.contains(edgeToUnvisitedNode.getV2()))
  26.                 {
  27.  
  28.                     int distanceToUnvisitedNode = edgeToUnvisitedNode.getWeight() + tenativeDistance.get(currentNode);
  29.                     // If the distance of the unvisited node is greater that the newly calculated distance, replace it
  30.                     if (tenativeDistance.get(edgeToUnvisitedNode.getV2()) > distanceToUnvisitedNode) {
  31.                         tenativeDistance.replace(edgeToUnvisitedNode.getV2(), distanceToUnvisitedNode);
  32.                         unvisitedNodes.remove(edgeToUnvisitedNode.getV2());
  33.                     }
  34.                 }
  35.             }
  36.  
  37.  
  38.  
  39.         }
  40.  
  41.     }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement