Aunque el cálculo de algoritmos de árbol de expansión mínimo y ruta más corta es similar, se centran en 2 requisitos diferentes.
En MST, el requisito es alcanzar cada vértice una vez (crear árbol de gráficos) y el costo total (colectivo) de alcanzar cada vértice debe ser mínimo entre todas las combinaciones posibles.
En la ruta más corta, el requisito es alcanzar el vértice de destino desde el vértice de origen con el costo más bajo posible (peso más corto). Entonces, aquí no nos preocupamos por alcanzar cada vértice, sino que solo nos enfocamos en los vértices de origen y destino y ahí es donde radica la diferencia.
- ¿Cuáles son los principios o características esenciales de los algoritmos gráficos en informática?
- ¿Cuál es el mejor camino para dominar el aprendizaje profundo?
- ¿Son necesarios los algoritmos y las clases de estructura de datos para hacer una clase de desarrollo de aplicaciones móviles?
- ¿Qué es la estructura de datos, algoritmo en informática? ¿Cuál es la mejor forma en línea para aprenderlo?
- ¿Cómo es que la mayoría de las empresas solicitan específicamente estructuras de datos y algoritmos? ¿Qué sucede cuando un adicto a los algoritmos con solo conocimiento de C ++ o Java es aceptado en una empresa que utiliza tecnologías web, aprende el marco utilizado desde cero?
Aquí está el ejemplo para aclarar por qué MST no necesariamente da la ruta más corta entre 2 vértices.
A ——— (5) ——— B ——— (5) —— C
| _________ (7) _________ |
En el caso de MST, bordes AB. BC estará en MST con un peso total de 10. Por lo tanto, el costo de llegar de A a C en MST es 10.
Pero en el caso de la ruta más corta, la ruta más corta entre A y C es AC, que es 7. AC nunca estuvo en MST.