operaciones - Algoritmo de Dijkstra. Min heap como una cola de prioridad mínima

camino mas corto grafos java

Question

Estoy leyendo sobre el algoritmo de Dijkstra en CLRS, Tercera edición (pág. 662). Aquí hay una parte del libro que no entiendo:

Si el gráfico es lo suficientemente escaso, en particular, E = o(V^2/lg V) , podemos mejorar el algoritmo implementando la cola de prioridad mínima con un mínimo binario binario.

¿Por qué debería ser escasa la gráfica?

Aquí hay otra parte:

Cada operación de DECREASE-KEY lleva tiempo O(log V) , y aún hay como máximo E operaciones.

Supongamos que mi gráfica se parece a esto:

Me gustaría calcular la ruta más corta de 1 a 6 y utilizar el enfoque de min-heap. Así que primero que todo, agrego todos mis nodos a una cola de prioridad mínima. Después de construir un montón mínimo, el nodo mínimo es el nodo de origen (ya que su distancia a sí mismo es 0). Lo extraigo y actualizo las distancias de todos sus vecinos.

Luego, necesito llamar a decreaseKey en el nodo con la distancia más baja para hacer un nuevo mínimo del montón. ¿Pero cómo sé su índice en tiempo constante?

Nodo

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;
    }

}

Answer 1

¿Por qué debería ser escasa la gráfica?

El tiempo de ejecución del algoritmo de Dijkstra depende de la combinación de la estructura de datos subyacente y la forma del gráfico (bordes y vértices).

Por ejemplo, utilizar una lista enlazada requeriría tiempo O(V²) , es decir, solo depende del número de vértices. Usar un montón requeriría O((V + E) log V) , es decir, depende tanto del número de vértices como del número de bordes.

Si su E es lo suficientemente más pequeña en comparación con V (como en E << V² / logV ), usar Heap se vuelve más eficiente.

Luego, necesito llamar a decreaseKey en el nodo con la distancia más baja para hacer un nuevo mínimo del montón. ¿Pero cómo sé su índice en tiempo constante?

Si está utilizando un montón binario, entonces extractMin siempre se ejecuta en tiempo O(log V) y le da el nodo con la distancia más baja (también conocida como clave).

Por ejemplo, si está implementando el binario min-heap como una matriz H , entonces el primer elemento de la matriz H[1] (por convención, contamos desde 1 ) siempre será el elemento con la distancia más baja, por lo que encontrarlo Sólo toma O(1) .

Sin embargo, después de cada extractMin , insert o decreaseKey extractMin , tendrá que ejecutar swim o sink para restaurar la condición de almacenamiento dinámico y, en consecuencia, mover el nodo de menor distancia hacia la parte superior. Esto toma O(log V) .

Lo que también desea hacer es mantener una asignación entre las claves en el montón y los vértices, como se menciona en el libro: "asegúrese de que los vértices y los elementos correspondientes del montón mantengan los identificadores entre sí" (se explica brevemente en la sección 6.5).

Answer 2

Supongamos que su gráfica consiste de vértices (Nodo) en su caso, tiene 7 (0 -> 6) y bordes. Estos están representados por el siguiente modelo:

Modelo de nodo:

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;
        }

}

Y los bordes estarán presentes por este modelo: 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;
        }


}

El gráfico (nodos + bordes) estará presente en esta clase: Gráfico

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;
        }



}

Esta es una implementación simple del algoritmo de Dijkstra. No utiliza ninguna optimización de rendimiento:

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;
        }

}

Luego crea una clase de prueba y agrega los valores de tu gráfica:

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);
        }
}