Алгоритм Дейкстры. Минимальная куча в качестве очереди с минимальным приоритетом
Я читаю о алгоритме Дейкстры в CLRS, Third Edition (стр. 662). Вот часть из книги, которую я не понимаю:
Если граф достаточно разрежен - в частности, E = o(V^2/lg V) - мы можем улучшить алгоритм, выполнив очередь с минимальным приоритетом с двоичной мини-кучей.
Почему граф должен быть разреженным?
Вот еще одна часть:
Каждая операция DECREASE-KEY требует времени O(log V), и все еще есть не более E таких операций.
Предположим, что мой график выглядит следующим образом:
![От 1 до 6]()
Я хотел бы рассчитать кратчайший путь от 1 до 6 и использовать метод min-heap. Итак, во-первых, я добавляю все мои узлы в очередь с минимальным приоритетом. После создания минимальной кучи min node является источником node (поскольку его расстояние до себя равно 0). Я извлекаю его и обновляю расстояния всех своих соседей.
Затем мне нужно вызвать decreaseKey на node с самым низким расстоянием, чтобы создать новый минимум кучи. Но как я могу узнать его индекс в постоянное время?
Node
private static class Node implements Comparable<Node> {
final int key;
int distance = Integer.MAX_VALUE;
Node prev = null;
public Node(int key) {
this.key = key;
}
@Override
public int compareTo(Node o) {
if (distance < o.distance) {
return -1;
} else if (distance > o.distance) {
return 1;
} else {
return 0;
}
}
@Override
public String toString() {
return "key=" + key + " distance=" + distance;
}
@Override
public int hashCode() {
return key;
}
@Override
public boolean equals(Object obj) {
if (this == obj) {
return true;
}
if (!(obj instanceof Node)) {
return false;
}
Node other = (Node) obj;
return key == other.key;
}
}
MinPriorityQueue
public static class MinPriorityQueue {
private Node[] array;
private int heapSize;
public MinPriorityQueue(Node[] array) {
this.array = array;
this.heapSize = this.array.length;
}
public Node extractMin() {
Node temp = array[0];
swap(0, heapSize - 1, array);
heapSize--;
sink(0);
return temp;
}
public boolean isEmpty() {
return heapSize == 0;
}
public void buildMinHeap() {
for (int i = heapSize / 2 - 1; i >= 0; i--) {
sink(i);
}
}
public void decreaseKey(int index, Node key) {
if (key.compareTo(array[index]) >= 0) {
throw new IllegalArgumentException("the new key must be greater than the current key");
}
array[index] = key;
while (index > 0 && array[index].compareTo(array[parentIndex(index)]) < 0) {
swap(index, parentIndex(index), array);
index = parentIndex(index);
}
}
private int parentIndex(int index) {
return (index - 1) / 2;
}
private int left(int index) {
return 2 * index + 1;
}
private int right(int index) {
return 2 * index + 2;
}
private void sink(int index) {
int smallestIndex = index;
int left = left(index);
int right = right(index);
if (left < heapSize && array[left].compareTo(array[smallestIndex]) < 0) {
smallestIndex = left;
}
if (right < heapSize && array[right].compareTo(array[smallestIndex]) < 0) {
smallestIndex = right;
}
if (index != smallestIndex) {
swap(smallestIndex, index, array);
sink(smallestIndex);
}
}
public Node min() {
return array[0];
}
private void swap(int i, int j, Node[] array) {
Node temp = array[i];
array[i] = array[j];
array[j] = temp;
}
}
Ответы
Ответ 1
Почему граф должен быть разреженным?
Время работы алгоритма Дейкстры зависит от комбинации базовой структуры данных и формы графика (ребер и вершин).
Например, использование связанного списка потребует времени O(V²), т.е. зависит только от количества вершин.
Для использования кучи потребуется O((V + E) log V), то есть она зависит как от количества вершин, так и от количества ребер.
Если ваш E достаточно меньше по сравнению с V (как в E << V² / logV), то использование кучи становится более эффективным.
Затем мне нужно вызвать decreaseKey на node с самым низким расстоянием, чтобы создать новый минимум кучи. Но как я могу узнать его индекс в постоянное время?
Если вы используете двоичную кучу, тогда extractMin всегда работает в O(log V) времени и дает вам node с самым низким расстоянием (клавиша a.k.a.).
Например, если вы реализуете двоичную мини-кучу в виде массива H, тогда первый элемент массива H[1] (по соглашению мы будем считать от 1) всегда будет элементом с самое низкое расстояние, поэтому для его нахождения требуется только O(1).
Однако после каждого extractMin, insert или decreaseKey вам нужно запустить swim или sink, чтобы восстановить состояние кучи, и, следовательно, переместить наименьшее расстояние node вверх. Это занимает O(log V).
То, что вы также хотите сделать, это поддерживать сопоставление между ключами в куче и вершинах, как указано в книге: "убедитесь, что
вершины и соответствующие кучевые элементы поддерживают ручки друг к другу "(кратко обсуждается в разделе 6.5).
Ответ 2
Предположим, что ваш граф состоит из вершин (Node) в вашем случае у вас есть 7 (0 → 6) и ребра. Они представлены следующей моделью:
Node модель:
public class Vertex{
final private String id;
final private String name;
public Vertex(String id, String name) {
this.id = id;
this.name = name;
}
public String getId() {
return id;
}
public String getName() {
return name;
}
@Override
public int hashCode() {
final int prime = 31;
int result = 1;
result = prime * result + ((id == null) ? 0 : id.hashCode());
return result;
}
@Override
public boolean equals(Object obj) {
if (this == obj)
return true;
if (obj == null)
return false;
if (getClass() != obj.getClass())
return false;
Vertex other = (Vertex) obj;
if (id == null) {
if (other.id != null)
return false;
} else if (!id.equals(other.id))
return false;
return true;
}
@Override
public String toString() {
return name;
}
}
И ребра будут присутствовать в этой модели: Edge
public class Edge {
private final String id;
private final Vertex source;
private final Vertex destination;
private final int weight;
public Edge(String id, Vertex source, Vertex destination, int weight) {
this.id = id;
this.source = source;
this.destination = destination;
this.weight = weight;
}
public String getId() {
return id;
}
public Vertex getDestination() {
return destination;
}
public Vertex getSource() {
return source;
}
public int getWeight() {
return weight;
}
@Override
public String toString() {
return source + " " + destination;
}
}
Граф (узлы + ребра) будут присутствовать в этом классе: График
public class Graph {
private final List<Vertex> vertexes;
private final List<Edge> edges;
public Graph(List<Vertex> vertexes, List<Edge> edges) {
this.vertexes = vertexes;
this.edges = edges;
}
public List<Vertex> getVertexes() {
return vertexes;
}
public List<Edge> getEdges() {
return edges;
}
}
Это простая реализация алгоритма Дейкстры. Он не использует оптимизацию производительности:
public class DijkstraAlgorithm {
private final List<Vertex> nodes;
private final List<Edge> edges;
private Set<Vertex> settledNodes;
private Set<Vertex> unSettledNodes;
private Map<Vertex, Vertex> predecessors;
private Map<Vertex, Integer> distance;
public DijkstraAlgorithm(Graph graph) {
// create a copy of the array so that we can operate on this array
this.nodes = new ArrayList<Vertex>(graph.getVertexes());
this.edges = new ArrayList<Edge>(graph.getEdges());
}
public void execute(Vertex source) {
settledNodes = new HashSet<Vertex>();
unSettledNodes = new HashSet<Vertex>();
distance = new HashMap<Vertex, Integer>();
predecessors = new HashMap<Vertex, Vertex>();
distance.put(source, 0);
unSettledNodes.add(source);
while (unSettledNodes.size() > 0) {
Vertex node = getMinimum(unSettledNodes);
settledNodes.add(node);
unSettledNodes.remove(node);
findMinimalDistances(node);
}
}
private void findMinimalDistances(Vertex node) {
List<Vertex> adjacentNodes = getNeighbors(node);
for (Vertex target : adjacentNodes) {
if (getShortestDistance(target) > getShortestDistance(node)
+ getDistance(node, target)) {
distance.put(target, getShortestDistance(node)
+ getDistance(node, target));
predecessors.put(target, node);
unSettledNodes.add(target);
}
}
}
private int getDistance(Vertex node, Vertex target) {
for (Edge edge : edges) {
if (edge.getSource().equals(node)
&& edge.getDestination().equals(target)) {
return edge.getWeight();
}
}
throw new RuntimeException("Should not happen");
}
private List<Vertex> getNeighbors(Vertex node) {
List<Vertex> neighbors = new ArrayList<Vertex>();
for (Edge edge : edges) {
if (edge.getSource().equals(node)
&& !isSettled(edge.getDestination())) {
neighbors.add(edge.getDestination());
}
}
return neighbors;
}
private Vertex getMinimum(Set<Vertex> vertexes) {
Vertex minimum = null;
for (Vertex vertex : vertexes) {
if (minimum == null) {
minimum = vertex;
} else {
if (getShortestDistance(vertex) < getShortestDistance(minimum)) {
minimum = vertex;
}
}
}
return minimum;
}
private boolean isSettled(Vertex vertex) {
return settledNodes.contains(vertex);
}
private int getShortestDistance(Vertex destination) {
Integer d = distance.get(destination);
if (d == null) {
return Integer.MAX_VALUE;
} else {
return d;
}
}
/*
* This method returns the path from the source to the selected target and
* NULL if no path exists
*/
public LinkedList<Vertex> getPath(Vertex target) {
LinkedList<Vertex> path = new LinkedList<Vertex>();
Vertex step = target;
// check if a path exists
if (predecessors.get(step) == null) {
return null;
}
path.add(step);
while (predecessors.get(step) != null) {
step = predecessors.get(step);
path.add(step);
}
// Put it into the correct order
Collections.reverse(path);
return path;
}
}
Затем создайте тестовый класс и добавьте свои значения графика:
public class TestDijkstraAlgorithm {
private List<Vertex> nodes;
private List<Edge> edges;
@Test
public void testExcute() {
nodes = new ArrayList<Vertex>();
edges = new ArrayList<Edge>();
for (int i = 0; i < 11; i++) {
Vertex location = new Vertex("Node_" + i, "Node_" + i);
nodes.add(location);
}
addLane("Edge_0", 0, 1, 5);
addLane("Edge_1", 0, 2, 40);
addLane("Edge_2", 0, 3, 21);
addLane("Edge_3", 2, 3, 13);
addLane("Edge_4", 2, 4, 19);
addLane("Edge_5", 4, 5, 32);
addLane("Edge_6", 3, 5, 41);
addLane("Edge_7", 4, 6, 14);
addLane("Edge_8", 5, 6, 8);
// Lets check from location Loc_1 to Loc_10
Graph graph = new Graph(nodes, edges);
DijkstraAlgorithm dijkstra = new DijkstraAlgorithm(graph);
dijkstra.execute(nodes.get(0));
LinkedList<Vertex> path = dijkstra.getPath(nodes.get(10));
assertNotNull(path);
assertTrue(path.size() > 0);
for (Vertex vertex : path) {
System.out.println(vertex);
}
}
private void addLane(String laneId, int sourceLocNo, int destLocNo,
int duration) {
Edge lane = new Edge(laneId,nodes.get(sourceLocNo), nodes.get(destLocNo), duration );
edges.add(lane);
}
}
