O algoritmo de Dijkstra ea súa implementación

Hai unha área separada chamada teoría dos grafia en matemáticas e ciencia da computación. Como parte do seu conxunto e para resolver varios problemas, tales como atopar o camiño máis curto entre os vértices. Un común entre matemáticos formas de solucionar este problema foi algoritmo do Dijkstra.

¿Que é un gráfico matemático

Crese que a noción da gráfica foi posto en uso no século XVIII por Leonhard Euler. Foi el quen anunciou a formulación e solución dun dos problemas clásicos desta teoría - os sete pontes de Königsberg. Co fin de explicar o obxecto desta teoría moitas veces usan esta analoxía como movemento entre distintas cidades. A continuación, o gráfico no plano será un diagrama enteiro percorrido, onde se fan vértices elementos específicos (por exemplo, cidades), e os bordos - camiño dun vértice a outro (analóxico estrada entre cidades). o algoritmo de Dijkstra, ademais doutros métodos, pode fornecer unha solución para esta cuestión.

Atopar o camiño máis curto

Unha das tarefas comúns da teoría dos grafia é aquel en que precisa para determinar o camiño de custo óptimo entre dous puntos. Pode reducir o avión para a decisión da gráfica no cal os vértices - cidades - son costelas conectados, que é un camiño posible. Cada estrada ten o seu propio lonxitude, polo tanto, viaxar nel terá que gastar moito diñeiro. Esta cantidade é equivalente ao peso das beiras da gráfica. Entón o problema na práctica pode formularse como segue: como abrir o camiño dunha cidade a outra, a ser gasto cos medios mínimos estrada.

formas de resolver

Para solucionar este problema que foron inventados por algúns algoritmos que se fan amplamente coñecidas no mundo científico. Por exemplo, o algoritmo de Floyd - Uorshella, Ford - Bellman. O xeito clásica de atopar solucións é tamén o algoritmo de Dijkstra. Pode ser usado para ponderados (peso coñecido de cada bordo) da gráfica, e para diluír. Para atopar a mellor forma que ten que facer varias etapas.

o algoritmo de Dijkstra

O punto deste método reside no feito de que todos os vértices do custo, comezando cun determinado, no que cada etiqueta se lle atribúe un determinado valor. Entón o resultado debería incluír os vértices cuxos etiquetas son mínimas. Na parte superior da primeira etapa inicial marcará cun valor igual a 0. Entón todos os picos seguintes considéranse, é dicir, aqueles que poden ser alcanzadas dende a fonte. Son rotulado, cuxo valor é determinado como a suma do código fonte e peso dos camiños. Do alto da seguinte paso, seleccione a que ten o menor valor da etiqueta, e estudou todos os vértices en que a partir del podemos ir sen usar os nós intermediarios. Especifique un novo álbum igual para os cumes de etiqueta - código fonte máis o peso do camiño. Se o valor é menor que a etiqueta de arriba, a etiqueta é modificado. Se non, segue sendo o valor orixinal. Á vez nunha matriz separada, cuxa dimensión é igual ao número de vértices, que almacena o resultado da optimización, en que é determinada maneira. Para aplicar un método como o algoritmo de Dijkstra, Pascal ofrece un medio moi cómodo. O algoritmo ten a vantaxe de que pode facilmente ser a base para un programa que ten un tamaño pequeno. Exemplos de tales produtos de software fáciles de atopar en internet.

solucións DLE diferentes ferramentas que pode usar a tarefa de atopar o camiño ideal. Para solucións como o algoritmo de Dijkstra, Delphi creará forma conveniente de entrada de datos visual e de saída o resultado final.