Grafos en Java: Algoritmo de Dijkstra

Los gráficos son una forma conveniente de almacenar ciertos tipos de datos. El concepto fue portado de las matemáticas y apropiado para las necesidades de la informática. Debido a...

Introducción

Los gráficos son una forma conveniente de almacenar ciertos tipos de datos. El concepto fue portado de las matemáticas y apropiado para las necesidades de la informática.

Debido al hecho de que muchas cosas se pueden representar como gráficos, el recorrido de gráficos se ha convertido en una tarea común, especialmente utilizada en ciencia de datos y aprendizaje automático.

¿Cómo funciona el algoritmo de Dijkstra?

El algoritmo de Dijkstra encuentra la ruta menos costosa en un gráfico ponderado entre nuestro nodo inicial y un nodo de destino, si existe tal ruta.

Al final del algoritmo, cuando llegamos al nodo de destino, podemos imprimir la ruta de menor costo retrocediendo desde el nodo de destino hasta el nodo de inicio. Más adelante en el artículo, veremos cómo podemos hacerlo al hacer un seguimiento de cómo llegamos a cada nodo.

Ya que esta vez usaremos gráficos ponderados, tendremos que crear una nueva clase GraphWeighted que tenga los métodos necesarios para manejarlos.

El algoritmo de Dijkstra funciona así:

  • Tenemos un grafo ponderado G con un conjunto de vértices (nodos) V y un conjunto de aristas E
  • También tenemos un nodo inicial llamado s, y establecemos la distancia entre s y s a 0
  • Marque la distancia entre s y todos los demás nodos como infinita, es decir, inicie el algoritmo como si no se pudiera acceder a ningún nodo desde el nodo s
  • Marque todos los nodos (excepto s) como no visitados, o marque s como visitados si todos los demás nodos ya están marcados como no visitados (que es el enfoque que usaremos)
  • Siempre que haya un nodo sin visitar, haga lo siguiente:
    • Find the node n that has the shortest distance from the starting node s
    • Mark n as visited
    • For every edge between n and m, where m is unvisited:
      • If cheapestPath(s,n) + cheapestPath(n,m) < cheapestPath(s,m), update the cheapest path between s and m to equal cheapestPath(s,n) + cheapestPath(n,m)

Esto puede parecer complicado, pero veamos un ejemplo que lo hace un poco más intuitivo:

Estamos buscando la ruta con el menor peso desde el nodo 0 hasta el nodo 6. Usaremos una matriz/tabla para representar mejor lo que sucede en el algoritmo.

Al principio, todos los datos que tenemos son la distancia entre el 0 y sus nodos vecinos.

El resto de las distancias se denotan como infinito positivo, es decir, no son accesibles desde ninguno de los nodos que hemos procesado hasta ahora (solo hemos procesado 0).

El siguiente paso es encontrar el nodo más cercano que aún no haya sido visitado y que podamos alcanzar desde uno de los nodos que hemos procesado. En nuestro caso, este es el nodo 1.

Ahora actualizaremos los valores de la ruta más corta si es necesario. Por ejemplo, ahora se puede acceder al nodo 3 desde el nodo 1.

También marcaremos 1 como visitado.

Nota: Tenemos que tener en cuenta cuánto "cuesta" llegar al nodo 1. Como nuestra posición inicial es 0 y cuesta 8 unidades ir del 0 al 1, tenemos que sumar ese 8 al costo total de "mover" de 1 a otro nodo. Es por eso que agregamos 8 (distancia de 0 a 1) + 3 (distancia de 1 a 3) = 11 a nuestra tabla, en lugar de solo 3.

Vemos que desde el nodo 1 podemos llegar a los nodos 2, 3 y 4.

  • Nodo 2 -> para ir de 1 a 2 cuesta 7 unidades, dado que el camino más corto de 0 a 1 cuesta 8 unidades, 8 + 7 es mayor que 11 (el camino más corto entre 0 y 2). Esto significa que no hemos encontrado una mejor ruta de 0 a 2 a través del nodo 1, por lo que no cambiamos nada.
  • Nodo 3 -> para ir del 1 al 3 cuesta 3 unidades, y dado que 3 era anteriormente inalcanzable, 8 + 3 es definitivamente mejor que infinito positivo, por lo que actualizamos la tabla en esa celda
  • Nodo 4 -> igual que con el nodo 3, anteriormente inalcanzable, por lo que también actualizamos la tabla para el nodo 4

