Nesse post vamos falar do problema 11011. Desafio cartográfico. De modo resumido o problema pede que dado um mapa de cidades ligadas por estradas, determine a distância entre o par de cidades mais distantes.
O problema pede basicamente o diâmetro do grafo onde as cidades representam os vértices e as estradas as arestas.
Achar o diâmetro de um grafo qualquer não é um problema tão simples. Entretando, observando as outras restrições dadas no enunciado podemos simplificar nosso problema:
(a) todas as estradas são de mão dupla;
(b) todas as estradas possuem 1km de comprimento;
(c) toda estrada conecta apenas duas cidades,
(d) dadas duas cidades quaisquer A e B, só existe uma única maneira de chegar em A partindo de B, e vice-versa.
Ou seja, nosso grafo sempre será uma árvore, e calcular o diâmetro de uma árvore é um problema bem mais simples.
O diâmetro de um grafo (que no nosso caso é uma árvore) é o maior caminho mínimo do grafo. A solução mais ingênua para esse problema seria calcular todas as distâncias entre todas as folhas do grafo e escolher a maior delas. Entretanto podemos fazer muito melhor que isso. Para tanto, observe que:
O vértice mais distante de um vértice u qualquer do grafo é uma das extremidades do diâmetro do grafo.
Para simplificar, e sem perda de generalidade, vamos supor que o diâmetro do grafo é único. Ou seja, existe exatamente um par de vértices {u, v}, tal que o comprimento do caminho mínimo entre u e v seja o maior do grafo. É fácil de ver que tanto u, quanto v são folhas do grafo.
Pegue qualquer nó w, vamos mostrar (por contradição) que o vértice mais distante dele é u ou v. Suponha que o vértice encontrado é diferente, digamos z. Vamos considerar dois casos.
Primeiro suponha que w esteja no caminho de u para v. Sem perda de generalidade, suponha que o caminho wu não têm sobreposição com o caminho wz. Temos:
dist(w, z) ≥ dist(w, v). Mas sabemos que dist(w, z) ≥ dist(w, u).
dist(u, z) = dist(u, w) + dist(w, z) ≥ dist(u, w) + dist(w, v) = dist(u, v). Isto contradiz a suposição de que d(u, v) é o diâmetro original da árvore.
Suponha agora que w não esteja sobre o caminho de u para v. Temos que ou o caminho wz se sobrepõe com o caminho uv ou está separado.
Caso existe sobreposição:
Considere o vértice y mais próximo de W e sobre a sobreposição dos caminhos. Sem perda de Assim, dist(y, z) ≥ dist(y, v).
Como dist(u, z) = dist(u, y) + dist(y, z) ≥ dist(u, y) + dist(y, v) = dist(u, v). O que leva novamente a uma contradição já que por hipotese {u, v} é o diâmetro original da árvore.
Se os caminhos não se sobrepõem, tem que haver dois vértices um no caminho uv e outro no caminho wz que são os mais próximos, sejam estes vértices x e y. Assim dist(u, z) = dist(u, y) + dist(y, z) ≥ dist(u, y) + dist(y, v) > dist(u, x) + dist(x, v) = dist(u, v). Daí a suposição de que {u, v} é o diâmetro é contrariada.
cqd.
Desse modo, o cálculo do diâmetro de uma árvore pode ser feito usando-se duas buscas em profundidade (ou em largura), uma delas (partindo de qualquer vértice) para achar o vértice mais distante, que será uma das extremidades (u ou v) do diâmetro. E a outra partindo-se do vértice encontrado (u ou v) para se calcular efetivamente o diâmetro do grafo.
Tanto a busca em profundidade quanto em largura têm complexidade O(E), sendo E o número de arestas do grafo.
O código abaixo implementa a solução apresentada acima.
Modelagem da Solução
O problema pede basicamente o diâmetro do grafo onde as cidades representam os vértices e as estradas as arestas.
Achar o diâmetro de um grafo qualquer não é um problema tão simples. Entretando, observando as outras restrições dadas no enunciado podemos simplificar nosso problema:
(a) todas as estradas são de mão dupla;
(b) todas as estradas possuem 1km de comprimento;
(c) toda estrada conecta apenas duas cidades,
(d) dadas duas cidades quaisquer A e B, só existe uma única maneira de chegar em A partindo de B, e vice-versa.
Ou seja, nosso grafo sempre será uma árvore, e calcular o diâmetro de uma árvore é um problema bem mais simples.
Diâmetro de uma Árvore
O diâmetro de um grafo (que no nosso caso é uma árvore) é o maior caminho mínimo do grafo. A solução mais ingênua para esse problema seria calcular todas as distâncias entre todas as folhas do grafo e escolher a maior delas. Entretanto podemos fazer muito melhor que isso. Para tanto, observe que:
O vértice mais distante de um vértice u qualquer do grafo é uma das extremidades do diâmetro do grafo.
Para simplificar, e sem perda de generalidade, vamos supor que o diâmetro do grafo é único. Ou seja, existe exatamente um par de vértices {u, v}, tal que o comprimento do caminho mínimo entre u e v seja o maior do grafo. É fácil de ver que tanto u, quanto v são folhas do grafo.
Pegue qualquer nó w, vamos mostrar (por contradição) que o vértice mais distante dele é u ou v. Suponha que o vértice encontrado é diferente, digamos z. Vamos considerar dois casos.
Primeiro suponha que w esteja no caminho de u para v. Sem perda de generalidade, suponha que o caminho wu não têm sobreposição com o caminho wz. Temos:
dist(w, z) ≥ dist(w, v). Mas sabemos que dist(w, z) ≥ dist(w, u).
dist(u, z) = dist(u, w) + dist(w, z) ≥ dist(u, w) + dist(w, v) = dist(u, v). Isto contradiz a suposição de que d(u, v) é o diâmetro original da árvore.
Suponha agora que w não esteja sobre o caminho de u para v. Temos que ou o caminho wz se sobrepõe com o caminho uv ou está separado.
Caso existe sobreposição:
Considere o vértice y mais próximo de W e sobre a sobreposição dos caminhos. Sem perda de Assim, dist(y, z) ≥ dist(y, v).
Como dist(u, z) = dist(u, y) + dist(y, z) ≥ dist(u, y) + dist(y, v) = dist(u, v). O que leva novamente a uma contradição já que por hipotese {u, v} é o diâmetro original da árvore.
Se os caminhos não se sobrepõem, tem que haver dois vértices um no caminho uv e outro no caminho wz que são os mais próximos, sejam estes vértices x e y. Assim dist(u, z) = dist(u, y) + dist(y, z) ≥ dist(u, y) + dist(y, v) > dist(u, x) + dist(x, v) = dist(u, v). Daí a suposição de que {u, v} é o diâmetro é contrariada.
cqd.
Desse modo, o cálculo do diâmetro de uma árvore pode ser feito usando-se duas buscas em profundidade (ou em largura), uma delas (partindo de qualquer vértice) para achar o vértice mais distante, que será uma das extremidades (u ou v) do diâmetro. E a outra partindo-se do vértice encontrado (u ou v) para se calcular efetivamente o diâmetro do grafo.
Complexidade da solução
Tanto a busca em profundidade quanto em largura têm complexidade O(E), sendo E o número de arestas do grafo.
Implementação
O código abaixo implementa a solução apresentada acima.
Se você copiou e colou o código acima você foi recompensado com um grande segmentation falt. Embora correto, o código tem um problema difícil de perceber. Ele é passível de um estouro de pilha! A pilha de ativação não é infinita, na realidade ela é bem pequena, e nosso código pode no pior caso fazer 10^6 chamadas a função dsf (lembre-se 2 ≤ N ≤ 10^6) causando assim um estouro de pilha que acaba por nos apresentar a exclarecedora mensagem de seg falt :(. O código abaixo resolve esse problema emulando uma pilha de ativação e removendo a recursão da função dsf.
