Estos son algunos puntos con restricciones y complejidades que he observado que podrían serle útiles para el problema del camino más corto.
1. Usando el algoritmo de dijkstra
– Si está implementando dijkstra usando una matriz 2d, entonces la complejidad será
O (v ^ 2) y prim también se implementan para el árbol de expansión mínimo.
-Y si lo está implementando mediante una lista de adyacencia utilizando un montón binario o una cola de prioridad, entonces la complejidad será O (Elogv) y prim también se implementará para el árbol de expansión mínima.
– Si utilizó el montón de Fibonacci, la complejidad puede reducirse aún más a O (E + VlogV)
2. Floyd Warshall
- ¿Cuáles son todas las áreas donde las estructuras de datos se aplican en escenarios del mundo real?
- ¿Cuáles son los algoritmos propuestos para la detección de revisiones falsas en el análisis de sentimientos?
- ¿Cuáles son las aplicaciones del algoritmo de la Torre de Hanoi?
- Cómo eliminar caracteres duplicados en la cadena char * p = 'chaabbcc'
- Cómo usar lower_bound para buscar una cadena en una estructura vectorial
Complejidad – O (v ^ 3).
Floyd Warshall encuentra caminos más cortos entre cada par de vértices, pero dijkstra solo se puede usar desde una fuente determinada a todos los destinos.
3. Dijkstra para cada par de vértices
Si aplica dijkstra en todos los nodos, la complejidad se convertirá
O (V * VlogV). De este modo, puedes encontrar los caminos más cortos entre cada par de vértices.
4. Algoritmo de Bellman-Ford y Johnson
Dijikstra no es válido para los bordes negativos, pero puede usar el algoritmo de Bellman-Ford cuya complejidad es O (VE) para la ruta desde la fuente dada a todos los destinos posibles, por lo que funciona para todos los tipos de gráficos.
Puede optimizarlo más utilizando el algoritmo de johnson. Su complejidad:
O (V ^ logV + VE)
5. Clasificación topológica
Para los bordes negativos si el gráfico está dirigido específicamente a un gráfico acíclico, puede usar el método que se usa para encontrar el problema de ruta más larga que es
use simplemente la clasificación topológica y luego actualice las distancias de su adyacente usando la distancia del vértice actual.
Su complejidad es O (V + E).