El sombreado naranja oscuro nos ayuda a realizar un seguimiento de los nodos que hemos visitado, discutiremos por qué se agregó el tono naranja más claro más adelante.

Ahora podemos elegir entre el nodo 2 y el nodo 3, ya que ambos son "cerca" del nodo 0. Vamos con el nodo 3.

Los nodos accesibles no visitados desde el nodo 3 son los nodos 4 y 5:

  • Nodo 4 -> Cuesta 5 unidades pasar del nodo 3 al nodo 4, y 11 + 5 no es mejor que el valor anterior de 16 unidades que encontramos, por lo que no hay necesidad de actualizar
  • Nodo 5 -> cuesta 2 unidades ir del nodo 3 al nodo 5, y 11 + 2 es mejor que infinito positivo, así que actualizamos la tabla
  • Marcamos 3 como visitadas.

El siguiente nodo a considerar es el nodo 2, sin embargo, el único nodo accesible desde el nodo 2 es el nodo 4 y el valor que obtenemos (11 + 9 = 20) no es mejor que el valor anterior que encontramos (16), por lo que hacemos no hay cambios en nuestra tabla, aparte de marcar el nodo 2 como visitado.

El siguiente nodo accesible más cercano es 5, y los vecinos no visitados de 5 son 4 y 6.

  • Nodo 4 -> 13 + 1 es mejor que 16, por lo que se actualiza el valor
  • Nodo 6 -> 13 + 8 es mejor que infinito positivo, por lo que se actualiza el valor
  • Marcar 5 como visitado.

Aunque podemos llegar al nodo final, ese no es el nodo más cercano al que se puede acceder (el 4 lo es), por lo que debemos visitar el 4 para verificar si tiene un mejor camino hacia el nodo 6.

Resulta que sí. 6 es el único nodo no visitado accesible desde el nodo 4, y 14 + 6 es menor que 21. Así que actualizamos nuestra tabla por última vez.

Dado que el siguiente nodo más cercano, accesible y no visitado es nuestro nodo final (el algoritmo ha terminado y tenemos nuestro resultado), el valor de la ruta más corta entre 0 y 6 es 20.

Esto, sin embargo, no nos da la respuesta a "CUÁL es el camino más barato" entre 0 y 6, solo nos dice su valor. Aquí es donde entra el sombreado naranja claro.

Necesitamos averiguar cómo llegamos a 6, y lo hacemos comprobando "¿cuándo cambió el valor del camino más corto a 6 la última vez?".

Mirando nuestra tabla, podemos ver que el valor cambió de 21 a 20 cuando estábamos mirando el nodo 4. Podemos verlo mirando el nombre de la fila en la que estábamos cuando el valor se convirtió en 20, o la celda de color naranja claro El nombre de la columna de 's justo antes de que cambiara el valor.

Ahora sabemos que hemos llegado al nodo 6 desde el nodo 4, pero ¿cómo llegamos al nodo 4? Siguiendo el mismo principio, vemos que el valor de 4 cambió por última vez cuando estábamos mirando el nodo 5.

Aplicando el mismo principio al nodo 5 -> llegamos desde el nodo 3; llegamos al nodo 3 desde el nodo 1, y al nodo 1 desde nuestro nodo inicial, el nodo 0.

Esto nos da la ruta 0 -> 1 -> 3 -> 5 -> 4 -> 6 como la ruta con el menor valor de 0 a 6. Esta ruta a veces no es única, hay ** pueden** ser varios caminos que tengan el mismo valor.

Si desea practicar el algoritmo en otro gráfico antes de entrar en el código, aquí hay otro ejemplo y la solución: intente encontrar la solución por su cuenta primero. Buscaremos el camino más corto entre 8 y 6:

Nota: el algoritmo de Dijkstra no funciona en todos los tipos de gráficos. Es posible que haya notado que no hemos utilizado pesos negativos en nuestros bordes en nuestros ejemplos; esto se debe a la sencilla razón de que Dijkstra no funciona en gráficos con pesos negativos.

