La diferencia entre el algoritmo de Floyd y el algoritmo de Dijkstra

¡Déjame decirte la respuesta estándar! El algoritmo de Floyd, también conocido como algoritmo de Floyd, método de punto de interpolación, es un algoritmo que se utiliza para encontrar el camino más corto entre los vértices en un gráfico ponderado determinado.

Proceso del algoritmo: 1. Partir de cualquier camino unilateral. La distancia entre los dos puntos es el peso del borde, o infinito si ningún borde conecta los dos puntos.

2. Para cada par de vértices u y v, vea si hay un vértice w que hace que el camino de u a w a v sea más corto que el camino conocido. Si es así actualízalo.

El algoritmo de Dijkstra es un algoritmo típico de ruta más corta de fuente única, que se utiliza para calcular las rutas más cortas desde un nodo a todos los demás nodos. La característica principal es que se expande capa por capa desde el punto inicial hasta llegar al punto final.

Los pasos del algoritmo son los siguientes:

1 Inicialmente establece S={V0}, T={vértices restantes} y la distancia. valores correspondientes a los vértices en T

Si existe, d(V0, Vi) es el peso sobre el arco

Si no existe, d(V0, Vi ) es ∝

2. Seleccione un vértice W cuyo valor de distancia sea el más pequeño de T y no esté en S, y agregue S

3. T: Si se agrega W como vértice intermedio, de V0 a El valor de distancia de Vi es más corto que el camino sin W, entonces modifique el valor de distancia

Repita los pasos 2 y 3 anteriores hasta que S contenga todos los vértices , es decir, S=T Hasta