O cálculo do caminho mais curto entre vértices é um dos problemas fundamentais na teoria dos grafos. Diferentes algoritmos oferecem vantagens específicas dependendo da estrutura do grafo, como a presença de pesos negativos, densidade de arestas ou a necessidade de processamento em tempo real. Abaixo estão abordagens modernizadas em C++ utilizando a biblioteca padrão (STL) para resolver o problema clássico de caminho mínimo em grafos não direcionados.
Dijkstra Ingênuo com Lista de Adjacência
A abordagem clássica do algoritmo de Dijkstra baseia-se em uma estratégia gulosa. A cada iteração, o vértice não visitado com a menor distância acumulada é selecionado, garantindo que as relaxações subsequentes partam do caminho mínimo atual. O uso de listas de adjacência otimiza a memória em grafos esparsos.
#include <iostream>
#include <vector>
#include <limits>
using namespace std;
struct Aresta {
int destino;
int peso;
};
const int INF = 1e9;
int num_vertices, num_arestas, origem, destino;
vector<vector<Aresta>> grafo;
int dijkstra_lista() {
vector<int> distancia(num_vertices + 1, INF);
vector<bool> processado(num_vertices + 1, false);
distancia[origem] = 0;
for (int iteracao = 0; iteracao < num_vertices; ++iteracao) {
int atual = -1;
for (int i = 1; i <= num_vertices; ++i) {
if (!processado[i] && (atual == -1 || distancia[i] < distancia[atual])) {
atual = i;
}
}
if (atual == -1) break;
processado[atual] = true;
for (const auto& aresta : grafo[atual]) {
if (distancia[aresta.destino] > distancia[atual] + aresta.peso) {
distancia[aresta.destino] = distancia[atual] + aresta.peso;
}
}
}
return distancia[destino];
}
int main() {
cin >> num_vertices >> num_arestas >> origem >> destino;
grafo.resize(num_vertices + 1);
for (int i = 0; i < num_arestas; ++i) {
int u, v, w;
cin >> u >> v >> w;
grafo[u].push_back({v, w});
grafo[v].push_back({u, w});
}
cout << dijkstra_lista() << endl;
return 0;
}
Dijkstra Ingênuo com Matriz de Adjacência
Para grafos densos, a representação por matriz de adjacência permite acesso direto $O(1)$ ao peso das arestas. A lógica de seleção do vértice mais próximo permanece inalterada, mas o relaxamento itera sobre todos os vértices possíveis.
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
const int INF = 1e9;
int main() {
int n, m, start_node, end_node;
cin >> n >> m >> start_node >> end_node;
vector<vector<int>> matriz(n + 1, vector<int>(n + 1, INF));
vector<int> dist(n + 1, INF);
vector<bool> visitado(n + 1, false);
for (int i = 0; i < m; ++i) {
int u, v, peso;
cin >> u >> v >> peso;
matriz[u][v] = min(matriz[u][v], peso);
matriz[v][u] = min(matriz[v][u], peso);
}
dist[start_node] = 0;
for (int step = 0; step < n; ++step) {
int atual = -1;
for (int i = 1; i <= n; ++i) {
if (!visitado[i] && (atual == -1 || dist[i] < dist[atual])) {
atual = i;
}
}
visitado[atual] = true;
for (int i = 1; i <= n; ++i) {
if (matriz[atual][i] != INF) {
dist[i] = min(dist[i], dist[atual] + matriz[atual][i]);
}
}
}
cout << dist[end_node] << endl;
return 0;
}
Dijkstra Otimizado com Fila de Prioridade (Min-Heap)
A busca linear pelo vértice de menor distância na versão ingênua resulta em complexidade $O(V^2)$. Utilizando uma estrutura de dados de fila de prioridade, o tempo de extração cai para $O(\log V)$, tornando o algoritmo altamente eficiente para grafos esparsos.
#include <iostream>
#include <vector>
#include <queue>
using namespace std;
struct No {
int id;
int distancia;
bool operator>(const No& outro) const {
return distancia > outro.distancia;
}
};
const int INF = 1e9;
int main() {
int n, m, origem, destino;
cin >> n >> m >> origem >> destino;
vector<vector<pair<int, int>>> adj(n + 1);
for (int i = 0; i < m; ++i) {
int u, v, w;
cin >> u >> v >> w;
adj[u].push_back({v, w});
adj[v].push_back({u, w});
}
vector<int> dist(n + 1, INF);
vector<bool> fechado(n + 1, false);
priority_queue<No, vector<No>, greater<No>> pq;
dist[origem] = 0;
pq.push({origem, 0});
while (!pq.empty()) {
int u = pq.top().id;
int d = pq.top().distancia;
pq.pop();
if (fechado[u]) continue;
fechado[u] = true;
for (const auto& vizinho : adj[u]) {
int v = vizinho.first;
int peso = vizinho.second;
if (dist[v] > d + peso) {
dist[v] = d + peso;
pq.push({v, dist[v]});
}
}
}
cout << dist[destino] << endl;
return 0;
}
Algoritmo SPFA (Sohrtest Path Faster Algorithm)
O SPFA é uma otimização do algoritmo de Bellman-Ford que utiliza uma fila para processar apenas os vértices cujas distâncias foram atualizadas na iteração anterior. Se um vértice já está na fila, ele não é inserido novamente, evitando processamento redundante.
#include <iostream>
#include <vector>
#include <queue>
using namespace std;
const int INF = 1e9;
int main() {
int n, m, start, target;
cin >> n >> m >> start >> target;
vector<vector<pair<int, int>>> grafo(n + 1);
for (int i = 0; i < m; ++i) {
int u, v, w;
cin >> u >> v >> w;
grafo[u].push_back({v, w});
grafo[v].push_back({u, w});
}
vector<int> dist(n + 1, INF);
vector<bool> na_fila(n + 1, false);
queue<int> q;
dist[start] = 0;
q.push(start);
na_fila[start] = true;
while (!q.empty()) {
int atual = q.front();
q.pop();
na_fila[atual] = false;
for (const auto& aresta : grafo[atual]) {
int proximo = aresta.first;
int custo = aresta.second;
if (dist[proximo] > dist[atual] + custo) {
dist[proximo] = dist[atual] + custo;
if (!na_fila[proximo]) {
q.push(proximo);
na_fila[proximo] = true;
}
}
}
}
cout << dist[target] << endl;
return 0;
}
Algoritmo de Bellman-Ford
O Bellman-Ford relaxa todas as arestas do grafo $V-1$ vezes. Uma característica importante desta implementação é o uso de um vetor de backup (cópia do estado anterior), o que é obrigatório em variações do problema onde existe um limite estrito no número de arestas percorridas, impedindo atualizações em cascata na mesma iteração.
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
struct Caminho {
int origem, destino, peso;
};
const int INF = 1e9;
int main() {
int n, m, inicio, fim;
cin >> n >> m >> inicio >> fim;
vector<Caminho> arestas;
for (int i = 0; i < m; ++i) {
int u, v, w;
cin >> u >> v >> w;
arestas.push_back({u, v, w});
arestas.push_back({v, u, w}); // Grafo não direcionado
}
vector<int> dist(n + 1, INF);
dist[inicio] = 0;
for (int i = 0; i < n; ++i) {
vector<int> backup = dist;
for (const auto& aresta : arestas) {
if (backup[aresta.origem] != INF) {
dist[aresta.destino] = min(dist[aresta.destino], backup[aresta.origem] + aresta.peso);
}
}
}
cout << dist[fim] << endl;
return 0;
}
Algoritmo de Floyd-Warshall
Baseado em programação dinâmica, o algoritmo de Floyd-Warshall calcula os caminhos mínimos entre todos os pares de vértices. Sua complexidade cúbica $O(V^3)$ o torna ideal para grafos com um número reduzido de vértices onde múltiplas consultas de distância serão realizadas.
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
const int INF = 1e9;
int main() {
int n, m, consulta_u, consulta_v;
cin >> n >> m >> consulta_u >> consulta_v;
vector<vector<int>> dist(n + 1, vector<int>(n + 1, INF));
for (int i = 1; i <= n; ++i) {
dist[i][i] = 0;
}
for (int i = 0; i < m; ++i) {
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 k = 1; k <= n; ++k) {
for (int i = 1; i <= n; ++i) {
for (int j = 1; j <= n; ++j) {
if (dist[i][k] != INF && dist[k][j] != INF) {
dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]);
}
}
}
}
cout << dist[consulta_u][consulta_v] << endl;
return 0;
}