Algoritmo de Dijkstra e Algoritmo de Kruskal

1783 palavras 8 páginas
Algoritmo de Dijkstra e Algoritmo de Kruskal

Resumo. Este artigo apresenta uma revisão sobre os principais conceitos do algoritmo de Dijkstra e do algoritmo de Kruskal, no qual são algoritmos gulosos usados para solucionar o problema de caminho mais curto e busca de uma árvore geradora mínima, em um grafo, respectivamente.

1. Introdução
Em muitos problemas de interesse prático, onde há uma sequencia de passos, e a cada passo há diversas alternativas, usa-se algoritmos relacionados com otimização para solucionar. A técnica que é usada para resolver este tipo de problema chama-se de algoritmo guloso, ou ganancioso, no qual é responsável por fazer a decisão, em cada passo, de uma escolha considerada ótima no momento, baseado simplesmente nas informações disponíveis, assim esperam que esta escolha leve até a solução ótima global. Embora algoritmos gulosos pareçam obviamente corretos, nem sempre seja possível chegar a uma solução ótima. Para compensar, algoritmos gulosos são muito rápidos e eficientes.
Apresenta-se neste artigo, o Algoritmo de Dijkstra, cujo é um algoritmo guloso, usado para se computar o caminho mínimo em um grafo, ou seja, sua função entenda-se que haja um grafo com peso nas arestas – como fosse o comprimento -, então se deseja atravessar do vértice inicial ao final, então um caminho de menor custo será o que teremos de percorrer, uma distancia menor para chegar de um vértice até outro.
Também será apresentado neste artigo, outro

Relacionados