Caminho Mínimo 1: Algoritmo Floyd-Warshall

O algoritmo Floyd-Warshall é uma abordagem direta para encontrar os caminhos mínimos entre todos os pares de vértices em um grafo. Ele utiliza três laços aninhados para explorar todas as possíveis rotas passando por um ponto entermediário.

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]);

É importante tratar arestas múltiplas durante a leitura da antrada, mantendo apenas o valor mínimo para cada par de vértices.

int dist[N][N];

void solve() {
    memset(dist, 0x3f, sizeof dist);
    int n, m;
    cin >> n >> m;

    while (m--) {
        int u, v, w;
        cin >> u >> v >> w;
        dist[u][v] = min(dist[u][v], w);
        dist[v][u] = min(dist[v][u], w);
    }

    for (int i = 1; i <= n; ++i) dist[i][i] = 0;

    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 << '\n';
    }
}

Caminho Mínimo 2: Reponderação com Potencial e Dijkstra

Este problema envolve grafos com pesos negativos, exigindo uma transformação de pesos antes de aplicar Dijkstra. O processo consiste em:

1. Reponderação via SPFA: Adiciona um vértice fictício conectado a todos os outros com peso zero. Usa SPFA para calcular o potencial h[i] de cada vértice.
2. Atualização de pesos: Transforma cada aresta (u,v) com peso w para w + h[u] - h[v], garantindo não-negatividade.
3. Dijkstra com correção final: Executa Dijkstra em cada vértice e corrige o resultado final usando d[u][v] = d'[u][v] - h[u] + h[v].

struct Edge {
    int to;
    ll cost;
    bool operator<(const Edge &other) const {
        return cost == other.cost ? to < other.to : cost > other.cost;
    }
};

vector<edge> graph[N];
ll potential[N], dist[N];
bitset<n> visited;

bool spfa(int start) {
    fill(potential + 1, potential + n + 1, INF);
    queue<int> q;
    bitset<N> inQueue;
    vector<int> count(n + 1, 0);

    q.push(start);
    potential[start] = 0;
    inQueue[start] = true;

    while (!q.empty()) {
        int u = q.front(); q.pop();
        inQueue[u] = false;

        for (auto &e : graph[u]) {
            int v = e.to;
            ll newDist = potential[u] + e.cost;
            if (newDist < potential[v]) {
                if (++count[v] >= n) return true;
                potential[v] = newDist;
                if (!inQueue[v]) {
                    q.push(v);
                    inQueue[v] = true;
                }
            }
        }
    }
    return false;
}

void dijkstra(int src, ll *result) {
    fill(result + 1, result + n + 1, INF);
    priority_queue<Edge> pq;
    visited.reset();

    result[src] = 0;
    pq.push({src, 0});

    while (!pq.empty()) {
        Edge curr = pq.top(); pq.pop();
        int u = curr.to;

        if (visited[u]) continue;
        visited[u] = true;

        for (auto &e : graph[u]) {
            int v = e.to;
            ll newDist = result[u] + e.cost;
            if (newDist < result[v]) {
                result[v] = newDist;
                pq.push({v, newDist});
            }
        }
    }

    // Correção final
    for (int i = 1; i <= n; ++i)
        result[i] = result[i] - potential[src] + potential[i];
}

void solve() {
    cin >> n >> m;

    for (int i = 1; i <= m; ++i) {
        ll u, v, w;
        cin >> u >> v >> w;
        graph[u].push_back({v, w});
    }

    // Adiciona vértice fictício 0
    for (int i = 1; i <= n; ++i)
        graph[0].push_back({i, 0});

    if (spfa(0)) {
        cout << "Ciallo~" << '\n';
        return;
    }

    // Atualiza pesos das arestas
    for (int u = 1; u <= n; ++u)
        for (auto &e : graph[u])
            e.cost += potential[u] - potential[e.to];

    // Executa Dijkstra para cada origem
    for (int i = 1; i <= n; ++i)
        dijkstra(i, dist[i]);

    int q;
    cin >> q;
    while (q--) {
        int x, y;
        cin >> x >> y;
        if (dist[x][y] > INF / 2)
            cout << 114514 << '\n';
        else
            cout << dist[x][y] << '\n';
    }
}
</n></edge>

Caminho Mínimo 3: BFS com Contagem de Caminhos

Problema de contagem de caminhos mínimos em grafos não ponderados. Usa BFS para encontrar distância mínima do vértice inicial, enquanto conta quantos caminhos distintos levam a cada vértice.

int n, m;
ll dist[N], ways[N];
vector<int> adj[N];

void bfs(int start) {
    fill(dist + 1, dist + n + 1, INF);
    fill(ways + 1, ways + n + 1, 0);
    bitset<N> vis;
    queue<int> q;

    q.push(start);
    dist[start] = 0;
    ways[start] = 1;
    vis[start] = true;

    while (!q.empty()) {
        int u = q.front(); q.pop();
        for (int v : adj[u]) {
            if (!vis[v]) {
                q.push(v);
                vis[v] = true;
                dist[v] = dist[u] + 1;
                ways[v] = ways[u];
            } else if (dist[v] == dist[u] + 1) {
                ways[v] += ways[u];
            }
        }
    }
}

void solve() {
    cin >> n >> m;
    for (int i = 1; i <= m; ++i) {
        int u, v;
        cin >> u >> v;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }

    bfs(1);

    for (int i = 1; i <= n; ++i)
        cout << ways[i] << " \n"[i == n];
}