все возможные пути в циклическом неориентированном графе

Question

Я пытаюсь разработать алгоритм, который определяет все возможные пути между двумя узлами в графе, как в этом примере:

.

Фактически, мне просто нужно знать, какие узлы появляются во всех существующих дорожках.

В сети только есть ссылки на DFS, A * или dijkstra, но я думаю, что они не работают в этом случае.

Кто-нибудь знает, как его решить?

Answer 1

Вы можете найти все пути, используя DFS, как описано Владом. Чтобы найти, какие узлы появляются в каждом пути, вы можете просто сохранить массив логических элементов, который говорит, что каждый узел появился на каждом пути до сих пор. Когда ваш DFS найдет путь, пройдите через каждую вершину не в пути и установите для соответствующего значения массива значение false. Когда вы закончите, только вершины со значениями true будут теми, которые появляются на каждом пути.

псевдокод:

int source; 
int sink; 
int nVerts; 
bool inAllPaths[nVerts]; // init to all true 
bool visited[nVerts]; // init to all false 
stack<int> path; // init empty 

bool dfs(int u) 
    if (visited[u]) 
    return; 
    if (u == sink) 
    for i = 0 to nVerts-1 
     if !stack.contains(i) 
     inAllPaths[i] = false; 
    return true; 
    else 
    visited[u] = true; 
    stack.push(u); 
    foreach edge (u, v) 
     dfs(v); 
    stack.pop(); 
    visited[u] = false; 
    return false; 


main() 
    dfs(source); 
    // inAllPaths contains true at vertices that exist in all paths 
    // from source to sink. 

Однако этот алгоритм не очень эффективный. Например, в полном графике n вершин (все вершины имеют ребра для всех остальных) число путей будет n! (n факториал).

Лучшим алгоритмом было бы проверить наличие в каждом пути каждой вершины отдельно. Для каждой вершины попробуйте найти путь от источника к раковине, не переходя к этой вершине. Если вы не можете найти его, это потому, что вершина появляется на каждом пути.

псевдокод:

// Using the same initialisation as above, but with a slight modification 
// to dfs: change the foreach loop to 
foreach edge (u, v) 
    if (dfs(v)) 
    return true; // exit as soon as we find a path 

main() 
    for i = 0 to nVerts-1 
    set all visited to false; 
    if (inAllPaths[i]) 
     visited[i] = true; 
     if (dfs(source)) 
     inAllPaths[i] = false; 
     visited[i] = false; 

К сожалению, это все еще имеет экспоненциальный худший случай при поиске пути. Вы можете исправить это, изменив поиск на поиск по ширине. Если я не ошибаюсь, это должно дать вам производительность O (VE).

Answer 2

Запустите DFS с вашего начального узла и сохраните свой собственный стек, который сообщает вам, какие узлы вы видели в любой момент времени. Позаботьтесь о циклах: если вы дважды видели узел, у вас есть цикл, и вам нужно прервать свой текущий путь. Старайтесь не посещать родительский узел, чтобы избежать циклов длины 1 (добавьте параметр parent в свою функцию DFS, это поможет).

Затем, когда вы достигнете узла назначения, выведите содержимое своего стека.

Как только DFS закончит, у вас будут все пути.

Answer 3

Для этой проблемы я бы сначала получил дерево t, сформированное из DFS на одном из ваших целевых узлов u. Затем, цвет все узлы, позволяет сказать, что синий, которые находятся в поддереве ы коренится в вашей второй целевой узел ст.

For each node k in subtree s, 
    if k has an edge to a non-blue node x 
    then k is true and x is true. 

Также знак v как истинный. Наконец, я бы использовал рекурсивную функцию вплоть до листьев. Кое-что как

function(node n){ 
    if(n = null) 
     return false 
    if(function(n.left) or function(n.right) or n.val){ 
     n.val = true 
     return true 
    } 
    else 
     return false 
} 

Все узлы, помеченные как истинные, будут вашими узлами на путях от u до v.(Вершины + Края), поскольку DFS = (V + E) для петель не более (V) не регрессивно (V)

Answer 4

вершина находится по пути от А до В, если она достижима от A и B от нее можно добраться.

Итак: сделайте заливку заливки, начиная с A. Отметьте все эти вершины. выполните заливку заливки, начиная с B и следующих краев в обратном направлении. Все отмеченные вершины, которые вы встречаете, являются частью решения.

Answer 5

Я знаю, что это было какое-то время, но я пришел сюда, чтобы найти какой-нибудь алгоритм, чтобы найти все пути (не только кратчайший путь) в SQL или Java, и я нашел эти три (я просто опубликую их, чтобы сохранить организованные концепции):

• Java

  http://introcs.cs.princeton.edu/java/45graph/AllPaths.java.html (зависимостей: Graph, ST, Set, в, находятся в http://introcs.cs.princeton.edu/java/45graph/)

• SQL (PostgreSQL).

  Проверить WITH RECURSIVE transitive_closure(a, b, distance, path_string) AS

  http://techportal.inviqa.com/2009/09/07/graphs-in-the-database-sql-meets-social-networks/

• PL/SQL (Oracle)

  https://forums.oracle.com/forums/thread.jspa?threadID=2415733

  select pth as "Path", distance as "Distance" 
  from (
      select connect_by_root(n1) || sys_connect_by_path(n2,'>') pth ,n2, level as distance 
      from -- Edge List Table 
      (select 'A' n1,'B' n2 from dual 
      union all select 'A','C' from dual 
      union all select 'B','C' from dual 
      union all select 'B','D' from dual 
      union all select 'D','G' from dual 
      union all select 'C','G' from dual 
      union all select 'D','I' from dual 
      union all select 'C','E' from dual 
      union all select 'E','F' from dual 
      union all select 'F','G' from dual 
      union all select 'F','H' from dual 
      ) links 
      start with n1='A' 
      connect by nocycle prior n2=n1) 
      where n2 = 'G'; 
  

  Результат:

  Distance Path 
  3 A>B>C>G 
  5 A>B>C>E>F>G 
  3 A>B>D>G 
  2 A>C>G 
  4 A>C>E>F>G 
  

Если вы разместите комментарии, строки start with n1... и where n2... запрос вернет все пути на всем графике.