Introducción
Contenido
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 Machine Learning.
- Gráficos en Java
- Representar gráficos en código
- Búsqueda en profundidad (DFS)
- Búsqueda primero en amplitud (BFS)
- Algoritmo de Dijkstra
¿Cómo funciona el algoritmo de Dijkstra?
El algoritmo de Dijkstra encuentra la ruta menos costosa en un gráfico ponderado entre nuestro node inicial y un node de destino, si existe dicha ruta.
Al final del algoritmo, cuando llegamos al node de destino, podemos imprimir la ruta de menor costo retrocediendo desde el node de destino hasta el node de inicio. Más adelante en el artículo veremos cómo podemos hacer eso al hacer un seguimiento de cómo llegamos a cada node.
Como esta vez usaremos gráficas ponderadas, tendremos que crear una nueva GraphWeightedclase que tenga los métodos necesarios para manejarlas.
El algoritmo de Dijkstra funciona así:
- Tenemos un gráfico ponderado
Gcon un conjunto de vértices (nodes)Vy un conjunto de aristasE - También tenemos un node inicial llamado
s, y establecemos la distancia entresysa 0 - Marque la distancia entre
sy todos los demás nodes como infinita, es decir, inicie el algoritmo como si ningún node fuera accesible desde el nodes - Marque todos los nodes (excepto
s) como no visitados, o marquescomo visitados si todos los demás nodes ya están marcados como no visitados (que es el enfoque que usaremos) - Siempre que haya un node no visitado, haga lo siguiente:
- Encuentre el node
nque tiene la distancia más corta desde el node inicials - Marcar
ncomo visitado - Para cada borde entre
nym, dondemno se visita:- Si
cheapestPath(s,n)+cheapestPath(n,m)<cheapestPath(s,m), actualice la ruta más barata entresympara que sea igual acheapestPath(s,n)+cheapestPath(n,m)
- Si
- Encuentre el node
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 node 0 al node 6. Usaremos una matriz / tabla para representar mejor lo que está sucediendo en el algoritmo.
Al principio, todos los datos que tenemos son la distancia entre 0 y sus nodes vecinos.
El resto de distancias se denotan como infinito positivo, es decir, no son accesibles desde ninguno de los nodes que hemos procesado hasta ahora (solo hemos procesado 0).
El siguiente paso es encontrar el node más cercano que aún no se ha visitado y al que podemos llegar desde uno de los nodes que hemos procesado. En nuestro caso, este es el node 1.
Ahora actualizaremos los valores de la ruta más corta si es necesario. Por ejemplo, ahora se puede acceder al node 3 desde el node 1.
También marcaremos 1 como visitado.
Nota: Tenemos que tener en cuenta cuánto «cuesta» llegar al node 1. Como nuestra posición inicial es 0 y cuesta 8 unidades pasar de 0 a 1, tenemos que sumar ese 8 al coste total de » moviéndose «de 1 a otro node. Es por eso que sumamos 8 (distancia de 0 a 1) + 3 (distancia de 1 a 3) = 11 a nuestra tabla, en lugar de solo 3.
Te puede interesar:Interfaz iterable de Java: Iterator, ListIterator y SpliteratorVemos que desde el node 1 podemos llegar a los nodes 2, 3 y 4.
- node 2 -> para llegar 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 ruta mejor de 0 a 2 a través del node 1, por lo que no cambiamos nada.
- node 3 -> pasar de 1 a 3 cuesta 3 unidades, y dado que 3 era inalcanzable anteriormente, 8 + 3 es definitivamente mejor que el infinito positivo, así que actualizamos la tabla en esa celda
- node 4 -> igual que con el node 3, anteriormente inalcanzable, por lo que también actualizamos la tabla para el node 4
El sombreado naranja oscuro nos ayuda a realizar un seguimiento de los nodes que hemos visitado, discutiremos por qué se agregó el tono naranja más claro más adelante.
Ahora podemos elegir entre el node 2 y el node 3, ya que ambos están tan «cerca» del node 0. Vayamos con el node 3.
Los nodes no visitados y accesibles desde el node 3 son los nodes 4 y 5:
- node 4 -> cuesta 5 unidades pasar del node 3 al node 4, y 11 + 5 no es mejor que el valor anterior de 16 unidades que encontramos, por lo que no es necesario actualizar
- node 5 -> cuesta 2 unidades pasar del node 3 al node 5, y 11 + 2 es mejor que el infinito positivo, así que actualizamos la tabla
- Marcamos 3 como visitado.
El siguiente node a considerar es el node 2, sin embargo, el único node accesible desde el node 2 es el node 4 y el valor que obtenemos (11 + 9 = 20) no es mejor que el valor anterior que encontramos (16), así que no hacemos cambios en nuestra tabla, además de marcar el node 2 como visitado.
El siguiente node alcanzable más cercano es el 5, y los vecinos no visitados de 5 son 4 y 6.
- node 4 -> 13 + 1 es mejor que 16, por lo que el valor se actualiza
- node 6 -> 13 + 8 es mejor que infinito positivo, por lo que el valor se actualiza
- Marque 5 como visitado.
Aunque podemos llegar al node final, ese no es el node alcanzable más cercano (4 lo es), por lo que debemos visitar el 4 para verificar si tiene una mejor ruta al node 6.
Resulta que sí. 6 es el único node no visitado accesible desde el node 4, y 14 + 6 es menor que 21. Así que actualizamos nuestra tabla una última vez.
Dado que el siguiente node más cercano, accesible y no visitado es nuestro node 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 la ruta más barata?» Entre 0 y 6, solo nos dice su valor. Aquí es donde entra el tono naranja claro.
Necesitamos averiguar cómo llegamos a 6, y lo hacemos comprobando «¿cuándo cambió el valor de la ruta más corta a 6 la última vez?».
Mirando nuestra tabla, podemos ver que el valor cambió de 21 a 20 cuando estábamos mirando el node 4. Podemos ver eso 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. nombre de la columna justo antes del cambio de valor.
Ahora sabemos que hemos llegado al node 6 desde el node 4, pero ¿cómo llegamos al node 4? Siguiendo el mismo principio, vemos que el valor de 4 cambió por última vez cuando estábamos mirando el node 5.
Aplicando el mismo principio al node 5 -> llegamos del node 3; llegamos al node 3 desde el node 1 y al node 1 desde nuestro node inicial, el node 0.
Te puede interesar:Métodos de objetos de Java: hashCode ()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, puede haber varias rutas que tienen 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: primero intente encontrar la solución por su cuenta. 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 (el menos costoso es 0 -> 3 -> 1).
El algoritmo de Dijkstra ve que el siguiente node más cercano es 1, por lo que no verifica el resto de los nodes 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 EdgeWeightedobjetos en la NodeWeightedclase, por lo que tenemos fácil acceso a todos los bordes de un node en particular.
Además, cada EdgeWeightedobjeto contiene el NodeWeightedobjeto de origen y el NodeWeightedobjeto de destino , en caso de que queramos intentar 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 NodeWeightedobjeto, por lo que cualquier cambio en ese objeto se refleja en todo el gráfico. Es posible que esto no sea 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 EdgeWeightedclase:
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 NodeWeightedobjetos representan los nodes reales en nuestro gráfico ponderado. Implementaremos esa clase poco después de los bordes.
Ahora, simplemente implementemos el toString()método por el bien de imprimir objetos y el compareTo()método:
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 nodes ponderados:
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;
}
}
El NodeWeightedes una clase que se asemeja bastante sencillo nodes regulares que hemos utilizado antes. Esta vez, la Graphclase no es la que contiene la información sobre los bordes entre los nodes, sino que cada node contiene una lista de sus propios vecinos.
Finalmente, implementemos la GraphWeightedclase que utilizará las dos clases anteriores para representar un gráfico:
public class GraphWeighted {
private Set<NodeWeighted> nodes;
private boolean directed;
GraphWeighted(boolean directed) {
this.directed = directed;
nodes = new HashSet<>();
}
// ...
}
Para almacenar nuestros nodes en el gráfico, usaremos a Set. Nos resultan convenientes, ya que no permiten objetos duplicados y, por lo general, es sencillo trabajar con ellos.
Ahora, como de costumbre, definamos los métodos principales que usaremos para construir nuestro gráfico, comenzando con el addNode()método:
// 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 addEdge()método junto con el addEdgeHelper()método utilizado por conveniencia y legibilidad:
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 GraphWeightedestá lista. Simplemente necesitamos algún método para imprimir bordes, verificar si hay un borde entre dos nodes y restablecer todos los nodes visitados.
Comencemos con la impresión de bordes:
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 nodes tienen una ventaja entre ellos:
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 resetea todos los nodes visitados para que prácticamente podamos resetear el algoritmo:
// Necessary call if we want to run the algorithm multiple times
public void resetNodesVisited() {
for (NodeWeighted node : nodes) {
node.unvisit();
}
}
Implementando el algoritmo de Dijkstra
Con nuestro gráfico ponderado y los nodes terminados, finalmente podemos enfocarnos en el algoritmo de Dijkstra. Va a ser un poco largo con muchas explicaciones en los comentarios, así que tengan paciencia con nosotros por un momento:
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 closestReachableUnvisited()método que evalúa cuál es el node más cercano al que podemos llegar y que no hemos visitado antes:
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:
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 el siguiente resultado:
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 anterior nos da el siguiente resultado:
The path with the smallest weight between 8 and 6 is:
8 1 4 7 6
The path costs: 12.0
Además, mientras buscamos la ruta más barata entre dos nodes usando Dijkstra, lo más probable es que encontremos muchas otras rutas más baratas entre nuestro node inicial y otros nodes en el gráfico. De hecho, hemos encontrado la ruta más barata de la fuente al node para cada node visitado. Siéntese en eso por un momento, lo probaremos en una última sección.
Te puede interesar:Control de flujo de Java: declaraciones while y do-whileSin embargo, si quisiéramos saber la ruta más corta entre nuestro node inicial y todos los demás nodes, necesitaríamos seguir ejecutando el algoritmo en todos los nodes 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 algoritmo codicioso. Lo que significa que en cada paso, el algoritmo hace lo que parece mejor en ese paso y no visita un node 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 bordes ponderados negativamente, no vuelve a visitar los nodes que podrían tener una ruta más barata a través de un borde ponderado negativamente porque el node ya ha sido visitado. Sin embargo, sin bordes ponderados negativamente, Dijkstra es globalmente óptimo (es decir, funciona).
Complejidad de Dijkstra
Consideremos la complejidad de este algoritmo y veamos por qué mencionamos PriorityQueuey agregamos un compareTo()método a nuestra EdgeWeightedclase.
El cuello de botella del algoritmo de Dijkstra es encontrar el siguiente node / vértice no visitado más cercano. Usar LinkedListesto tiene una complejidad de O (numberOfEdges), ya que en el peor de los casos necesitamos pasar por todos los bordes del node para encontrar el que tenga el menor peso.
Para mejorar esto, podemos usar la estructura de datos del montón de Java – PriorityQueue. El uso de a PriorityQueuenos garantiza que el siguiente node no visitado más cercano (si hay uno) será el primer elemento de PriorityQueue.
Entonces, ahora encontrar el siguiente node más cercano se realiza en un tiempo constante (O (1)), sin embargo, mantener el orden 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 del 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 O ((numberOfEdges + numberOfNodes) * log (numberOfEdges)) complejidad al usar 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 demostrar realmente que realmente funciona. El algoritmo es lo suficientemente «intuitivo» como para que demos por sentado ese hecho, pero demostremos que ese es realmente el caso.
Usaremos la inducción matemática para demostrar la 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 nodes que hemos visitado) son en realidad las rutas más baratas desde la fuente hasta ese node, incluido el node de destino cuando llegamos a eso.
Te puede interesar:Control de flujo de Java: declaraciones if y if-elseDemostramos esto demostrando que es cierto al principio (para el node de inicio) y demostramos que sigue siendo cierto en cada paso del algoritmo.
Definamos algunos nombres abreviados para las cosas que necesitaremos en esta demostración:
CPF(x): C heapest P ath F ound de principio node a node xACP(x): A ctual C heapest P ath de principio node a node xd(x,y): La distancia / peso del borde entre los nodes y y xV: Todos los nodes visitados hasta ahora
Muy bien, queremos demostrar que en cada paso del algoritmo, y al final x ∈ V, CPF(x) = ACP(x), es decir, que para cada node que hemos visitado, la ruta más barata que hemos encontrado es en realidad la ruta más barata para ese node.
Caso base: (al principio) solo tenemos un node V, y ese es el node inicial. Entonces, desde V = {start}y ACP(start) = 0 = CPF(start), nuestro algoritmo es correcto.
Hipótesis inductiva: después de agregar un node na V(visitar ese node), para cadax ∈ V => CPF(x) = ACP(x)
Paso inductivo: sabemos que Vsin nnuestro algoritmo es correcto. Necesitamos demostrar que permanece correcto después de agregar un nuevo node n. Digamos que V'es V ∪ {n}(en otras palabras, V'es lo que obtenemos después de visitar el node n).
Entonces sabemos que para cada node en Vnuestro algoritmo es correcto, es decir, para cada x ∈ V, CPF(x) => ACP(x), por lo que para que sea cierto V', necesitamos demostrarlo CPF(n) = ACP(n).
Lo demostraremos por contradicción, es decir, lo asumiremos CPF(n) ≠ ACP(n)y demostraremos que eso no es posible.
Asumamos eso ACP(n) < CPF(n).
El ACP(n)comienza en algún lugar Vy en algún momento se va Vpara llegar n(ya nque no está V, tiene que irse V). Digamos que algún borde ( x, y) es el primer borde que sale V, es decir, que xestá dentro Vpero yno lo está.
Sabemos dos cosas:
- El camino que nos llevó
ACP(x)es un subtrayecto del camino que nos llevaACP(n) ACP(x) + d(x,y) <= ACP(n)(ya que hay al menos tantos nodes entre inicio yycomo hay entre inicio yn, ya que sabemos cuál es la ruta más barata por la quenpasay)
Nuestra hipótesis inductiva dice aquello a CPF(x) = ACP(x)lo que cambiemos (2) CPF(x) + d(x,y) <= ACP(x).
Dado que y es adyacente a x, el algoritmo debe haber actualizado el valor de yal mirar x(ya que xestá en V), así que lo sabemos CPF(y) <= CPF(x) + d(x,y).
Además, dado que el nalgoritmo eligió el node , sabemos que ndebe ser el node más cercano de todos los no visitados (recordatorio: ytampoco fue visitado y se suponía que estaba en el camino más corto hacia n), lo que significa eso CPF(n) <= CPF(y).
Si combinamos todas estas desigualdades veremos lo que CPF(n) < ACP(n)nos da una contradicción, es decir, nuestra suposición de que ACP(n) < CPF(n)no era correcta.
CPF(n) <= CPF(y)yCPF(y) <= CPF(x) + d(x,y)danos ->CPF(n) <= CPF(x) + d(x,y)CPF(x) + d(x,y) <= ACP(x)yACP(x) + d(x,y) <= ACP(n)danos ->CPF(n) <= ACP(x)que luego nos daCPF(n) < ACP(n)
Por lo tanto, nuestro algoritmo hace lo que se supone que debe hacer.
Nota: Esto también demuestra que las rutas a todos los nodes que hemos visitado durante el algoritmo son también las rutas más baratas a esos nodes, no solo la ruta que encontramos para el node 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 Machine Learning.
El algoritmo de Dijkstra encuentra la ruta menos costosa en un gráfico ponderado entre nuestro node inicial y un node de destino, si existe dicha ruta. Comienza en el node de destino y retrocede hasta el node raíz, a lo largo de los bordes ponderados en la ruta «más barata» para cruzar.