Si ejecutamos el algoritmo, buscando la ruta menos costosa entre 0 y 1, el algoritmo devolvería 0 -> 2 -> 1 aunque eso no sea correcto (la menos costosa es 0 -> 3 -\ > 1).

El algoritmo de Dijkstra ve que el siguiente nodo más cercano es 1, por lo que no verifica el resto de los nodos no visitados. Esto solo demuestra que Dijkstra no funciona con gráficos que contienen bordes negativos.

Ahora pasemos a la parte interesante: el código real. Hay varias formas de diseñar clases para este algoritmo, pero hemos optado por mantener la lista de objetos EdgeWeighted en la clase NodeWeighted, por lo que tenemos fácil acceso a todos los bordes de un nodo en particular.

Además, cada objeto EdgeWeighted contiene el objeto NodeWeighted de origen y el objeto NodeWeighted de destino, en caso de que queramos probar e implementar el algoritmo de manera diferente en el futuro.

Nota: Nuestra implementación se basa en la igualdad de objetos en el verdadero sentido, y todos nuestros métodos comparten exactamente el mismo objeto NodeWeighted, por lo que cualquier cambio en ese objeto se refleja en todo el gráfico. Esto podría no ser algo que desee en su código, sin embargo, confiar en esto hace que nuestro código sea mucho más legible y mejor para fines educativos, por lo que hemos elegido ese enfoque.

Implementación de un gráfico ponderado

Comencemos con la clase más simple de todas las que usaremos, la clase EdgeWeighted:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
public class EdgeWeighted implements Comparable<EdgeWeighted> {

    NodeWeighted source;
    NodeWeighted destination;
    double weight;

    EdgeWeighted(NodeWeighted s, NodeWeighted d, double w) {
        // Note that we are choosing to use the (exact) same objects in the Edge class
        // and in the GraphShow and GraphWeighted classes on purpose - this MIGHT NOT
        // be something you want to do in your own code, but for sake of readability
        // we've decided to go with this option
        source = s;
        destination = d;
        weight = w;
    }

    // ...
}

Los objetos NodeWeighted representan los nodos reales en nuestro gráfico ponderado. Implementaremos esa clase poco después de los bordes.

Ahora, simplemente implementemos el método toString() para imprimir objetos y el método compareTo():

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
public String toString() {
    return String.format("(%s -> %s, %f)", source.name, destination.name, weight);
}

// We need this method if we want to use PriorityQueues instead of LinkedLists
// to store our edges, the benefits are discussed later, we'll be using LinkedLists
// to make things as simple as possible
public int compareTo(EdgeWeighted otherEdge) {

    // We can't simply use return (int)(this.weight - otherEdge.weight) because
    // this sometimes gives false results
    if (this.weight > otherEdge.weight) {
        return 1;
    }
    else return -1;
}

Con nuestros bordes ponderados fuera del camino, implementemos nuestros nodos ponderados:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
public class NodeWeighted {
    // The int n and String name are just arbitrary attributes
    // we've chosen for our nodes these attributes can of course
    // be whatever you need
    int n;
    String name;
    private boolean visited;
    LinkedList<EdgeWeighted> edges;

    NodeWeighted(int n, String name) {
        this.n = n;
        this.name = name;
        visited = false;
        edges = new LinkedList<>();
    }

    boolean isVisited() {
        return visited;
    }

    void visit() {
        visited = true;
    }

    void unvisit() {
        visited = false;
    }
}

NodeWeighted es una clase bastante sencilla que se parece a los nodos regulares que hemos usado antes. Esta vez, la clase Graph no es la que contiene la información sobre los bordes entre los nodos, sino que cada nodo contiene una lista de sus propios vecinos.

Finalmente, implementemos la clase GraphWeighted que utilizará las dos clases anteriores para representar un gráfico:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
public class GraphWeighted {
    private Set<NodeWeighted> nodes;
    private boolean directed;

    GraphWeighted(boolean directed) {
        this.directed = directed;
        nodes = new HashSet<>();
    }

    // ...
}

Para almacenar nuestros nodos en el gráfico, usaremos un Set. Son convenientes para nosotros, ya que no permiten objetos duplicados y, en general, es fácil trabajar con ellos.

Ahora, como de costumbre, definamos los métodos principales que usaremos para construir nuestro gráfico, comenzando con el método addNode():

