Implementación del camino más corto en Java
Implementación del algoritmo de Dijkstra
A continuación, se muestra un ejemplo de cómo implementar el algoritmo de Dijkstra en Java para encontrar el camino más corto entre dos nodos en un grafo ponderado:
import java.util.*;
public class DijkstraShortestPath {
public static Map<Integer, Integer> dijkstra(Map<Integer, List<int[]>> graph, int source, int destination) {
Map<Integer, Integer> distances = new HashMap<>();
PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> a[1] - b[1]);
// Initialize distances and add the source node to the priority queue
for (int node : graph.keySet()) {
distances.put(node, Integer.MAX_VALUE);
}
distances.put(source, 0);
pq.offer(new int[]{source, 0});
while (!pq.isEmpty()) {
int[] current = pq.poll();
int currentNode = current[0];
int currentDistance = current[1];
// If we've reached the destination, return the distances map
if (currentNode == destination) {
return distances;
}
// If the current distance is greater than the recorded distance, skip this node
if (currentDistance > distances.get(currentNode)) {
continue;
}
// Update the distances and add the neighbors to the priority queue
for (int[] neighbor : graph.get(currentNode)) {
int neighborNode = neighbor[0];
int neighborWeight = neighbor[1];
int totalDistance = currentDistance + neighborWeight;
if (totalDistance < distances.get(neighborNode)) {
distances.put(neighborNode, totalDistance);
pq.offer(new int[]{neighborNode, totalDistance});
}
}
}
return distances;
}
public static void main(String[] args) {
// Example usage
Map<Integer, List<int[]>> graph = new HashMap<>();
graph.put(1, new ArrayList<>(Arrays.asList(new int[]{2, 4}, new int[]{3, 2}, new int[]{4, 7})));
graph.put(2, new ArrayList<>(Arrays.asList(new int[]{1, 4}, new int[]{3, 3}, new int[]{4, 4}, new int[]{5, 5})));
graph.put(3, new ArrayList<>(Arrays.asList(new int[]{1, 2}, new int[]{2, 3}, new int[]{4, 3}, new int[]{5, 1})));
graph.put(4, new ArrayList<>(Arrays.asList(new int[]{1, 7}, new int[]{2, 4}, new int[]{3, 3}, new int[]{5, 2})));
graph.put(5, new ArrayList<>(Arrays.asList(new int[]{2, 5}, new int[]{3, 1}, new int[]{4, 2})));
Map<Integer, Integer> distances = dijkstra(graph, 1, 5);
System.out.println("Shortest distance from 1 to 5: " + distances.get(5));
}
}
Esta implementación utiliza una cola de prioridad para explorar eficientemente el grafo y actualizar las distancias más cortas. El método dijkstra() toma un grafo representado como un mapa de listas de adyacencia, un nodo fuente y un nodo destino, y devuelve un mapa de las distancias más cortas desde la fuente a todos los demás nodos.
Implementación de la búsqueda en amplitud (BFS, Breadth-First Search)
A continuación, se muestra un ejemplo de cómo implementar BFS en Java para encontrar el camino más corto entre dos nodos en un grafo no ponderado:
import java.util.*;
public class BreadthFirstSearch {
public static Map<Integer, Integer> bfs(Map<Integer, List<Integer>> graph, int source, int destination) {
Map<Integer, Integer> distances = new HashMap<>();
Queue<Integer> queue = new LinkedList<>();
// Initialize distances and add the source node to the queue
for (int node : graph.keySet()) {
distances.put(node, Integer.MAX_VALUE);
}
distances.put(source, 0);
queue.offer(source);
while (!queue.isEmpty()) {
int currentNode = queue.poll();
// If we've reached the destination, return the distances map
if (currentNode == destination) {
return distances;
}
// Explore the neighbors and update their distances
for (int neighbor : graph.get(currentNode)) {
if (distances.get(neighbor) == Integer.MAX_VALUE) {
distances.put(neighbor, distances.get(currentNode) + 1);
queue.offer(neighbor);
}
}
}
return distances;
}
public static void main(String[] args) {
// Example usage
Map<Integer, List<Integer>> graph = new HashMap<>();
graph.put(1, new ArrayList<>(Arrays.asList(2, 3, 4)));
graph.put(2, new ArrayList<>(Arrays.asList(1, 3, 5)));
graph.put(3, new ArrayList<>(Arrays.asList(1, 2, 4, 5)));
graph.put(4, new ArrayList<>(Arrays.asList(1, 3, 5)));
graph.put(5, new ArrayList<>(Arrays.asList(2, 3, 4)));
Map<Integer, Integer> distances = bfs(graph, 1, 5);
System.out.println("Shortest distance from 1 to 5: " + distances.get(5));
}
}
Esta implementación utiliza una cola para explorar el grafo de manera en amplitud. El método bfs() toma un grafo representado como un mapa de listas de adyacencia, un nodo fuente y un nodo destino, y devuelve un mapa de las distancias más cortas desde la fuente a todos los demás nodos.
Conclusión
En este tutorial, has aprendido cómo implementar dos algoritmos populares de camino más corto, el algoritmo de Dijkstra y la búsqueda en amplitud, en Java. Estos algoritmos se utilizan ampliamente en diversas aplicaciones y pueden ayudarte a encontrar los caminos más eficientes en tus problemas basados en grafos.
Recuerda elegir el algoritmo adecuado según los requisitos específicos de tu problema, como si el grafo es ponderado o no ponderado, y si necesitas encontrar el camino más corto entre una fuente única y todos los demás nodos o entre una fuente única y un destino único.
