Алгоритм Дейкстры на Java NllPointerException

266
11 апреля 2019, 22:10

Пытаюсь реализовать алгоритм Дейкстры для нахождения кратчайшего пути во взвешенном графе на 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");
    }
}
Answer 1

Проблема в том, что этот код HashMap<String, Integer> neightbors = graph.get(node);при передаче ему ключа "end" возвращает null, т.к. ранее Вы добавили туда значение graph.put("end", null); И, как следствие, когда Вы делаете foreach по null, у Вас вылетает NullPointerException.

READ ALSO
Как работает приведенный код [закрыт]

Как работает приведенный код [закрыт]

не могу понять как работает алгоритм считыванияНе понятно именно это :

246
PriorityQueue Java не работает - не работает сортировка

PriorityQueue Java не работает - не работает сортировка

У меня почему-то не работает Priority Queue А именно - я задаю comparator и начинаю вставлять элементы - а они вставляются не по порядку :( Судя по гуглу...

229
Таг form из Spring выдает исключение

Таг form из Spring выдает исключение

При попытке использовать элемент <springform:select ("http://wwwspringframework

226
Запись файла на память телефона

Запись файла на память телефона

Я хочу чтобы файлы сохранялись в отдельной папке приложения на одном уровне с папкой DownloadsSd карты нет

234