1
2
3
4
5
6
7
// Doesn't need to be called for any node that has an edge to another node
// since addEdge makes sure that both nodes are in the nodes Set
public void addNode(NodeWeighted... n) {
    // We're using a var arg method so we don't have to call
    // addNode repeatedly
    nodes.addAll(Arrays.asList(n));
}

Y con él, el método addEdge() junto con el método addEdgeHelper() utilizado por conveniencia y legibilidad:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
public void addEdge(NodeWeighted source, NodeWeighted destination, double weight) {
    // Since we're using a Set, it will only add the nodes
    // if they don't already exist in our graph
    nodes.add(source);
    nodes.add(destination);

    // We're using addEdgeHelper to make sure we don't have duplicate edges
    addEdgeHelper(source, destination, weight);

    if (!directed && source != destination) {
        addEdgeHelper(destination, source, weight);
    }
}

private void addEdgeHelper(NodeWeighted a, NodeWeighted b, double weight) {
    // Go through all the edges and see whether that edge has
    // already been added
    for (EdgeWeighted edge : a.edges) {
        if (edge.source == a && edge.destination == b) {
            // Update the value in case it's a different one now
            edge.weight = weight;
            return;
        }
    }
    // If it hasn't been added already (we haven't returned
    // from the for loop), add the edge
    a.edges.add(new EdgeWeighted(a, b, weight));
}

En este punto, nuestra lógica principal para GraphWeighted está lista. Simplemente necesitamos algún método para imprimir bordes, verificar si hay un borde entre dos nodos y restablecer todos los nodos visitados.

Comencemos con los bordes de impresión:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
public void printEdges() {
    for (NodeWeighted node : nodes) {
        LinkedList<EdgeWeighted> edges = node.edges;

        if (edges.isEmpty()) {
            System.out.println("Node " + node.name + " has no edges.");
            continue;
        }
        System.out.print("Node " + node.name + " has edges to: ");

        for (EdgeWeighted edge : edges) {
            System.out.print(edge.destination.name + "(" + edge.weight + ") ");
        }
        System.out.println();
    }
}

Ahora, una simple verificación si dos nodos tienen un borde entre ellos:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
public boolean hasEdge(NodeWeighted source, NodeWeighted destination) {
    LinkedList<EdgeWeighted> edges = source.edges;
    for (EdgeWeighted edge : edges) {
        // Again relying on the fact that all classes share the
        // exact same NodeWeighted object
        if (edge.destination == destination) {
            return true;
        }
    }
    return false;
}

Y finalmente, el método que restablece todos los nodos visitados para que podamos restablecer prácticamente el algoritmo:

1
2
3
4
5
6
// Necessary call if we want to run the algorithm multiple times
public void resetNodesVisited() {
    for (NodeWeighted node : nodes) {
        node.unvisit();
    }
}

Implementación del algoritmo de Dijkstra

