grafos

Algoritmo de Dijkstra
O Algoritmo de Dijkstra é um dos algoritmos que calcula o caminho de custo mínimo ou caminho mais curto entre vértices de um grafo com arestas de peso não negativo,é um algoritmo guloso, ou seja, toma a decisão que parece ótima no momento a partir da escolha de um vértice como raiz da busca

Algoritmo de Kruskal
Mas tudo bem, para o problema da AGM isso não vai ser um problema muito grande. Alguns matemáticos já conseguiram comprovar que o problema pode ser resolvido de maneira muito mais fácil: basta irmos escolhendo as menores arestas, uma a uma e com o cuidado de não formar ciclos, que eventualmente teremos uma árvore geradora mínima para qualquer grafo! Essa estratégia para resolver o problema é conhecida como o Algoritmo de Kruskal e pode ser resumida como:
Dado um grafo formado pelo conjunto de nós N e o conjunto de arestas E, faça, até que tenhamos formado uma árvore geradora:
1. Escolher, do conjunto de arestas E, aquela que possua o menor peso.
2. Se a inclusão desta aresta na solução não formar um ciclo, incluimos a aresta.
3. Caso contrário, descartamos a aresta e a retiramos de E.
Algoritmo de Prim
Outro algoritmo famoso para o problema é o Algoritmo de Prim, que funciona de maneira bastante semelhante ao anterior. No algoritmo de Kruskal, começamos com várias árvores separadas (no começo, cada nó é uma árvore) e vamos juntando essas árvores através das arestas de menor valor até formarmos uma árvore geradora. No algoritmo de Prim, iniciamos com uma árvore formada por um único nó (qualquer nó do grafo) e vamos adicionando à árvore, a cada passo, o nó que estiver mais próximo dela. Poderíamos resumir o algoritmo assim:
Dado um grafo formado pelo conjunto de nós N e o conjunto de arestas E, escolha um nó qualquer do grafo e coloque na árvore T. Repita os seguintes passos até que T seja uma árvore geradora:
1. Escolher o nó que está mais próximo da árvore T, ou seja, o nó que está ligado a um nó de T pela aresta de