Created
October 29, 2020 20:02
-
-
Save YusufAbdelaziz/db47bbef7f4895d6829544ec1ff3f32a to your computer and use it in GitHub Desktop.
Implementing Dijkstra from Grokking Algorithms
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| import java.util.*; | |
| public class Dijkstra { | |
| public static String findLowestNode(HashMap<String, Integer> costs, ArrayList<String> processedNodes) { | |
| String lowestNode = null; | |
| Integer lowestNodeVal = Integer.MAX_VALUE; | |
| for (String node : costs.keySet()) { | |
| if (lowestNodeVal > costs.get(node) && !processedNodes.contains(node)) { | |
| lowestNode = node; | |
| lowestNodeVal = costs.get(node); | |
| } | |
| } | |
| return lowestNode; | |
| } | |
| public static void main(String[] args) { | |
| // Graph HashMap which stores each node as key and a HashMap as value which consists of neighbours of that node | |
| // as key and their weight as value. | |
| HashMap<String, HashMap<String, Integer>> graph = new HashMap<>(); | |
| HashMap<String, Integer> start = new HashMap<>(); | |
| start.put("a", 6); | |
| start.put("b", 2); | |
| HashMap<String, Integer> b = new HashMap<>(); | |
| b.put("a", 3); | |
| b.put("fin", 5); | |
| HashMap<String, Integer> a = new HashMap<>(); | |
| a.put("fin", 1); | |
| HashMap<String, Integer> fin = new HashMap<>(); | |
| graph.put("start", start); | |
| graph.put("b", b); | |
| graph.put("a", a); | |
| graph.put("fin", fin); | |
| // Costs HashMap | |
| HashMap<String, Integer> costs = new HashMap<>(); | |
| costs.put("a", 6); | |
| costs.put("b", 2); | |
| costs.put("fin", Integer.MAX_VALUE); | |
| // Parents HashMap | |
| HashMap<String, String> parents = new HashMap<>(); | |
| parents.put("a", "start"); | |
| parents.put("b", "start"); | |
| parents.put("fin", null); | |
| ArrayList<String> processedNodes = new ArrayList<>(); | |
| String node = findLowestNode(costs, processedNodes); | |
| while (node != null) { | |
| int nodeCost = costs.get(node); | |
| var neighbours = graph.get(node).keySet(); | |
| for (String neighbour : neighbours) { | |
| var neighbourCost = graph.get(node).get(neighbour); | |
| var newCost = nodeCost + neighbourCost; | |
| if (newCost < costs.get(neighbour)) { | |
| costs.put(neighbour, newCost); | |
| parents.put(neighbour, node); | |
| } | |
| } | |
| processedNodes.add(node); | |
| node = findLowestNode(costs, processedNodes); | |
| } | |
| System.out.println(parents); | |
| } | |
| } |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment