En teoría de grafos, el algoritmo para la determinación del camino más corto, dado un vértice origen, hacia el resto de los vértices en un grafo que tiene pesos en cada arista se denomina:
- A.Algoritmo de Kruskal.
- B.Algoritmo de Prim.
- C.Algoritmo de Dijkstra.Respuesta correcta
- D.Algoritmo de Floyd-Warshall.
Explicación
El algoritmo de Dijkstra, propuesto en 1959, calcula el camino más corto desde un vértice origen al resto en un grafo ponderado con pesos no negativos. Complejidad O((V+E) log V) con heap binario. Kruskal calcula el árbol de expansión mínima (MST), igual que Prim. Floyd-Warshall calcula caminos más cortos entre TODOS los pares de vértices, no desde un origen. Para grafos con pesos negativos sin ciclos negativos: Bellman-Ford. Para no ponderados: BFS.