지시 순환 그래프의 모든 노드를 포함하는 최단 경로를 찾으려면 어떻게합니까?

Question

하나의 노드 에서 지시 순환 형 그래프의 최단 경로 예제가 필요합니다 (입력 노드가되는 그래프의 모든 노드에 도달해야 함).

예가 있으면 C++ 또는 알고리즘으로 필요합니다.

Answer 1

편집 : 죄송합니다. 이걸 고르는 것에 대해 @jfclavette에게 감사드립니다. 오래된 대답은 끝입니다.

해결하려는 문제는 Travelling salesman problem입니다. potential solutions이 많이 있지만 NP 완성이므로 큰 그래프는 풀 수 없습니다.

올드 대답은 :

당신은 무엇을 발견하려는 것은 그래프의 girth라고합니다. 노드에서 무한대까지의 거리를 설정하고 Floyd-Warshall 알고리즘을 사용하여 해결할 수 있습니다. 노드 i로부터의 최단 사이클의 길이는 바로 위치 ii의 엔트리이다.

Answer 2

가중치가없는 그래프의 경우 BFS가 작업을 수행합니다. 그래프에는 잠재적 인주기가 있기 때문에 방문한 노드를 추적해야합니다 (어쨌든 BFS를 위해이 작업을 수행해야 할 필요가 있음).

가중 그래프의 경우 bellman-Ford 알고리즘을 사용할 수 있습니다. 또한 사이클을 감지 할 수 있습니다.

Answer 3

비 중량의 경우 : Breadth first search. 가중치의 경우 : Dijkstra's. 의사 코드에서

Answer 4

는 :

//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가 ∞를 반환하면 그래프는 비순환 적입니다.

가장 짧은주기의 실제 경로를 반환하려면 약간의 수정 만 수행해야합니다.