Пытаюсь реализовать алгоритм Дейкстры для нахождения кратчайшего пути во взвешенном графе на java, при запуске пишет NullPointerException на 54 строке. Там где for (String n : neightbors.keySet()). Что не так? Вот код
import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
import java.util.Map.Entry;
public class Main {
private static final Integer infinity = Integer.MAX_VALUE - 10;//псевдобесконечность
private static HashMap<String, Integer> inner(String[] Keys, Integer[] Values) {
HashMap<String, Integer> innerMap = new HashMap<>();
for (int i = 0; i < Keys.length; i++) {
innerMap.put(Keys[i], Values[i]);
}
return innerMap;
}
private static void printInnerMap(Map<String, HashMap<String, Integer>> graph) {
for (Entry<String, HashMap<String, Integer>> o : graph.entrySet()) {
System.out.println(o);
}
}
private static String getLowestCost(Map<String, Integer> costs, List<String> processed) {
Integer min = Integer.MAX_VALUE - 1;
String minStr = null;
for (Entry<String, Integer> o : costs.entrySet()) {
if (o.getValue() < min && (!processed.contains(o.getKey()))) {
min = o.getValue();
minStr = o.getKey();
}
}
return minStr;
}
public static void main(String[] args) {
///////////////////Заготовка////////////////
Map<String, HashMap<String, Integer>> graph = new HashMap<>();//Мапа графа
/*Заполнение мапы графа через функцию, возвращающую HashMap, для вложенности*/
graph.put("start", inner(new String[] {"A", "B"}, new Integer[] {6, 2}));
graph.put("A", inner(new String[] {"end"}, new Integer[] {1}));
graph.put("B", inner(new String[] {"A", "end"}, new Integer[] {3, 5}));
graph.put("end", null);
Map<String, Integer> costs = new HashMap<>();//Мапа стоимостей
costs.put("A", 6);
costs.put("B", 2);
costs.put("end", infinity);
Map<String, String> parents = new HashMap<>();//Мапа родителей для обратного хода (кратчайший путь)
parents.put("A", "start");
parents.put("B", "start");
parents.put("end", null);
List<String> processed = new ArrayList<>();
//////////////////Алгоритм//////////////////////
String node = getLowestCost(costs, processed);
while (node != null) {
Integer cost = costs.get(node);
HashMap<String, Integer> neightbors = graph.get(node);
for (String n : neightbors.keySet()) {
Integer newCost = cost + neightbors.get(n);
if (newCost < costs.get(n)) {
costs.put(n, newCost);
parents.put(n, node);
}
}
processed.add(node);
node = getLowestCost(costs, processed);
}
System.out.println("BlaBlaBla");
}
}
Проблема в том, что этот код HashMap<String, Integer> neightbors = graph.get(node);при передаче ему ключа "end" возвращает null, т.к. ранее Вы добавили туда значение graph.put("end", null); И, как следствие, когда Вы делаете foreach по null, у Вас вылетает NullPointerException.
Апостиль в Лос-Анджелесе без лишних нервов и бумажной волокиты
Основные этапы разработки сайта для стоматологической клиники
Продвижение своими сайтами как стратегия роста и независимости