Как мне найти кратчайший путь, который охватывает все узлы в ориентированном циклическом графе?

Question

Мне нужен пример кратчайшего пути ориентированного циклического графа из одного узла (он должен достигать всех узлов графа от узла, который будет входным).

Пожалуйста, если есть пример, он мне нужен на C ++ или в алгоритме.

Answer 1

РЕДАКТИРОВАТЬ: Ой, неправильно прочитал вопрос. Спасибо @jfclavette за то, что подобрали это. Старый ответ в конце.

Проблема, которую вы пытаетесь решить, называется Задача коммивояжера . Существует множество потенциальных решений , но они NP-завершены, поэтому вы не сможете найти решение для больших графиков.

Старый ответ:

То, что вы пытаетесь найти, называется обхват графика. Это можно решить, установив расстояния от узла до самого себя до бесконечности и используя алгоритм Floyd-Warshall . Длина самого короткого цикла от узла i - это просто запись в позиции ii.

Answer 2

в псевдокоде:

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

Это запускает немного разные Дейкстры в каждой вершине. Мутировавший Dijkstras имеет несколько ключевых отличий. Во-первых, все начальные расстояния установлены на ∞, даже Начать вершину. Во-вторых, начальная вершина должна быть помещена в очередь первой, чтобы сделать уверен, что это срабатывает первым, так как все они имеют одинаковый приоритет Наконец, мутировавший Dijkstras возвращает расстояние до начального узла. Если бы не было путь назад к начальной вершине, расстояние остается ∞. Минимум всех этих Возвращение из мутировавшего Dijkstras является кратчайшим путем. Так как Dijkstras работает в худшем случае в O (| V | ^ 2) и min_cycle запускает эту форму Dijkstras | V | раз конечное время выполнения для нахождения кратчайшего цикла - O (| V | ^ 3). Если min_cyc возвращается ∞ то график ацикличный.

Чтобы вернуть фактический путь кратчайшего цикла, необходимо внести лишь небольшие изменения.

Answer 3

В невзвешенном случае: Поиск в ширину . В взвешенном случае: Дейкстры .

Answer 4

Для невзвешенного графика BFS сделает эту работу. Поскольку в вашем графике есть потенциальный цикл, вам нужно отслеживать посещаемый узел (вам все равно нужно это сделать для BFS).

Для взвешенного графика можно использовать алгоритм Беллмана – Форда. Он также способен обнаруживать циклы.