Algoritmo de Dijkstra

Utilizado para grafos ponderados con pesos positivos sin ciclos. Pasos:

1. Inicializar matriz de adyacencia, arreglo de distancias desde el origen y arreglo de nodos visitados
2. Repetir para todos los nodos:
   1. Ancontrar nodo no visitado con mínima distancia
   2. Marcar como visitado
   3. Actualizar distancias de vecinos no visitados

Código C++

class Solucion {
public:
    int tiempoRed(vector<vector<int>>& conexiones, int n, int origen) {
        const int infinito = INT_MAX;
        vector<vector<int>> grafo(n+1, vector<int>(n+1, infinito));
        vector<int> distancias(n+1, infinito);
        vector<bool> procesado(n+1, false);
        int max_demora = 0;
        
        for (auto& c : conexiones) {
            grafo[c[0]][c[1]] = c[2];
        }
        for (int i = 1; i <= n; ++i) {
            grafo[i][i] = 0;
        }
        distancias[origen] = 0;
        
        for (int contador = 0; contador < n; ++contador) {
            int min_val = infinito;
            int nodo_actual = -1;
            
            for (int j = 1; j <= n; ++j) {
                if (!procesado[j] && distancias[j] < min_val) {
                    nodo_actual = j;
                    min_val = distancias[j];
                }
            }
            
            if (nodo_actual == -1) return -1;
            procesado[nodo_actual] = true;
            max_demora = max(max_demora, min_val);
            
            for (int vecino = 1; vecino <= n; ++vecino) {
                if (!procesado[vecino] && grafo[nodo_actual][vecino] != infinito) {
                    if (distancias[vecino] > distancias[nodo_actual] + grafo[nodo_actual][vecino]) {
                        distancias[vecino] = distancias[nodo_actual] + grafo[nodo_actual][vecino];
                    }
                }
            }
        }
        return max_demora;
    }
};

Código Python

import math

class Solucion:
    def tiempoRed(self, conexiones: List[List[int]], n: int, origen: int) -> int:
        grafo = [[math.inf] * (n+1) for _ in range(n+1)]
        distancias = [math.inf] * (n+1)
        procesado = [False] * (n+1)
        max_demora = 0
        
        for u, v, w in conexiones:
            grafo[u][v] = w
            
        for i in range(1, n+1):
            grafo[i][i] = 0
            
        distancias[origen] = 0
        
        for _ in range(n):
            min_val = math.inf
            nodo_actual = -1
            
            for j in range(1, n+1):
                if not procesado[j] and distancias[j] < min_val:
                    nodo_actual = j
                    min_val = distancias[j]
                    
            if nodo_actual == -1:
                return -1
                
            procesado[nodo_actual] = True
            max_demora = max(max_demora, min_val)
            
            for vecino in range(1, n+1):
                if not procesado[vecino] and grafo[nodo_actual][vecino] != math.inf:
                    nueva_dist = distancias[nodo_actual] + grafo[nodo_actual][vecino]
                    if nueva_dist < distancias[vecino]:
                        distancias[vecino] = nueva_dist
                        
        return max_demora

Algoritmo de Floyd

Calcula caminos mínimos entre todos los pares. Funciona con pesos negativos (sin ciclos negativos).

class Solucion {
public:
    int tiempoRed(vector<vector<int>>& conexiones, int n, int origen) {
        const int infinito = INT_MAX/2;
        vector<vector<int>> dp(n+1, vector<int>(n+1, infinito));
        
        for (auto& c : conexiones) {
            dp[c[0]][c[1]] = c[2];
        }
        for (int i = 1; i <= n; ++i) dp[i][i] = 0;
        
        for (int inter = 1; inter <= n; ++inter) {
            for (int i = 1; i <= n; ++i) {
                for (int j = 1; j <= n; ++j) {
                    if (dp[i][j] > dp[i][inter] + dp[inter][j]) {
                        dp[i][j] = dp[i][inter] + dp[inter][j];
                    }
                }
            }
        }
        
        int resultado = *max_element(dp[origen].begin()+1, dp[origen].end());
        return (resultado >= infinito) ? -1 : resultado;
    }
};

Código Python

class Solucion:
    def tiempoRed(self, conexiones: List[List[int]], n: int, origen: int) -> int:
        dp = [[10**9] * (n+1) for _ in range(n+1)]
        
        for i in range(1, n+1):
            dp[i][i] = 0
            
        for u, v, w in conexiones:
            dp[u][v] = w
            
        for inter in range(1, n+1):
            for i in range(1, n+1):
                for j in range(1, n+1):
                    if dp[i][j] > dp[i][inter] + dp[inter][j]:
                        dp[i][j] = dp[i][inter] + dp[inter][j]
                        
        max_demora = max(dp[origen][1:])
        return -1 if max_demora >= 10**9 else max_demora

Algoritmo de Bellman Ford

Maneja pesos negativos (sin ciclos negativos). Relaja aristas repetidamente.

class Solucion {
public:
    int tiempoRed(vector<vector<int>>& conexiones, int n, int origen) {
        vector<int> dist(n+1, INT_MAX);
        dist[origen] = 0;
        
        for (int i = 1; i < n; ++i) {
            for (auto& arista : conexiones) {
                int u = arista[0], v = arista[1], w = arista[2];
                if (dist[u] != INT_MAX && dist[u] + w < dist[v]) {
                    dist[v] = dist[u] + w;
                }
            }
        }
        
        int demora_max = *max_element(dist.begin()+1, dist.end());
        return (demora_max == INT_MAX) ? -1 : demora_max;
    }
};

Código Python

class Solucion:
    def tiempoRed(self, conexiones: List[List[int]], n: int, origen: int) -> int:
        dist = [10**9] * (n+1)
        dist[origen] = 0
        
        for _ in range(n-1):
            actualizado = False
            for u, v, w in conexiones:
                if dist[u] != 10**9 and dist[u] + w < dist[v]:
                    dist[v] = dist[u] + w
                    actualizado = True
            if not actualizado: break
                
        max_demora = max(dist[1:])
        return -1 if max_demora == 10**9 else max_demora