(Dijkstra's) Как эффективно найти ключ HashMap с минимальным значением, которое также находится в другом наборе?

Question

Я реализую алгоритм Дейкстры после этого псевдокода из Википедии , и я немного застрял в ускорении алгоритма.Я знаю, что могу использовать приоритетную очередь / кучу Fibre также для оптимальности, но я пока не совсем понимаю эти 2, и я хотел бы сначала начать с базовой реализации.

Одна из частейнаходит вершину с минимальным значением в dist, которая также находится в наборе Q (псевдокодом).

(я представлял свой направленный взвешенный граф с помощью LinkedHashMap<String, LinkedHashMap<String, Double>>, чтобы представить вершину по ее меткеи его значения - список вершин, с которыми он связан, с их весами.)

Вот как я реализовал эти 2:

// Vertex:Distance HashMap, i.e. dist.
HashMap<String, Double> dist = new HashMap<>();

    for (String v : this.adjacencyList.keySet()) {
        dist.put(v, Double.POSITIVE_INFINITY);
    }

dist.put(s, (double) 0);

Set<String> vertices = this.adjacencyList.keySet(); // This is Q.

while (!vertices.isEmpty()) {
!!! u ← vertex in Q with min dist[u] !!!

}

Часть !!! - это то, что я застрял"вкл.Я могу придумать, как это сделать методом грубой силы, то есть отсортировать dist, а затем найти наименьший ключ, который также находится в vertices, но это не похоже на разумный способ сделать это.Как мне решить эту проблему?

Поскольку HashMaps изначально не сортируются, мне придется каким-то образом отсортировать их, чтобы получить минимальное значение, верно?Первоначально это будет корневая вершина s, поскольку все остальное - бесконечность, но я не должен сортировать эту каждую итерацию.Разве я не должен использовать HashMap<String, Double> для dist, во-первых?

Что мне делать?Спасибо.

Answer 1

Почему вы не используете TreeSet или TreeMap с пользовательским компаратором?С TreeSet вы можете отсортировать все предметы (упакованные в POJO) по наименьшему расстоянию.Первое, что вы берете из набора при итерации, имеет наименьшее расстояние.

Вот пример такого набора:

class Elements {
    public Double distance;
    public String vertex; // Whatever you want
}

TreeSet<Elements> queue = new TreeSet<Elements>(new Comparator<Elements>() {
        @Override
        public int compare(Elements a, Elements b) {
            return a.distance.compareTo(b.distance);
        }
    }
);