Na ciência matemática e na ciência da computação, existeuma área separada chamada teoria dos grafos. Dentro de sua estrutura, vários problemas são colocados e resolvidos, por exemplo, sobre como encontrar o caminho mais curto entre os picos. O algoritmo de Dijkstra tem sido uma das maneiras mais comuns de resolver esse problema entre os matemáticos.
Acredita-se que o conceito de gráfico foi introduzido emusado no século XVIII por Leonard Euler. Foi ele quem anunciou a formulação e solução de um dos problemas clássicos desta teoria - sobre as sete pontes de Koenigsberg. Para explicar o objeto dessa teoria, na maioria das vezes eles usam essa analogia como movimento entre diferentes cidades. Então, o gráfico no plano representará todo o esquema da rota, onde os vértices serão pontos específicos (por exemplo, cidades) e as arestas serão os caminhos de um vértice para outro (análogo a uma estrada entre cidades). O algoritmo de Dijkstra, além de outros métodos, pode fornecer uma solução para essa questão.
Um dos problemas padrão na teoria dos grafos éaquele em que você precisa determinar o caminho econômico entre dois pontos. Pode ser reduzido em um plano à solução de um grafo no qual os vértices - cidades - são conectados por arestas, que representam possíveis estradas. Além disso, cada estrada tem seu próprio comprimento, portanto, alguns fundos terão que ser gastos para percorrer ao longo dela. Essa soma é equivalente ao peso de uma aresta no gráfico. Então, o problema na prática pode ser formulado da seguinte forma: como pavimentar o caminho de uma cidade para outra para gastar o mínimo de dinheiro na estrada.
Soluções
Para resolver este problema, algunsalgoritmos que se tornaram amplamente conhecidos no mundo científico. Por exemplo, o algoritmo Floyd-Warshall, Ford-Bellman. O algoritmo de Dijkstra também é uma maneira clássica de encontrar uma solução. Ele pode ser usado para um gráfico ponderado (o peso de cada aresta é conhecido) e um gráfico esparso. Para encontrar o caminho final, você precisa seguir várias etapas.
Algoritmo de Dijkstra
O objetivo deste método é quetodos os vértices são percorridos, começando com um determinado, e cada um recebe um rótulo com algum valor. Então, o resultado incluirá aqueles vértices cujos rótulos são mínimos. No primeiro passo, é atribuído ao vértice original um rótulo com o valor 0. Em seguida, são considerados todos os vértices seguintes, ou seja, aqueles que podem ser alcançados a partir do original. Eles são atribuídos a rótulos, cujo valor é determinado como a soma da origem e do peso do caminho. A partir dos vértices do próximo passo, seleciona-se aquele que tiver o menor valor de rótulo, e estudam-se todos os vértices que podem ser alcançados a partir dele sem usar vértices intermediários. Um novo valor de rótulo é determinado, igual ao rótulo do vértice de origem mais o peso do caminho. Se o valor recebido for menor que o rótulo do vértice, o rótulo é alterado. Caso contrário, o valor original permanece. Nesse caso, em uma matriz separada, cuja dimensão é igual ao número de vértices do gráfico, o resultado da otimização é salvo, pelo qual o caminho é determinado. Para implementar um método como o algoritmo de Dijkstra, Pascal oferece ferramentas muito convenientes. O algoritmo tem a vantagem de poder ser facilmente usado como base para um programa de tamanho pequeno. Exemplos de tais produtos de software são fáceis de encontrar na Internet.
