Modify the Java code that runs Dijkstra\'s Algorithm to run Bellman Ford algorti

Question

 Modify the Java code that runs Dijkstra's Algorithm to run Bellman Ford algortihm.  public class Dijkstra {    public static DijkstraResult getShortestPaths(GeoGraph graph, GeoGraphNode start) {       HashMap<GeoGraphNode, Double> distances = new HashMap();       HashMap<GeoGraphNode, GeoGraphNode> previous = new HashMap();       ArrayList<GeoGraphNode> unvisited = new ArrayList();        for (GeoGraphNode node : graph.getNodes()) {          distances.put(node, (node == start)?0:Double.POSITIVE_INFINITY);          previous.put(node, null);          unvisited.add(node);       }        while (!unvisited.isEmpty()) {          GeoGraphNode current = getNodeWithMinimumDistance(start, distances, unvisited);          unvisited.remove(current);           for (GeoGraphNode adj: current.getConnections()) {             double alt = distances.get(current) + current.distanceTo(adj);             if (alt < distances.get(adj)) {                distances.put(adj, alt);                previous.put(adj, current);             }          }       }        DijkstraResult result = new DijkstraResult();       result.start = start;       result.previous = previous;       result.distances = distances;       return result;    }     public static GeoGraphNode getNodeWithMinimumDistance(GeoGraphNode start, HashMap<GeoGraphNode, Double> distances, ArrayList<GeoGraphNode> unvisited) {       GeoGraphNode best = null;        for (GeoGraphNode node: distances.keySet()) {          if ((best == null || distances.get(node) < distances.get(best)) && unvisited.contains(node)) {             best = node;          }       }        return best;    }     public static class DijkstraResult {       public GeoGraphNode start;       public HashMap<GeoGraphNode, Double> distances;       public HashMap<GeoGraphNode, GeoGraphNode> previous;        public ArrayList<GeoGraphNode> shortedPathTo(GeoGraphNode end) {           ArrayList<GeoGraphNode> path = new ArrayList<GeoGraphNode>();          path.add(end);          GeoGraphNode current = end;           while (current != start && previous.containsKey(current)) {             current = previous.get(current);             path.add(current);          }           Collections.reverse(path);           return path;       }    } } 

Explanation / Answer

Difference b/w Bellman ford and Dijkstra is of choosing current vertex whose neighbors has to be relaxed.
In Dijkstra, we choose current node as node with min distance matrix while in Bellman Ford we sequentially go vertex from 1 to N and try to relax all edges.

You can change getNodeWithMinDistance as to return any node and loop over all edges available and check for relaxtion condition (which is already there in code). Do it according to your GeoGraph class.

Related Questions

Navigate

• Browse (All)
• Browse M
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.