Camino Más Corto de Fuente Única

Algoritmo de Dijkstra (solo para aristas con pesos positivos, fuente única)

Su lógica se puede entender como ir al nodo más cercano actualmente alcanzable que aún no hemos determinado si es la ruta más corta, y encotnrar su camino más corto.

Leemos todas las aristas y sus pesos, luego inicializamos todas las distancias desde los nodos hasta el inicio como infinitas, excepto el nodo inicio que es 0.

Ver código``` int n, m, inicio, destino; cin >> n >> m >> inicio >> destino; for(int i = 1; i <= m; i++){ int u, v, peso; cin >> u >> v >> peso; grafo[u][v] = peso; grafo[v][u] = peso; } memset(distancia, 0x3f, sizeof(distancia)); distancia[inicio] = 0; // Ahora continuamente actualizamos distancias más cortas for(int i = 1; i <= n; i++){ int nodo_actual = -1; for(int j = 1; j <= n; j++){ if(!visitado[j]){ if(nodo_actual == -1) nodo_actual = j; else{ if(distancia[nodo_actual] > distancia[j]) nodo_actual = j; } } } visitado[nodo_actual] = 1; for(int j = 1; j <= n; j++){ if(grafo[nodo_actual][j] > 0) { distancia[j] = min(distancia[j], distancia[nodo_actual] + grafo[nodo_actual][j]); } } }

Este método utiliza una matriz de adyacencia, lo cual es ineficiente para n=1e5. Por lo tanto, optimizamos con una estructura de heap y almacenamos el grafo usando vectores.

Ver código```
#define PII pair<int, int>
int distancia[100010];
vector<PII> grafo[100010];
bool visitado[100010];

void dijkstra(int inicio){
    memset(distancia, 0x3f, sizeof(distancia));
    distancia[inicio] = 0;
    priority_queue<PII, vector<PII>, greater<PII>> cola;
    cola.push({0, inicio});
    while(!cola.empty()){
        auto [dist, nodo] = cola.top();
        cola.pop();
        if(visitado[nodo]){
            continue;
        }
        visitado[nodo] = true;
        for(auto [vecino, peso] : grafo[nodo]){
            if(distancia[vecino] > distancia[nodo] + peso){
                distancia[vecino] = distancia[nodo] + peso;
                cola.push({distancia[vecino], vecino});
            }
        }
    }
}
void resolver() {
    int n, m, inicio;
    cin >> n >> m >> inicio;
    for(int i = 1; i <= m; i++){
        int a, b, c;
        cin >> a >> b >> c;
        grafo[a].push_back({b, c});
    }
    dijkstra(inicio);
    for(int i = 1; i <= n; i++){
        cout << distancia[i] << " ";
    }
    return;
}

La primera optimización consiste en usar un vector de pares para almacenar el grafo y, durante la búsqueda, utilizar una estructura de heap optimizada. Colocamos el array de distancias en la primera dimensión para ordenar, de modo que el primer elemento encontrado sea la arista más corta. El resto del proceso es similar a la búsqueda anterior.

Camino Más Corto Múltiples Fuentes

Algoritmo Floyd

Este algoritmo de camino más corto se basa en la idea de programación dinámica, actualizando continuamente la distancia más corta entre nodos i y j.

Ver código``` int dist[110][110]; void resolver() { int n, m; cin >> n >> m;

memset(dist, 0x3f, sizeof(dist));
for(int i = 1; i <= n; i++){
    dist[i][i] = 0;
}
for(int i = 1; i <= m; i++){
    int a, b, c;
    cin >> a >> b >> c;
    dist[a][b] = min(dist[a][b], c);
    dist[b][a] = min(dist[b][a], c);
}
for(int k = 1; k <= n; k++){
    for(int i = 1; i <= n; i++){
        for(int j = 1; j <= n; j++){
            dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]);
        }
    }
}
for(int i = 1; i <= n; i++){
    for(int j = 1; j <= n; j++){
        cout << dist[i][j] << " ";
    }
    cout << endl;
}
return;

}