1. Información general
El énfasis en este artículo es el problema de la ruta más corta (SPP), siendo uno de los problemas teóricos fundamentales conocidos en la teoría de grafos, y cómo se puede utilizar el algoritmo de Dijkstra para resolverlo.
El objetivo básico del algoritmo es determinar la ruta más corta entre un nodo inicial y el resto del gráfico.
2. Problema del camino más corto con Dijkstra
Dado un gráfico ponderado positivamente y un nodo inicial (A), Dijkstra determina el camino más corto y la distancia desde la fuente a todos los destinos en el gráfico:
La idea central del algoritmo de Dijkstra es eliminar continuamente las rutas más largas entre el nodo inicial y todos los destinos posibles.
Para realizar un seguimiento del proceso, necesitamos tener dos conjuntos distintos de nodos, asentados y no asentados.
Los nodos asentados son los que tienen una distancia mínima conocida desde la fuente. El conjunto de nodos sin resolver reúne nodos a los que podemos llegar desde la fuente, pero no conocemos la distancia mínima desde el nodo inicial.
Aquí hay una lista de pasos a seguir para resolver el SPP con Dijkstra:
- Establezca la distancia a startNode en cero.
- Establezca todas las demás distancias en un valor infinito.
- Agregamos el startNode al conjunto de nodos sin resolver.
- Si bien el conjunto de nodos sin resolver no está vacío, nosotros:
- Elija un nodo de evaluación del conjunto de nodos sin asentar, el nodo de evaluación debe ser el que tenga la distancia más baja desde la fuente.
- Calcule nuevas distancias a los vecinos directos manteniendo la distancia más baja en cada evaluación.
- Agregue vecinos que aún no están asentados al conjunto de nodos sin asentar.
Estos pasos se pueden agregar en dos etapas, inicialización y evaluación. Veamos cómo se aplica eso a nuestro gráfico de muestra:
2.1. Inicialización
Antes de comenzar a explorar todas las rutas en el gráfico, primero debemos inicializar todos los nodos con una distancia infinita y un predecesor desconocido, excepto la fuente.
Como parte del proceso de inicialización, debemos asignar el valor 0 al nodo A (sabemos que la distancia del nodo A al nodo A es 0 obviamente)
Entonces, cada nodo en el resto del gráfico se distinguirá con un predecesor y una distancia:
Para finalizar el proceso de inicialización, debemos agregar el nodo A a los nodos sin resolver, configurarlo para que se elija primero en el paso de evaluación. Tenga en cuenta que el conjunto de nodos asentados todavía está vacío.
2.2. Evaluación
Ahora que tenemos nuestro gráfico inicializado, elegimos el nodo con la distancia más baja del conjunto sin asentar, luego evaluamos todos los nodos adyacentes que no están en nodos asentados:
La idea es agregar el peso del borde a la distancia del nodo de evaluación y luego compararlo con la distancia del destino. Por ejemplo, para el nodo B, 0 + 10 es menor que INFINITY, por lo que la nueva distancia para el nodo B es 10, y el nuevo predecesor es A, lo mismo se aplica al nodo C.
A continuación, el nodo A se mueve de los nodos sin asentar a los nodos asentados.
Los nodos B y C se agregan a los nodos sin resolver porque se pueden alcanzar, pero deben evaluarse.
Ahora que tenemos dos nodos en el conjunto sin resolver, elegimos el que tiene la distancia más baja (nodo B), luego reiteramos hasta que establezcamos todos los nodos en el gráfico:
Aquí hay una tabla que resume las iteraciones que se realizaron durante los pasos de evaluación:
| Iteración | Inestable | Colocado | EvaluationNode | UN | segundo | C | re | mi | F |
|---|---|---|---|---|---|---|---|---|---|
| 1 | UN | - | UN | 0 | A-10 | A-15 | X-∞ | X-∞ | X-∞ |
| 2 | ANTES DE CRISTO | UN | segundo | 0 | A-10 | A-15 | B-22 | X-∞ | B-25 |
| 3 | C, F, D | A, B | C | 0 | A-10 | A-15 | B-22 | C-25 | B-25 |
| 4 | D, E, F | A B C | re | 0 | A-10 | A-15 | B-22 | D-24 | D-23 |
| 5 | E, F | A B C D | F | 0 | A-10 | A-15 | B-22 | D-24 | D-23 |
| 6 | mi | A B C D F | mi | 0 | A-10 | A-15 | B-22 | D-24 | D-23 |
| Final | - | TODAS | NINGUNA | 0 | A-10 | A-15 | B-22 | D-24 | D-23 |
La notación B-22, por ejemplo, significa que el nodo B es el predecesor inmediato, con una distancia total de 22 desde el nodo A.
Finalmente, podemos calcular las rutas más cortas desde el nodo A son las siguientes:
- Nodo B: A -> B (distancia total = 10)
- Nodo C: A -> C (distancia total = 15)
- Nodo D: A -> B -> D (distancia total = 22)
- Nodo E: A -> B -> D -> E (distancia total = 24)
- Nodo F: A -> B -> D -> F (distancia total = 23)
3. Implementación de Java
En esta sencilla implementación representaremos un gráfico como un conjunto de nodos:
public class Graph { private Set nodes = new HashSet(); public void addNode(Node nodeA) { nodes.add(nodeA); } // getters and setters }A node can be described with a name, a LinkedList in reference to the shortestPath, a distance from the source, and an adjacency list named adjacentNodes:
public class Node { private String name; private List shortestPath = new LinkedList(); private Integer distance = Integer.MAX_VALUE; Map adjacentNodes = new HashMap(); public void addDestination(Node destination, int distance) { adjacentNodes.put(destination, distance); } public Node(String name) { this.name = name; } // getters and setters }The adjacentNodes attribute is used to associate immediate neighbors with edge length. This is a simplified implementation of an adjacency list, which is more suitable for the Dijkstra algorithm than the adjacency matrix.
As for the shortestPath attribute, it is a list of nodes that describes the shortest path calculated from the starting node.
By default, all node distances are initialized with Integer.MAX_VALUE to simulate an infinite distance as described in the initialization step.
Now, let's implement the Dijkstra algorithm:
public static Graph calculateShortestPathFromSource(Graph graph, Node source) { source.setDistance(0); Set settledNodes = new HashSet(); Set unsettledNodes = new HashSet(); unsettledNodes.add(source); while (unsettledNodes.size() != 0) { Node currentNode = getLowestDistanceNode(unsettledNodes); unsettledNodes.remove(currentNode); for (Entry adjacencyPair: currentNode.getAdjacentNodes().entrySet()) { Node adjacentNode = adjacencyPair.getKey(); Integer edgeWeight = adjacencyPair.getValue(); if (!settledNodes.contains(adjacentNode)) { calculateMinimumDistance(adjacentNode, edgeWeight, currentNode); unsettledNodes.add(adjacentNode); } } settledNodes.add(currentNode); } return graph; }The getLowestDistanceNode() method, returns the node with the lowest distance from the unsettled nodes set, while the calculateMinimumDistance() method compares the actual distance with the newly calculated one while following the newly explored path:
private static Node getLowestDistanceNode(Set unsettledNodes) { Node lowestDistanceNode = null; int lowestDistance = Integer.MAX_VALUE; for (Node node: unsettledNodes) { int nodeDistance = node.getDistance(); if (nodeDistance < lowestDistance) { lowestDistance = nodeDistance; lowestDistanceNode = node; } } return lowestDistanceNode; }private static void CalculateMinimumDistance(Node evaluationNode, Integer edgeWeigh, Node sourceNode) { Integer sourceDistance = sourceNode.getDistance(); if (sourceDistance + edgeWeigh < evaluationNode.getDistance()) { evaluationNode.setDistance(sourceDistance + edgeWeigh); LinkedList shortestPath = new LinkedList(sourceNode.getShortestPath()); shortestPath.add(sourceNode); evaluationNode.setShortestPath(shortestPath); } }Now that all the necessary pieces are in place, let's apply the Dijkstra algorithm on the sample graph being the subject of the article:
Node nodeA = new Node("A"); Node nodeB = new Node("B"); Node nodeC = new Node("C"); Node nodeD = new Node("D"); Node nodeE = new Node("E"); Node nodeF = new Node("F"); nodeA.addDestination(nodeB, 10); nodeA.addDestination(nodeC, 15); nodeB.addDestination(nodeD, 12); nodeB.addDestination(nodeF, 15); nodeC.addDestination(nodeE, 10); nodeD.addDestination(nodeE, 2); nodeD.addDestination(nodeF, 1); nodeF.addDestination(nodeE, 5); Graph graph = new Graph(); graph.addNode(nodeA); graph.addNode(nodeB); graph.addNode(nodeC); graph.addNode(nodeD); graph.addNode(nodeE); graph.addNode(nodeF); graph = Dijkstra.calculateShortestPathFromSource(graph, nodeA); Después del cálculo, se establecen los atributos de ruta más corta y distancia para cada nodo en el gráfico, podemos iterar a través de ellos para verificar que los resultados coincidan exactamente con lo que se encontró en la sección anterior.
4. Conclusión
En este artículo, hemos visto cómo el algoritmo de Dijkstra resuelve el SPP y cómo implementarlo en Java.
La implementación de este proyecto simple se puede encontrar en el siguiente enlace del proyecto de GitHub.