Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- public static void WikiDijkstras(Graph g, ArrayList<Vertex> targets, Vertex start){
- Vertex initialNode = start;
- // Assign every node a distance value of infinity
- Map<Vertex, Integer> tenativeDistance = new HashMap<>();
- for(Vertex v : g.getTargets()){
- tenativeDistance.put(v,Integer.MAX_VALUE);
- }
- // Update start to 0
- tenativeDistance.replace(start,0);
- // Mark all nodes except for start as unvisited
- Set<Vertex> unvisitedNodes = new HashSet<>();
- unvisitedNodes.addAll(g.getTargets());
- unvisitedNodes.remove(start);
- Vertex currentNode = initialNode;
- while(!unvisitedNodes.isEmpty()){
- //Vertex currentNode = unvisitedNodes.iterator().next();
- Iterator<Edge> edgeIterator = currentNode.edgeIterator();
- while(edgeIterator.hasNext()) {
- Edge edgeToUnvisitedNode = edgeIterator.next();
- if (unvisitedNodes.contains(edgeToUnvisitedNode.getV2()))
- {
- int distanceToUnvisitedNode = edgeToUnvisitedNode.getWeight() + tenativeDistance.get(currentNode);
- // If the distance of the unvisited node is greater that the newly calculated distance, replace it
- if (tenativeDistance.get(edgeToUnvisitedNode.getV2()) > distanceToUnvisitedNode) {
- tenativeDistance.replace(edgeToUnvisitedNode.getV2(), distanceToUnvisitedNode);
- unvisitedNodes.remove(edgeToUnvisitedNode.getV2());
- }
- }
- }
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement