사이클에서 가장 짧은 경로를 지시 그래프

Question

나는 방향 그래프의 바이 패스의 최단 경로 예를 하나의 노드가 필요합니다 (그것은 양극에서 그래프의 모든 노드에 도달해야 입력됩니다) 제발 내가 필요로하는 경우 바랍니다 C++ 또는 알고리즘 덕분에 .........

Answer 1

당신은 minimum spanning tree을 찾아야합니다.

위키피디아의 방향 그래프에서는 this 알고리즘을 사용할 수 있습니다. 의사 코드에서

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

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