El algoritmo de Dijkstra requiere…
Opciones
- Un grafo dirigido acíclico (DAG)
- Pesos de arista que no sean negativos (Opción correcta)
- Un grafo sin pesos en sus aristas
- Una matriz de adyacencia como representación
Respuesta
Pesos de arista no negativos
Por qué
Dijkstra encuentra caminos más cortos cuando las aristas tienen pesos (distancias, costes). Siempre expande a continuación el nodo no visitado más cercano (con un min-heap) y considera su distancia como definitiva.
Esa decisión 'definitiva' solo es correcta si ninguna arista puede acortar un camino después, es decir, sin pesos negativos.
Con pesos negativos usa Bellman-Ford. Complejidad con un heap: O((V + E) log V).
Recuerda
Dijkstra = camino más corto con pesos, sin aristas negativas.