En esta sección exploraremos cómo analizar la complejidad de algoritmos en grafos, enfocándonos en los algoritmos de caminos más cortos, como BFS, Dijkstra y Floyd-Warshall.

✅ Objetivo:

• Entender cómo representar grafos en código.
• Analizar la complejidad de algoritmos en grafos.
• Implementar BFS, Dijkstra y Floyd-Warshall en Java, JavaScript, TypeScript y Python.

📌 1. Representación de Grafos

Un grafo es una estructura de datos formada por nodos (vértices) y conexiones (aristas).

📌 Ejemplo: Representar un grafo con lista de adyacencia

1import java.util.*;
2
3public class Graph {
4    private Map<Integer, List<Integer>> adjList = new HashMap<>();
5
6    public void addEdge(int u, int v) {
7        adjList.computeIfAbsent(u, k -> new ArrayList<>()).add(v);
8        adjList.computeIfAbsent(v, k -> new ArrayList<>()).add(u);
9    }
10
11    public List<Integer> getNeighbors(int node) {
12        return adjList.getOrDefault(node, new ArrayList<>());
13    }
14}

✅ Análisis:

• Espacio: O(V + E), donde V son los nodos y E las aristas.
• Acceder a vecinos: O(1), si el grafo está bien estructurado.

📌 2. Búsqueda en Grafos: BFS (O(V + E))

El BFS (Breadth-First Search) explora todos los nodos a la misma distancia antes de avanzar.

📌 Ejemplo: BFS para recorrer un grafo

1// Java - O(V + E) - BFS en un grafo
2import java.util.*;
3
4public class BFS {
5    public static void bfs(Graph graph, int start) {
6        Queue<Integer> queue = new LinkedList<>();
7        Set<Integer> visited = new HashSet<>();
8        queue.add(start);
9        visited.add(start);
10
11        while (!queue.isEmpty()) {
12            int node = queue.poll();
13            System.out.println(node);
14            for (int neighbor : graph.getNeighbors(node)) {
15                if (!visited.contains(neighbor)) {
16                    queue.add(neighbor);
17                    visited.add(neighbor);
18                }
19            }
20        }
21    }
22}

✅ Análisis:

• Complejidad Temporal: O(V + E), donde V son los nodos y E las aristas.
• Útil para encontrar caminos más cortos en grafos no ponderados.

📌 3. Dijkstra (O((V + E) log V))

El algoritmo de Dijkstra encuentra el camino más corto desde un nodo origen a todos los demás en un grafo con pesos positivos.

📌 Ejemplo: Implementación de Dijkstra

1// Java - O((V + E) log V) - Algoritmo de Dijkstra
2import java.util.*;
3
4public class Dijkstra {
5    public static Map<Integer, Integer> dijkstra(Map<Integer, List<int[]>> graph, int start) {
6        PriorityQueue<int[]> pq = new PriorityQueue<>(Comparator.comparingInt(a -> a[1]));
7        Map<Integer, Integer> distances = new HashMap<>();
8        pq.add(new int[]{start, 0});
9        distances.put(start, 0);
10
11        while (!pq.isEmpty()) {
12            int[] current = pq.poll();
13            int node = current[0], cost = current[1];
14
15            for (int[] neighbor : graph.getOrDefault(node, new ArrayList<>())) {
16                int nextNode = neighbor[0], weight = neighbor[1];
17                int newDist = cost + weight;
18                if (newDist < distances.getOrDefault(nextNode, Integer.MAX_VALUE)) {
19                    distances.put(nextNode, newDist);
20                    pq.add(new int[]{nextNode, newDist});
21                }
22            }
23        }
24        return distances;
25    }
26}

✅ Análisis:

• Complejidad Temporal: O((V + E) log V), porque usa una cola de prioridad.
• Útil para encontrar caminos mínimos en grafos con pesos positivos.

📌 4. Floyd-Warshall (O(V³))

El algoritmo Floyd-Warshall encuentra todos los caminos más cortos entre todos los pares de nodos en un grafo con pesos positivos o negativos.

📌 Ejemplo: Implementación de Floyd-Warshall

1// Java - O(V³) - Algoritmo Floyd-Warshall
2public class FloydWarshall {
3    public static int[][] floydWarshall(int[][] graph) {
4        int n = graph.length;
5        int[][] dist = new int[n][n];
6        for (int i = 0; i < n; i++) {
7            System.arraycopy(graph[i], 0, dist[i], 0, n);
8        }
9
10        for (int k = 0; k < n; k++) {
11            for (int i = 0; i < n; i++) {
12                for (int j = 0; j < n; j++) {
13                    if (dist[i][k] != Integer.MAX_VALUE && dist[k][j] != Integer.MAX_VALUE) {
14                        dist[i][j] = Math.min(dist[i][j], dist[i][k] + dist[k][j]);
15                    }
16                }
17            }
18        }
19        return dist;
20    }
21}

✅ Análisis:

• Complejidad Temporal: O(V³), ya que revisa todos los pares de nodos.
• **Útil para encontrar caminos más cortos entre todos los nodos.

📌 5. Comparación de Algoritmos de Caminos Más Cortos

📌 Conclusión:

• BFS es ideal para caminos sin peso.
• Dijkstra es eficiente en grafos grandes con pesos positivos.
• Floyd-Warshall se usa en grafos pequeños cuando queremos todas las distancias.