Aula - Dijkstra com Vértices Auxiliares

Aula por Enzo Dantas

Nessa aula nós vamos falar sobre a ideia conhecida como "vértices auxiliares". Essa ideia é utilizada para resolver problemas de menor caminho com alguma condição adicional. A ideia consiste em adicionar estados aos vértices para reprentar tal condição extra e, de certa forma, construir um novo grafo que servirá para achar a resposta que queremos.

Problema 1

Flight Discount

Dado um grafo direcionado e com pesos, diga o menor caminho entre os vértices $1$ e $N$ com a condição de que você possui um cupom de desconto, o qual divide por dois (arredondado para baixo) o custo de qualquer aresta.

Para resolver esse problema, imagine um grafo qualquer. Em um Dijkstra comum, cada vértice possui um distância mínima para ser alcançado e so é processado uma vez. Como levar em conta a condição do cupom? Como testar se eu devo usar ou não o cupom em uma certa aresta? A ideia aqui é olhar para o cupom como uma condição dos vértices em vez de uma condição das arestas. Adicionaremos um novo estado para o array $dist$: em vez de usar o array $dist[N]$ normal, usaremos um array $dist[N][2]$, onde $dist[u][0]$ guarda a menor distância para chegar em $u$ sem usar cupons e $dist[u][1]$ guarda a menor distância para chegar em $u$ já tendo usado um cupom. Pensando no código do algoritmo, é fácil imaginar quais modificações seriam feitas: se estamos em um certo vértice $u$ e estamos olhando para uma aresta $u \rightarrow v$ que tem peso $w$, temos dois casos:

1. Se já usamos um cupom para chegar em $u$, então dizemos que uma possível distância para $v$ já tendo usado um cupom é $dist[u][1] + w$.
2. Caso ainda não tenhamos usado o cupom, dizemos que uma possível distância para $v$ sem ter usado o cupom é $dist[u][0] + w$, e uma possível distância para $v$ tendo usado o cupom é usando o cupom nessa aresta, ou seja, $dist[u][1] + \lfloor \frac{w}{2} \rfloor$.

Uma maneira de visualizar essa ideia, o que é útil para entender porque ela funciona, é imaginar cada estado do array $dist$ como um vértice separado e imaginar as arestas que são criadas. Consequentemente, estaremos visualizando um novo grafo.

Observe o grafo a seguir:

Imaginando o novo grafo, chegamos no seguinte:

Com esse novo grafo em mente, perceba que basta rodar um Dijkstra comum nele para achar a resposta que queremos. Segue a implementação do algoritmo discutido acima.

Mas esse problema possui apenas dois estados para cada vértice. Será que há como tornar essa ideia mais interessante?

Problema 2

2a fase OBI 2022

Dado um grafo com $N \le 10^4$ vértices e arestas bidirecionais, cada uma com um custo $C_i$ e um tempo $T_i$, diga o caminho de menor tempo com custo menor ou igual a $S \le 200$ entre os vértices $inicio$ e $fim$.

Como utilizar a ideia de vértices auxiliares aqui? Qual condição podemos adicionar a um vértice / qual estado podemos adicionar ao array $dist$? Observando que $S$ é pequeno, criaremos o array $dist[N][S]$. Ou seja, guardaremos o menor tempo para chegar em um vértice com um certo custo. Formalmente, $dist[u][c]$ guarda o menor tempo para chegar no vértice $u$ com custo igual a $c$. Para a transição de um vértice para outro, partindo de um vértice $(u, c)$ é possível chegar no vértice $(v, c+C_i)$ com tempo $dist(u, c)+T_i$, sendo respectivamente $C_i$ e $T_i$ o custo e tempo da aresta $u \rightarrow v$.

Novamente, é interessante imaginar o grafo auxiliar para compreender a ideia mais aprofundadamente. Note que, apesar de um mesmo vértice poder ser processado várias (uma vez com distância 1, outra com distância 2, outras com distância até D), cada vértice do grafo auxiliar é processado apenas uma vez. Esse detalhe é importante para conseguir calcular a complexidade do algoritmo.

 

Abaixo estão alguns problemas selecionados pela equipe NOIC que exploram aplicações diversas e interessantes da ideia de vértices auxiliares.

Problemas para praticar

(Fácil) Relógios

(Fácil) Paired Payment

(Fácil) Fine Dining

(Fácil) Milk Pumping

(Médio) Delivery Cost

(Médio) Flight Routes

(Difícil) Quarrel

(Difícil) Tesouro do TurTur

(Muito Difícil) Commuter Pass