Con nuestro gráfico ponderado y los nodos listos, finalmente podemos centrarnos en el propio algoritmo de Dijkstra. Va a ser un poco largo con muchas explicaciones en los comentarios, así que tengan paciencia con nosotros por un momento:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
public void DijkstraShortestPath(NodeWeighted start, NodeWeighted end) {
    // We keep track of which path gives us the shortest path for each node
    // by keeping track how we arrived at a particular node, we effectively
    // keep a "pointer" to the parent node of each node, and we follow that
    // path to the start
    HashMap<NodeWeighted, NodeWeighted> changedAt = new HashMap<>();
    changedAt.put(start, null);

    // Keeps track of the shortest path we've found so far for every node
    HashMap<NodeWeighted, Double> shortestPathMap = new HashMap<>();

    // Setting every node's shortest path weight to positive infinity to start
    // except the starting node, whose shortest path weight is 0
    for (NodeWeighted node : nodes) {
        if (node == start)
            shortestPathMap.put(start, 0.0);
        else shortestPathMap.put(node, Double.POSITIVE_INFINITY);
    }

    // Now we go through all the nodes we can go to from the starting node
    // (this keeps the loop a bit simpler)
    for (EdgeWeighted edge : start.edges) {
        shortestPathMap.put(edge.destination, edge.weight);
        changedAt.put(edge.destination, start);
    }

    start.visit();

    // This loop runs as long as there is an unvisited node that we can
    // reach from any of the nodes we could till then
    while (true) {
        NodeWeighted currentNode = closestReachableUnvisited(shortestPathMap);
        // If we haven't reached the end node yet, and there isn't another
        // reachable node the path between start and end doesn't exist
        // (they aren't connected)
        if (currentNode == null) {
            System.out.println("There isn't a path between " + start.name + " and " + end.name);
            return;
        }

        // If the closest non-visited node is our destination, we want to print the path
        if (currentNode == end) {
            System.out.println("The path with the smallest weight between "
                                   + start.name + " and " + end.name + " is:");

            NodeWeighted child = end;

            // It makes no sense to use StringBuilder, since
            // repeatedly adding to the beginning of the string
            // defeats the purpose of using StringBuilder
            String path = end.name;
            while (true) {
                NodeWeighted parent = changedAt.get(child);
                if (parent == null) {
                    break;
                }

                // Since our changedAt map keeps track of child -> parent relations
                // in order to print the path we need to add the parent before the child and
                // it's descendants
                path = parent.name + " " + path;
                child = parent;
            }
            System.out.println(path);
            System.out.println("The path costs: " + shortestPathMap.get(end));
            return;
        }
        currentNode.visit();

        // Now we go through all the unvisited nodes our current node has an edge to
        // and check whether its shortest path value is better when going through our
        // current node than whatever we had before
        for (EdgeWeighted edge : currentNode.edges) {
            if (edge.destination.isVisited())
                continue;

            if (shortestPathMap.get(currentNode)
               + edge.weight
               < shortestPathMap.get(edge.destination)) {
                shortestPathMap.put(edge.destination,
                                   shortestPathMap.get(currentNode) + edge.weight);
                changedAt.put(edge.destination, currentNode);
            }
        }
    }
}

Y finalmente, definamos el método closestReachableUnvisited() que evalúa cuál es el nodo más cercano al que podemos llegar y que no hemos visitado antes:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
private NodeWeighted closestReachableUnvisited(HashMap<NodeWeighted, Double> shortestPathMap) {

    double shortestDistance = Double.POSITIVE_INFINITY;
    NodeWeighted closestReachableNode = null;
    for (NodeWeighted node : nodes) {
        if (node.isVisited())
            continue;

        double currentDistance = shortestPathMap.get(node);
        if (currentDistance == Double.POSITIVE_INFINITY)
            continue;

        if (currentDistance < shortestDistance) {
            shortestDistance = currentDistance;
            closestReachableNode = node;
        }
    }
    return closestReachableNode;
}

Ahora que tenemos todo eso, probemos nuestro algoritmo en el primer ejemplo de arriba:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
public class GraphShow {
    public static void main(String[] args) {
        GraphWeighted graphWeighted = new GraphWeighted(true);
        NodeWeighted zero = new NodeWeighted(0, "0");
        NodeWeighted one = new NodeWeighted(1, "1");
        NodeWeighted two = new NodeWeighted(2, "2");
        NodeWeighted three = new NodeWeighted(3, "3");
        NodeWeighted four = new NodeWeighted(4, "4");
        NodeWeighted five = new NodeWeighted(5, "5");
        NodeWeighted six = new NodeWeighted(6, "6");

        // Our addEdge method automatically adds Nodes as well.
        // The addNode method is only there for unconnected Nodes,
        // if we wish to add any
        graphWeighted.addEdge(zero, one, 8);
        graphWeighted.addEdge(zero, two, 11);
        graphWeighted.addEdge(one, three, 3);
        graphWeighted.addEdge(one, four, 8);
        graphWeighted.addEdge(one, two, 7);
        graphWeighted.addEdge(two, four, 9);
        graphWeighted.addEdge(three, four, 5);
        graphWeighted.addEdge(three, five, 2);
        graphWeighted.addEdge(four, six, 6);
        graphWeighted.addEdge(five, four, 1);
        graphWeighted.addEdge(five, six, 8);

        graphWeighted.DijkstraShortestPath(zero, six);
    }
}

Obtenemos la siguiente salida:

1
2
3
The path with the smallest weight between 0 and 6 is:
0 1 3 5 4 6
The path costs: 20.0

Que es exactamente lo que obtuvimos al hacer manualmente el algoritmo.

