Problema de caminho mais curto
Você já usou o Google Maps para encontrar a rota mais curta ou o custo mínimo de gás para ir de um ponto a outro? Nesse caso, você encontrou um exemplo do problema do caminho mais curto . Em termos matemáticos, essa é uma maneira de encontrar a distância mais curta possível entre dois vértices em um gráfico.
Suponha que estejamos tentando encontrar o caminho mais curto de sua casa até a casa de Divya. Conhecemos as distâncias entre vários locais da cidade. Se permitirmos que vários locais sejam vértices e as rotas entre eles sejam arestas, podemos criar um gráfico ponderado que representa a situação. Definição rápida: um gráfico ponderado é uma coleção de vértices e arestas com arestas tendo um valor numérico (ou peso) associado a eles.
 |
Este gráfico é um ótimo exemplo de gráfico ponderado usando os termos que acabamos de apresentar. Existem várias rotas diferentes que podemos seguir, mas queremos saber qual é a mais curta. Felizmente, temos um bom algoritmo que pode nos ajudar.
Algoritmo de Dijkstra
O algoritmo de Dijkstra é um algoritmo que podemos usar para encontrar distâncias mais curtas ou custos mínimos, dependendo do que é representado em um gráfico. Você está basicamente trabalhando de trás para frente, do fim ao começo, encontrando a perna mais curta a cada vez. As etapas para este algoritmo são as seguintes:
Passo 1: Comece no vértice final marcando-o com uma distância 0, porque é 0 unidades do final. Chame este vértice de seu vértice atual e coloque um círculo ao redor dele indicando como tal.
Etapa 2: #Identifique todos os vértices que estão conectados ao vértice atual com uma aresta. Calcule a distância até o final adicionando o peso da aresta à marca no vértice atual. Marque cada um dos vértices com sua distância correspondente, mas apenas altere a marca de um vértice se for menor que a marca anterior. Cada vez que você marcar o vértice inicial com uma marca, mantenha o controle do caminho que resultou nessa marca.
Etapa 3: rotule o vértice atual como visitado, colocando um X sobre ele. Depois que um vértice é visitado, não o examinaremos novamente.
Passo 4: Dos vértices que você acabou de marcar, encontre aquele com a menor marca e torne-o seu vértice atual. Agora, você pode começar novamente a partir da etapa 2.
Etapa 5: Depois de rotular o vértice inicial como visitado – pare. A distância do caminho mais curto é a marca do vértice inicial, e o caminho mais curto é o caminho que resultou nessa marca.
Vamos agora considerar encontrar o caminho mais curto de sua casa até a casa de Divya para ilustrar esse algoritmo.
Inscrição
Primeiro, começamos no vértice final (a casa de Divya). Marque-o com um zero e chame este vértice de vértice atual, colocando um círculo ao redor dele, como você pode ver no gráfico:
 |
A próxima etapa é marcar todos os vértices que estão conectados à casa de Divya por uma aresta com a distância do final. Vamos calcular rapidamente essas distâncias enquanto olhamos para uma representação visual do que está acontecendo usando nosso gráfico anterior:
- Cinema = 0 + 4 = 4
- Supermercado = 0 + 5 = 5
- Posto de gasolina = 0 + 6 = 6
 |
Agora terminamos a casa de Divya, então a rotulamos como visitada com um X. Vemos que o menor vértice marcado é a sala de cinema com uma marca de 4. Este é nosso novo vértice atual, e começamos novamente na etapa 2.
 |
Agora, marcamos quaisquer vértices conectados por uma aresta à sala de cinema, adicionando o peso da aresta de conexão à marca da sala de cinema. Como a casa de Divya está marcada como visitada, não precisamos considerar esse vértice.
- Mercearia = 4 + 2 = 6, mas 6> 5 (a marca atual da mercearia), então não mudamos a marca.
- Sua casa = 4 + 3 = 7, então marcamos sua casa com 7 e registramos o caminho que resultou nessa marca.
Vemos que dos dois vértices, o supermercado é marcado com o número menor. Esse se torna nosso vértice atual, e rotulamos o cinema como visitado.
 |
Volte para a etapa 2! O supermercado é conectado por uma aresta a todos os outros vértices. Consideramos apenas vértices não visitados, que são a sua casa e o posto de gasolina.
- Posto de gasolina = 5 + 1 = 6, mas 6 = 6 (a marca atual), portanto, não precisamos substituí-lo.
- Sua casa = 5 + 4 = 9, mas 9> 7 (a marca atual), então não a alteramos.
Desde 6 <7, tornamos o posto de gasolina o próximo vértice atual e rotulamos o supermercado como visitado.
 |
Mais uma vez, etapa 2. O único vértice conectado ao posto de gasolina que não foi rotulado como visitado é sua casa. Adicionamos o peso da borda que conecta sua casa e o posto de gasolina à marca atual do posto de gasolina.
- Sua casa = 2 + 6 = 8, mas 8> 7, então deixamos a marca atual de sua casa como está.
 |
Ficamos com sua casa como o único vértice que resta para visitar. Como todos os vértices que estão conectados por uma aresta à sua casa foram visitados, podemos marcar sua casa como visitada e podemos parar por aqui. O caminho mais curto de sua casa até a casa de Divya é de 11 quilômetros e vai da sua casa ao cinema até a casa de Divya.
Ufa! Conseguimos!
Resumo da lição
Vamos levar alguns minutos para revisar o que aprendemos sobre o algoritmo de Dijkstra …
O algoritmo de Dijkstra é um algoritmo usado para resolver o problema da distância mais curta. Ou seja, nós o usamos para encontrar a menor distância entre dois vértices em um gráfico. Dependendo do que o gráfico representa, podemos encontrar as rotas mais curtas, custos mínimos, etc., todos usando este algoritmo.
O algoritmo funciona começando no vértice final e visitando os vértices, encontrando a distância mais curta desse vértice até o vértice final. Quando chegamos ao vértice inicial, podemos identificar o caminho mais curto e seu comprimento.
Embora as etapas sejam bastante simples, o algoritmo pode se tornar bastante tedioso quando feito à mão. Graças a Deus, o algoritmo de Dijkstra abriu caminho para que os aplicativos de computador encontrem distâncias mais curtas ou custos mínimos em questão de segundos!