Algoritmos de grafos: Dijkstra, Prim, Kruskal y Ford-Fulkerson
Algoritmo de Dijkstra: Caminos Mínimos en Grafos
El algoritmo de Dijkstra es fundamental para encontrar los caminos más cortos desde un nodo fuente único hacia todos los demás nodos en un grafo con pesos de arista no negativos.
Definición de Elementos Clave:
- P: Conjunto de nodos permanentes (ya visitados y con su camino mínimo finalizado).
- T: Conjunto de nodos temporales (pendientes de visitar o actualizar).
- ui: Longitud del camino mínimo actual desde el vértice inicial hasta el vértice i, para todo i = 1, ..., n (donde n es el número de vértices del grafo).
- pred: Vector que almacena los predecesores de cada nodo en el camino mínimo.
Pasos del Algoritmo de Dijkstra:
Paso 0: Inicialización
Se etiquetan los nodos con la longitud del arco