En el algoritmo Floyd – Warshall para encontrar las rutas más cortas en un gráfico, inicialmente establece dist [u] [v] = [math] \ infty [/ math] y dist [v] [v] = 0. En otras palabras, la distancia desde cualquier vértice u al vértice v (u ≠ v) es infinita, y la distancia desde cualquier vértice v a sí mismo es 0.
En este caso, queremos que la ruta finalice en el vértice inicial, por lo que en lugar de establecer dist [v] [v] = 0, establecemos dist [v] [v] = [math] \ infty [/ math]. Esto significa que desde v, queremos la ruta más corta a v, que es lo mismo que encontrar el ciclo más corto que incluye el vértice v.
Una vez que tenemos todos los valores para dist [v] [v] después de ejecutar Floyd Warshall, tenemos la longitud del ciclo más corto en el gráfico que contiene el vértice v, para todos los v. Para encontrar el ciclo más corto en el gráfico (que necesita no incluye un vértice particular v), simplemente queremos encontrar min (dist [v] [v]), que será el ciclo más corto.
- ¿Dónde debo desarrollar mi lógica, en matemáticas relacionadas con la programación?
- ¿Cuál es la mejor manera de aprender algoritmos de informática?
- ¿Qué tiene más sentido estudiar como programador después de aprender algoritmos básicos?
- ¿Cuáles son los rompecabezas de algoritmos de notación O más interesantes?
- ¿Por qué los problemas NP completos son más difíciles que los problemas NP si un problema NP puede reducirse a un problema NP completo?
Editar: Esto solo funcionará si no hay ciclos negativos, lo cual es una suposición para Floyd Warshall.
