4.1. Método general.
Ejemplo. Algoritmo de Kruskal, para hallar el árbol de expansión de costo mínimo.
- El conjunto de candidatos inicial será el conjunto de aristas con sus pesos.
- El elemento seleccionado en cada paso será el candidato de menor coste y que no forme un ciclo en la solución actual.
- Tenemos una solución cuando hayamos seleccionado N-1 nodos.
Ejemplo. Algoritmo de Dijkstra, para el cálculo de distancias mínimas.
- Los candidatos son los nodos del grafo.
- Seleccionar en cada paso el nodo candidato con valor de camino especial más corto.
Otros ejemplos: algoritmo de Prim, algoritmo para calcular el flujo máximo.
¿Qué pasa con el algoritmo de Floyd?