Gracias por A2A!
Puedo entender lo que te llevó a esta pregunta.
Pero, el algoritmo de Prim no se puede utilizar para encontrar la ruta más corta desde un vértice a todos los demás vértices en un gráfico no dirigido.
- ¿Cuál es la diferencia entre un tipo estable e inestable?
- ¿Cómo funciona un algoritmo de 'aprendizaje de representación'?
- En problemas de DP, ¿cómo sabe si usar una matriz / tabla 1D o una matriz / tabla 2D?
- ¿Por qué Java utiliza diferentes algoritmos de clasificación para diferentes tipos de datos?
- ¿En qué lenguaje de programación están escritos los algoritmos de aprendizaje automático de Google: C ++ o Java? ¿Por qué?
Veamos las posibles razones por las que no se puede usar.
- Algoritmo de Prim
- Básicamente es un algoritmo codicioso (elige el borde ponderado mínimo adyacente a un vértice).
- Encuentra el árbol de expansión mínima (es decir, un árbol que consta de cada borde presente en el gráfico sin ningún ciclo en el que se minimice el peso total de los bordes). [Que ya has mencionado]
Ahora, esta es una imagen de un árbol de expansión mínimo, digamos que lo obtuvimos por la regla de Prim. Ahora lo ves por ti mismo
El camino (me dirijo a ellos con su peso)
3–2–2 tiene un peso total de 7 todavía, hubo una conexión directa de 6, eligió ese camino. El algoritmo de Prim siempre elegirá el borde ponderado mínimo local ya que es un algoritmo codicioso.
Por lo tanto, no podemos encontrar una solución correcta cuando intentamos encontrar el camino más corto .
Sí, ya que es un MST que conecta todos los bordes pero no genera la ruta más corta entre los vértices.
Dado que esta no es la forma de encontrar el camino más corto, debe haber algunos de ellos, y hay algún algoritmo para hacer la tarea:
- BFS si el peso no está definido o igual
- El algoritmo de Bellman Ford solía encontrar las rutas más cortas desde el vértice de origen a todos los demás vértices en un gráfico ponderado.
- El algoritmo de Floyd – Warshall se utiliza para encontrar los caminos más cortos entre todos los pares de vértices en un gráfico.
Notas al pie :
- Algoritmo de Prim – Wikipedia
- Árbol de expansión mínima – Wikipedia
- Algoritmo codicioso – Wikipedia
- Algoritmo de Bellman – Ford – Wikipedia
- Algoritmo de Floyd – Warshall – Wikipedia
- Estructuras de datos y primer recorrido transversal
¡Gracias por leer!
Espero eso ayude:)
