¿Cómo encuentro la ruta más corta que cubre todos los nodos en un gráfico cíclico dirigido?

Necesito un ejemplo de la ruta más corta de un gráfico cíclico dirigido desde un nodo (debe llegar a todos los nodos del gráfico desde un nodo que será la entrada).

Por favor, si hay un ejemplo, lo necesito en C ++, o el algoritmo.

EDIT: Oops, malinterpreta la pregunta. Gracias @jfclavette por recoger esto. La vieja respuesta está al final.

El problema que estás tratando de resolver se llama el problema del vendedor viajero . Hay muchas soluciones potenciales , pero se completa con NP, por lo que no podrá resolver gráficos grandes.

Respuesta antigua:

Lo que estás tratando de encontrar se llama la circunferencia de un gráfico. Se puede resolver configurando las distancias de un nodo a sí mismo hasta el infinito y utilizando el algoritmo Floyd-Warshall . La longitud del ciclo más corto desde el nodo i es solo la entrada en la posición ii.

En Pseudocódigo:

//INPUT: graph G = (V,E) //OUTPUT: shortest cycle length min_cycle(G) min = ∞ for u in V len = dij_cyc(G,u) if min > len min = len return min //INPUT: graph G and vertex s //OUTPUT: minimum distance back to s dij_cyc(G,s) for u in V dist(u) = ∞ //makequeue returns a priority queue of all V H = makequeue(V) //using dist-values as keys with s First In while !H.empty? u = deletemin(H) for all edges (u,v) in E if dist(v) > dist(u) + l(u,v) then dist(v) = dist(u) + l(u,v) decreasekey(H,v) return dist(s) 

Esto ejecuta un Dijkstra ligeramente diferente en cada vértice. El Dijkstras mutado tiene algunas diferencias clave. Primero, todas las distancias iniciales se establecen en, incluso el vértice de inicio. Segundo, el vértice de inicio debe ponerse en la cola primero para asegurarse de que se salga primero, ya que todos tienen la misma prioridad. Finalmente, el Dijkstras mutado devuelve la distancia al nodo de inicio. Si no había una ruta de regreso al vértice de inicio, la distancia sigue siendo. El mínimo de todos estos retornos de las Dijkstras mutadas es la ruta más corta. Dado que Dijkstras funciona en el peor de los casos en O (| V | ^ 2) y min_cycle ejecuta esta forma de Dijkstras | V | veces, el tiempo de ejecución final para encontrar el ciclo más corto es O (| V | ^ 3). Si min_cyc devuelve ∞ entonces la gráfica es acíclica.

Para volver a la ruta real del ciclo más corto, solo se deben hacer pequeñas modificaciones.

En el caso no ponderado: Amplia primera búsqueda . En el caso ponderado: de Dijkstra .

Para el gráfico no ponderado, BFS hará el trabajo. Dado que existe un ciclo potencial en su gráfico, debe realizar un seguimiento del nodo visitado (de todos modos, debe hacer esto para BFS).

Para el gráfico ponderado, se puede utilizar el algoritmo de Bellman-Ford. También es capaz de detectar ciclos.