Algoritmo de Dijkstra e Algoritmo de Kruskal

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 algoritmo guloso, o Algoritmo de Kruskal, usado para descobrir uma árvore geradora mínima em um grafo conexo e ponderado, isto significa, que sua função é encontrar um subconjunto das arestas que forma uma árvore que inclui todos os vértices, onde o peso total, dado pela soma dos pesos das arestas da árvore, é minimizado, ou seja, a ideia de Kruskal é unir todas as arestas de menor peso sem formar ciclos, para encontrar a árvore geradora mínima.

2. Algoritmo de Dijkstra
O algoritmo de