32 lines
1.6 KiB
TeX
32 lines
1.6 KiB
TeX
Encontrar o menor caminho entre dois pontos em um mapa é um problema clássico.
|
|
Mas, em alguns sistemas de navegação, todas as rotas que fazem parte de algum
|
|
menor caminho podem ficar congestionadas. Nesse caso, queremos encontrar uma rota
|
|
alternativa.
|
|
|
|
O mapa é representado por um grafo direcionado e ponderado. Os vértices são
|
|
pontos do mapa, e cada aresta direcionada representa uma rota de um ponto para
|
|
outro com um certo comprimento.
|
|
|
|
O quase menor caminho entre a origem $S$ e o destino $D$ é o menor caminho de
|
|
$S$ até $D$ que não usa nenhuma aresta pertencente a qualquer menor caminho de
|
|
$S$ até $D$ no grafo original.
|
|
|
|
Sua tarefa é determinar o comprimento do quase menor caminho. Caso não exista
|
|
nenhum caminho que satisfaça essa condição, a resposta deve ser $-1$.
|
|
|
|
Por exemplo, suponha que a figura abaixo representa o mapa dado, com círculos
|
|
representando localizações e linhas representando rotas diretas, de mão única
|
|
com as distâncias indicadas. O ponto de partida está marcado como $S$ e o de
|
|
destino está marcado como $D$. As linhas em negrito pertencem a um caminho
|
|
mínimo (nesse caso existem dois caminhos mínimos, cada um com extensão \(4\)).
|
|
Logo, o quase menor caminho seria o indicado com linhas pontilhadas (extensão
|
|
\(5\)), já que nenhuma rota entre dois pontos consecutivos pertence a nenhum
|
|
caminho mínimo. Note que poderia existir mais de uma resposta possível, por
|
|
exemplo, se a rota com extensão \(3\) tivesse extensão \(1\). Bem como poderia
|
|
inexistir uma resposta certa.
|
|
|
|
\begin{figure}[h]
|
|
\centering
|
|
\includegraphics[width=0.3\textwidth]{image.png}
|
|
\end{figure}
|