Consideremos un gráfico ponderado dirigido que tiene N vértices y M bordes.
El algoritmo de Dijkstra solo es aplicable cuando ninguno de los bordes tiene pesos negativos y tiene asintóticos O (N ^ 2 + M) u O (N + MlogM) [si lo implementa a través de la cola de prioridad]. Encuentra las distancias desde algún vértice de inicio fijo a todos los demás vértices.
Ford-Bellman hace lo mismo con los asintóticos O (NM) pero sin suponer que los pesos de los bordes no son negativos. También permite detectar ciclos negativos en caso de que el problema del camino más corto no esté bien definido.
El algoritmo de Floyd-Worshall similar al algoritmo de Ford-Bellman no depende de si el gráfico contiene bordes con valores negativos, ya que ambos pueden verse como los enfoques de programación dinámica para el problema del camino más corto. Por otro lado, FW resuelve un problema de ruta más corta un poco diferente que los dos algoritmos anteriores. Encuentra todas las distancias más cortas entre vértices, por ejemplo, la salida es una matriz NxN donde la celda (i, j) establece cuál es la distancia más corta entre i y j. Asintótico es O (N ^ 3 + M). Puede notar que, en general, es más eficiente que ejecutar N veces el algoritmo Ford Belman (a menos que tenga N> M, lo cual es bastante inusual). Pero en caso de que su gráfico no tenga bordes ponderados negativos y sea lo suficientemente escaso, también puede considerar ejecutar N vértices de cola de prioridad totalizando O (N ^ 2 + NMlogM).
- ¿Qué pasaría si más personas se dieran cuenta de que la Ley podría entenderse como una serie de algoritmos sociales en un programa que se resiste a la compilación?
- Cómo verificar si un algoritmo que hice en C ++ es eficiente en la vida real
- ¿Qué son los algoritmos de calibración para aplicaciones biomédicas en teléfonos inteligentes?
- Cómo implementar el mapa usando el árbol de búsqueda binario en Java
- ¿Deberíamos permitir patentes sobre algoritmos?