Usarlo en el segundo ejemplo de arriba nos da el siguiente resultado:

1
2
3
The path with the smallest weight between 8 and 6 is:
8 1 4 7 6
The path costs: 12.0

Además, mientras buscábamos la ruta más barata entre dos nodos usando Dijkstra, lo más probable es que encontráramos muchas otras rutas más baratas entre nuestro nodo inicial y otros nodos en el gráfico. En realidad, hemos encontrado la ruta más económica desde el origen hasta el nodo para cada nodo visitado. Solo siéntate en eso por un momento, lo probaremos en una última sección.

Sin embargo, si quisiéramos saber la ruta más corta entre nuestro nodo inicial y todos los demás nodos, necesitaríamos seguir ejecutando el algoritmo en todos los nodos que aún no se han visitado. En el peor de los casos, necesitaríamos ejecutar el algoritmo numberOfNodes - 1 veces.

Nota: El algoritmo de Dijkstra es un ejemplo de un algoritmo codicioso. Lo que significa que en cada paso, el algoritmo hace lo que parece mejor en ese paso y no visita un nodo más de una vez. Tal paso es localmente óptimo pero no necesariamente óptimo al final.

Esta es la razón por la que Dijkstra falla con los bordes ponderados negativamente, no vuelve a visitar los nodos que podrían tener un camino más económico a través de un borde ponderado negativamente porque el nodo ya ha sido visitado. Sin embargo, sin bordes ponderados negativamente, Dijkstra es globalmente óptimo (es decir, funciona).

Complejidad de Dijkstra

Let's consider the complejidad de este algoritmo, and look at why we mentioned PriorityQueue and added a compareTo() method to our EdgeWeighted class.

El cuello de botella del algoritmo de Dijkstra es encontrar el siguiente nodo/vértice no visitado más cercano. Usando LinkedList esto tiene una complejidad de O(numberOfEdges), ya que en el peor de los casos necesitamos recorrer todos los bordes del nodo para encontrar el que tiene el menor peso.

Para mejorar esto, podemos usar la estructura de datos del montón de Java - PriorityQueue. El uso de una PriorityQueue nos garantiza que el siguiente nodo no visitado más cercano (si lo hay) será el primer elemento de la PriorityQueue.

Entonces, ahora encontrar el siguiente nodo más cercano se realiza en tiempo constante (O(1)), sin embargo, mantener ordenada la ‘PriorityQueue’ (eliminar los bordes usados ​​y agregar otros nuevos) toma O(log(numberOfEdges)) tiempo . Esto sigue siendo mucho mejor que O(numberOfEdges).

Además, tenemos O(numberOfNodes) iteraciones y, por lo tanto, tantas eliminaciones de PriorityQueue (que toman O(log(numberOfEdges)) tiempo), y agregar todos nuestros bordes también toma O(log(numberOfEdges )) tiempo.

Esto nos da un total de complejidad O((numberOfEdges + numberOfNodes) * log(numberOfEdges)) cuando usamos PriorityQueue.

Si no usamos PriorityQueue (como no lo hicimos), la complejidad sería O((numberOfEdges + numberOfNodes) * numberOfEdges) .

Corrección del algoritmo de Dijkstra

Hasta ahora hemos estado usando el algoritmo de Dijkstra sin probar realmente que realmente funciona. El algoritmo es lo suficientemente "intuitivo" para que demos por hecho ese hecho, pero demostremos que ese es realmente el caso.

We'll use mathematical induction to prove the exactitud de este algoritmo.

¿Qué significa "corrección" en nuestro caso?

Bueno, queremos demostrar que al final de nuestro algoritmo, todas las rutas que hemos encontrado (todos los nodos que hemos visitado) son en realidad las rutas más baratas desde el origen hasta ese nodo, incluido el nodo de destino cuando Hazlo.

Probamos esto demostrando que es cierto al principio (para el nodo de inicio) y demostramos que sigue siendo cierto en cada paso del algoritmo.

Definamos algunos nombres abreviados para las cosas que necesitaremos en esta prueba:

  • CPF(x): Cmás alto Path Fencontrado desde el nodo de inicio hasta el nodo x
  • ACP(x): Aactual Cmás alto Path desde el nodo inicial hasta el nodo x
  • d(x,y): La distancia/peso del borde entre los nodos y y x
  • V: Todos los nodos visitados hasta el momento

