Esto puede parecer simple en el gráfico que proporcionó. (Trataremos con ‘rutas simples’ que son rutas que no atraviesan un vértice más de una vez). Por ejemplo, aquí están todas las rutas simples de A a B:
A, B
A, C, B
- ¿Cómo se construye un SO por primera vez?
- ¿Por qué se le da tanta importancia al aprendizaje automático?
- Informática: ¿Por qué la memoria contenida en los registros es tan costosa?
- ¿Cómo describirías a los miembros de la facultad en el departamento de CS de tu universidad?
- ¿Qué algoritmos de visión por computadora se pueden usar para aumentar la claridad de una imagen?
A, C, D, B
A, C, D, E, B
El número de caminos simples de un vértice a otro es exponencial en la suma de los vértices y bordes. Por lo tanto, en general, le gustaría evitar encontrar todos los caminos entre dos vértices.
La buena noticia es que con frecuencia queremos encontrar el camino más corto de un vértice a otro. En este caso, puede utilizar el algoritmo de ruta más corta de Dijkstra. Este es un algoritmo hermoso, y es muy rápido.
Pero si debe encontrar todas las rutas de un nodo a otro, puede usar un algoritmo de búsqueda de amplitud. Si está interesado en él, consulte el artículo de Wikipedia, Breadth-first search.
