ANTECEDENTES

El problema de Camino es básicamente un problema de determinar conectividad en grafos. Debe simplemente decidirse que vertices al borrarse logran que no exista camino entre el vértice 1 y el vértice 1000.

APROXIMACIONES

Lo primero que podría pensarse para resolver este problema es mirar que vértices no es posible evitar en ninguno de los caminos que van desde el vértice 1 hasta el vértice 1000.

En este caso, se deben generar todos los caminos posibles entre el vértice 1 y el vértice 1000. Después debe contarse en cuantos de los caminos aparece cada vértice. Entonces los vértices que son imposibles de evitar en el recorrido son aquellos que aparecen en todos los caminos.

Sin embargo este algoritmo no es eficiente debido a que requiere que se prueben todos los caminos, lo que implica un algoritmo de backtracking. A medida que se incrementa el número de arcos y el número de nodos, este algoritmo se vuelve ineficiente. En el peor de los casos, cuando existieran 1000 vértices y existieran arcos entre todos ellos, el número de combinaciones o caminos a probar sería aproximadamente 1000!, más exactamente este número sería 998! ya que solo consideramos los caminos que inician en 1 y terminan en 1000.

De esta forma, este primer enfoque solo serviría para grafos en los que existan pocos arcos y por tanto el número de caminos diferentes sea muy pequeño.

SOLUCIÓN

La solución propuesta tiene mayor relación con el problema de probar conectividad en grafos. Para este proceso, se prueba ignorando en cada paso un vértice. Si es posible aún llegar desde el vértice 1 hasta el 1000, entonces podemos decir que ese vértice puede evitarse. Si por el contrario, el hecho de ignorar ese vértice hace que 1 y 1000 queden desconectados, sabemos entonces que ese es un vértice imposible de evitar.

Para probar la conectividad pueden pensarse varias opciones. Una de ellas podría ser usar un algoritmo de caminos mínimos para determinar si hay ruta entre 1 y 1000, pero esto es un proceso de O(n²), lo que aún no es lo suficientemente eficiente. Además sabemos que no se necesita conocer el camino mínimo, sino simplemente saber si existe un camino o no.

Para este propósito, lo más eficiente es realizar un recorrido simple del grafo, el cual puede hacerse con una búsqueda por niveles o una búsqueda en profundidad. Esta última alternativa es la más sencilla, ya que se puede implementar con un algoritmo recursivo simple. Si dentro de la búsqueda llegamos al vértice 1000 podemos cortar el algoritmo y declarar que el vértice ignorado no es indispensable. Una búsqueda de este tipo tiene un orden de ejecución O(n+m) (n vértices y m arcos) lo que proporciona una buena eficiencia.

CÓDIGO

Dentro del código las funciones que resuelven el problema son

DFS( origen )

Realiza una búsqueda en profundidad a partir del vértice recibido como parámetro. Si llega al vértice 1000 corta la recursión.

Proceso()

Toma cada uno de los vértices intermedios y lanza una búsqueda en profundidad ignorando cada vez uno de los vértices. Si no es posible llegar al vértice 1000, se imprime el vértice ignorado como un vértice al que es obligatorio visitar.

Duvier Alexander Zuluaga Mora

duvier@softhome.net