Muy bien, queremos probar que en cada paso del algoritmo, y al final x ∈ V, CPF(x) = ACP(x), es decir, que para cada nodo que hemos visitado, la ruta más barata que 've found es en realidad la ruta más barata para ese nodo.

Caso base: (al principio) solo tenemos un nodo en V, y ese es el nodo inicial. Así que como V = {inicio} y ACP(inicio) = 0 = CPF(inicio), nuestro algoritmo es correcto.

Hipótesis Inductiva: Después de agregar un nodo n a V (visitando ese nodo), para cada x ∈ V => CPF(x) = ACP(x)

Paso inductivo: Sabemos que para V sin n nuestro algoritmo es correcto. Necesitamos probar que sigue siendo correcto después de agregar un nuevo nodo n. Digamos que V' es V ∪ {n} (en otras palabras, V' es lo que obtenemos después de visitar el nodo n).

Así que sabemos que para cada nodo en V nuestro algoritmo es correcto, es decir, que para cada x ∈ V, CPF(x) => ACP(x), así que para que sea cierto para V' necesitamos Demuestre que CPF(n) = ACP(n).

Probaremos esto por contradicción, es decir, asumiremos que CPF(n) ≠ ACP(n) y mostraremos que eso no es posible.

Supongamos que ACP(n) < CPF(n).

El ‘ACP(n)’ comienza en algún lugar de ‘V’ y en algún punto deja ‘V’ para llegar a ’n’ (ya que ’n’ no está en ‘V’, tiene que dejar ‘V’). Digamos que alguna arista (x,y) es la primera arista que sale de V, es decir, que x está en V pero y no lo está.

Sabemos dos cosas:

  1. La ruta que nos lleva a ACP(x) es una subruta de la ruta que nos lleva a ACP(n)
  2. ACP(x) + d(x,y) <= ACP(n) (ya que hay al menos tantos nodos entre inicio e y como entre inicio y n, ya que conocemos el la ruta más barata a n pasa por y)

Nuestra hipótesis inductiva dice que CPF(x) = ACP(x), lo que nos permite cambiar (2) a CPF(x) + d(x,y) <= ACP(x).

Dado que y es adyacente a x, el algoritmo debe haber actualizado el valor de y al observar x (ya que x está en V), por lo que sabemos que CPF(y) < = FECP(x) + d(x,y).

Además, dado que el nodo n fue seleccionado por el algoritmo, sabemos que n debe ser el nodo más cercano de todos los no visitados (recordatorio: y tampoco fue visitado y se suponía que estaba en el camino más corto a n) , lo que significa que CPF(n) <= CPF(y).

Si combinamos todas estas desigualdades, veremos que CPF(n) < ACP(n) lo que nos da una contradicción, es decir, nuestra suposición de que ACP(n) < CPF(n) no era correcta .

  • CPF(n) <= CPF(y) y CPF(y) <= CPF(x) + d(x,y) nos dan -> CPF(n) <= CPF(x) + d(x,y)
  • CPF(x) + d(x,y) <= ACP(x) y ACP(x) + d(x,y) <= ACP(n) nos dan -> CPF(n) <= ACP(x) que luego nos da CPF(n) < ACP(n)

Por lo tanto, nuestro algoritmo hace lo que se supone que debe hacer.

Nota: Esto también prueba que las rutas a todos los nodos que hemos visitado durante el algoritmo también son las rutas más baratas a esos nodos, no solo la ruta que encontramos para el nodo de destino.

Conclusión

Los gráficos son una forma conveniente de almacenar ciertos tipos de datos. El concepto fue portado de las matemáticas y apropiado para las necesidades de la informática. Debido al hecho de que muchas cosas se pueden representar como gráficos, el recorrido de gráficos se ha convertido en una tarea común, especialmente utilizada en ciencia de datos y aprendizaje automático.

El algoritmo de Dijkstra encuentra la ruta menos costosa en un gráfico ponderado entre nuestro nodo inicial y un nodo de destino, si existe tal ruta. Comienza en el nodo de destino y retrocede hasta el nodo raíz, a lo largo de los bordes ponderados en el camino "más barato" para cruzar.