A simple graph trick to solve some SSSP problems
Estas são notas que acompanham a oficina que ministrei recentemente no Clube de Programação da UTFPR. Nela, eu apresentei o algoritmo de Dijkstra e um truque simples mas útil para resolver problemas no contexto de programação competitiva.
Como o truque é simples, não faz mal adicionar a explicação do algoritmo de Dijkstra, mas você pode consultá-la em outros lugares como o CP-Algorithms. Os problemas apresentados serão três, sendo que os dois primeiros têm soluções mais simples (mas servem para motivos didáticos).
Os termos distância, peso e custo são usados sem distinção. Neste texto não há nenhum rigor relacionado a notação.
Nos três problemas nós usaremos o algoritmo de Dijkstra, então antes de irmos ao truque (e às soluções) vamos ver este algoritmo em detalhe.
O algoritmo de Dijkstra resolve o problema de caminhos mínimos com origem única (Single-Source Shortest Paths, SSSP) para grafos com arcos de peso não-negativo. Neste problema, dado um vértice de origem, o objetivo é encontrar a menor distância para cada um dos outros vértices num caminho que começa na origem.
Para as explicações a seguir, vamos fixar a origem no vértice $1$.
A ideia intuitiva do algoritmo é: dado um vértice $u$ que com certeza tem caminho mínimo $w$, para cada arco $(u, v)$, é possível que o menor caminho de $v$ tenha custo $w+E_{u,v}$. Isso equivaleria a dizer que o caminho mínimo de $v$ passa pelo arco $(u, v)$. Posto de outra forma: para cada vértice com caminho mínimo definido, vamos tentar descobrir um novo menor caminho para seus vizinhos.
Vamos guardar duas informações para cada vértice $v$: se ele já foi processado e qual a menor distância conhecida de $1$ até ele ($d_v$). Inicialmente, $d_1 = 0$ e $d_v = \infty \; \forall v \neq 1$.
Para cada passo do algoritmo, vamos escolher o vértice $v$ com o menor $d_v$ entre aqueles que não foram processados ainda, e então processá-lo. Processar um vértice $v$ consiste em relaxar todos os arcos $(v, u)$ com a ideia apresentada na seção anterior: $d_u = \min(d_u, d_v+E_{v,u})$.
É fácil ver que cada vértice só é processado uma vez, porque só processaremos um vértice que não foi processado. Mas por que é garantido que, ao processar um vértice, já temos o menor valor possível de $d_v$?
Digamos que seja possível que, após processar o vértice $v$, relaxemos algum arco que diminua o valor $d_v$.
Se houvesse arcos negativos, poderia acontecer de inserirmos $v$ num ciclo com soma negativa, e aí seria possível tornar $d_v = -\infty$ (veja o grafo abaixo). No nosso problema, não há arcos negativos.
Como não há arcos negativos, o único jeito é se encontrarmos algum vértice $u$ com $d_u < d_v$, onde há um caminho de $u$ até $v$ com peso $x$ tal que $d_u + x < d_v$. No entanto, como processamos sempre o vértice com menor distância primeiro, e como $d_u < d_v$, nós teríamos processado $u$ antes de $v$.
Portanto, ao processar o vértice $v$, já conhecemos o menor valor possível para $d_v$.
Agora, qual será a complexidade desse algoritmo? Começaremos por algumas observações.
Cada vértice é processado apenas uma vez, porque não processamos vértices que já foram processados. Isso implica em um termo $\mathcal{O}(n)$ em algum lugar na complexidade final.
Nós relaxaremos um arco $(u, v)$ sempre que processarmos o vértice de origem $u$, ou seja, uma vez. Isso implica em um termo $+\mathcal{O}(m)$ em algum lugar na complexidade final (separado do termo anterior).
Ignorando as complexidades de escolher o próximo vértice a processar e de relaxar um arco, temos uma complexidade de $\mathcal{O}(n+m)$.
Em grafos densos, o número de arcos é próximo do máximo ($\mathcal{O}(n^2)$). Se guardamos em um vetor booleano $m$ quais vértices já foram processados, podemos a cada iteração do algoritmo buscar o próximo vértice a ser processado em $\mathcal{O}(n)$, relaxando cada arco em $\mathcal{O}(1)$. Isso significa uma complexidade $\mathcal{O}(n^2 + m) = \mathcal{O}(n^2)$. Para grafos densos, essa complexidade é ótima. Abaixo deixo uma implementação do algoritmo nesse caso:
using ii = pair<int, int>;
vector<int> dijkstra(int s, vector<vector<ii>> &g) {
const int n = g.size();
vector<int> d(n+1, 0x3f3f3f3f), m(n+1);
d[s] = 0;
for (int i = 0; i < n; ++i) {
// escolhe o próximo
int v = 0;
for (int j = 1; j < n; ++j)
if (!m[j] && (m[v] || d[v] > d[j]))
v = j;
// processa
m[v] = 1;
for (auto [x, u]: g[v])
// relaxa arco (v, u)
d[u] = min(d[u], d[v]+x);
}
return d;
}
Quando o número de arcos é muito menor que o máximo possível, existe uma variação com desempenho melhor. O que vamos fazer é usar uma estrutura que permita inserção de valores e remoção de mínimo em tempo logarítmico, e guardar nela pares $(d_v, v)$.
A melhoria dessa variação é que a seleção do próximo vértice a processar terá custo logarítmico, já que basta selecionar o menor par na estrutura.
Ao mesmo tempo, relaxar um arco deixará de ser constante, porque ao encontrar um peso menor para o vértice $u$ nós teremos de adicioná-lo à estrutura em tempo logarítmico.
Com essa alteração, a complexidade do algoritmo passa a ser $\mathcal{O}(n\log n + m\log n)$, que é muito melhor que a anterior no caso de grafos esparsos.
A implementação abaixo usa uma fila de prioridade, mas outras estruturas apresentam a mesma complexidade. Com uma fibonacci heap é possível atingir tempo constante na inserção e logarítmico na remoção, mas como ela é muito mais difícil de implementar, não é tão adequada para programação competitiva.
using ii = pair<int, int>;
vector<int> dijkstra(int s, vector<vector<ii>> &g) {
const int n = g.size();
vector<int> d(n+1, 0x3f3f3f3f);
priority_queue<ii, vector<ii>, greater<ii>> pq;
pq.emplace(d[s]=0, s);
while (pq.size()) {
// escolhe o próximo
auto [w, v] = pq.top(); pq.pop();
if (w != d[v]) // descarta pares desatualizados
continue;
// processa
for (auto [x, u]: g[v])
// relaxa arco (v, u)
if (d[u] > w+x)
pq.emplace(d[u]=(w+x), u);
}
return d;
}
Agora vamos ao truque que é o ponto central disso tudo. É uma técnica de modelagem bem simples, que só merece um nome porque essa página precisava de um título.
A técnica consiste em duplicar o grafo, fazendo com que cada vértice e arco tenha uma versão “original” e uma “modificada”. A modificação depende do problema.
Além dos vértices e arcos duplicados, existirão arcos de transição entre o “grafo original” e o “grafo duplicado”. Isso vai fazer mais sentido quando olharmos para os problemas, mas essencialmente esses arcos de transição representam decisões irreversíveis sobre a maneira como se caminha no grafo: a versão duplicada do grafo é onde você caminha depois de tomar essas decisões.
Esse é o problema mais simples, com uma solução muito mais simples que essa, mas é bem fácil de pensar com esse truque. Aqui, a versão duplicada do grafo vai ser igual ao grafo original, e os arcos de transição serão os arcos com o desconto aplicado. Dessa maneira, o desconto só poderá ser aplicado uma vez em um caminho pelo grafo, porque não existem arcos de retorno para a parte original.
Considere este grafo de exemplo:
Com o truque aplicado, teríamos o grafo abaixo. A parte de cima é idêntica ao grafo original, bem como a parte de baixo. Os arcos que levam de cima para baixo correspondem ao desconto aplicado. Note que não há arcos de baixo para cima.
A implementação dessa solução é muito simples. O código do Dijkstra é o mesmo, e a construção do grafo é levemente diferente:
for (int i = 0; i < m; ++i) {
int a, b, c;
cin >> a >> b >> c;
g[a].emplace_back(c, b); // arco conforme na entrada
g[a+n].emplace_back(c, b+n); // arco duplicado (parte de "baixo" do grafo)
g[a].emplace_back(c/2, b+n); // arco de transição (desconto)
}
Neste código, nós reservamos os vértices $1 \leq v \leq n$ para o grafo “original”, e os vértices $n+1 \leq v^{\prime} \leq 2n$ para o grafo duplicado.
A ideia aqui é muito parecida com a do problema anterior. Dessa vez os arcos de transição terão custo $0$, mas os pesos dos arcos serão diferentes dependendo de em qual parte do grafo você está. O grafo original corresponde ao prefixo do caminho, que é de carro, e o grafo duplicado corresponde ao sufixo, que é de trem.
for (int i = 0; i < n; ++i)
for (int j = 0; j < n; ++j) {
int d;
cin >> d;
g[i].emplace_back(d*a, j); // custo de carro: A*D(i,j)
g[i].emplace_back(0, i+n); // transição: custo 0
g[i+n].emplace_back(d*b+c, j+n); // custo de trem: B*D(i,j) + C
}
Neste problema vamos usar uma ideia mais complicada, mas ainda baseada no truque do grafo duplicado. A primeira coisa que queremos ignorar na nossa modelagem é que tem dois objetos distintos se movendo.
Observe que, em termos de custo, a mão esquerda e a mão direita se encontrarem num ponto X é a mesma coisa que a mão esquerda fazer o mesmo caminho até o ponto X, depois fazer o caminho contrário da mão direita até o ponto de origem desta.
Isto é, no caminho ótimo para as duas mãos se encontrarem (nesta visualização na qual a mão direita não se move), a mão esquerda vai caminhar pelo grafo normalmente até um ponto arbitrário do caminho, e então passará a caminhar pelo grafo com arcos invertidos pelo resto do caminho.
Agora a modelagem com o truque fica praticamente pronta: o grafo duplicado será o grafo transposto, e os arcos de transição levarão cada vértice $v$ ao vértice $v^{\prime}$ com custo $0$.
Construção do grafo:
for (int i = 0; i < n; ++i)
g[i].emplace_back(0, i);
while (m--) {
int u, v, w;
cin >> u >> v >> w;
u--, v--;
g[u].emplace_back(w, v);
g[v].emplace_back(w, u);
}
Note que para encontrar a menor distância até um vértice $v$, em qualquer um dos problemas mencionados, você deverá selecionar a distância mínima entre $d_v$ e $d_{v^{\prime}}$.
É isso! Esse foi o truque. Apesar de ser bem simples eu achei que seria algo acessível para as pessoas mais novas em programação competitiva, então escolhi esse tema para a oficina.
Se houver qualquer dúvida não hesite em entrar em contato comigo.