Como faço para encontrar o caminho mais curto que cobre todos os nós em um gráfico cíclica dirigido?

Question

I precisa de um exemplo do caminho mais curto de um grafo clico direccionado a partir de um nó (Que deve chegar a todos os nós do gráfico de um nó, que será a entrada).

Por favor, se há um exemplo, eu preciso dele em C ++, ou o algoritmo.

Answer 1

EDIT: Opa, descaracterizou a pergunta. Graças @jfclavette para escolher isso. velha resposta está no fim.

O problema que você está tentando resolver é chamado o Problema do caixeiro viajante . Há muitos , mas é NP-completo para que você não será capaz de resolver para grandes gráficos.

resposta antiga:

O que você está tentando encontrar é chamado o perímetro de um gráfico. Ele pode ser resolvido, definindo as distâncias de um nó para si ao infinito e usando o Floyd-Warshall algoritmo. O comprimento do ciclo mais curto do nó i é, em seguida, apenas a entrada na posição II.

Answer 2

Em 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)

Este executa um Dijkstra ligeiramente diferente é em cada vértice. O Dijkstras mutado tem algumas diferenças fundamentais. Em primeiro lugar, todas as distâncias iniciais são ajustados para 8, mesmo o iniciar vértice. Em segundo lugar, o vértice de início deve ser colocado na fila primeiro a fazer certeza que sai primeira vez que todos eles têm a mesma prioridade. finalmente, o mutante Dijkstras retorna a volta distância para o nó de início. Se houver nenhuma foi caminho de volta para o início vértice os restos distância 8. O mínimo de todos estes rendimentos do Dijkstras mutado é o caminho mais curto. Desde Dijkstras runs no pior dos casos em O (| V | ^ 2) e min_cycle executa esta forma de Dijkstras | V | vezes, o tempo de funcionamento final para encontrar o ciclo mais curto é O (| V | ^ 3). Se os retornos min_cyc 8, em seguida, o gráfico é acíclico.

Para retornar o caminho real do ciclo mais curto apenas ligeiras modificações precisam ser feitas.

Answer 3

No caso não ponderada: Amplitude primeiro procurar . No caso ponderada:. de Dijkstra

Answer 4

Para grafo não ponderada, BFS irá fazer o trabalho. Uma vez que existe ciclo potencial no seu gráfico, você precisa manter o controle de nó visitou (você espécie de necessidade de fazer isso para BFS de qualquer maneira).

Para grafo ponderado, carregador Ford-algoritmo pode ser usado. Ele também é capaz de detectar ciclos.