Dag의 최단 경로

Question

사이의 최단 경로를 찾는 데 필요한 s 및 t 꼭지점이있는 그래프가 있습니다. 그래프에는 다음과 같이 대문자로 사용하려는 많은 특수 속성이 있습니다.

• 그래프는 DAG (directed acyclic graph)입니다.
• 전통적인 O (| V + E |)보다 빠른 O (| V |) 시간에 위상 적 정렬을 만들 수 있습니다.
• 토폴로지 정렬 내에서 s는 목록의 첫 번째 항목이고 t는 마지막 항목입니다.

버텍스의 토폴로지 종류를 얻은 후에는 현재의 다이크 스트라의 균일 비용보다 더 빠른 최단 경로를 찾을 수 있다고 말했지만, 알고리즘을 찾을 수없는 것 같습니다.

의사 코드는 크게 감사하겠습니다.

EDITS : s에서 t까지의 모든 경로는 동일한 수의 모서리를 갖습니다. 가장자리에 무게가 있습니다. 최저 비용 경로를 찾고 있습니다.

Answer 1

나는 내 직감에 반하여 숙제가 아니라고 생각합니다. 토폴로지 순서에 따라 제공되는 정보를 활용해야합니다. 토폴로지 순서에 따라 노드 n을 검사 할 때마다 n에 대한 모든 가능한 경로를 이미 통과했음을 보장 할 수 있습니다. 이 사용은 당신이 위상 순서 (의사)의 하나의 선형 스캔으로 최단 경로를 생성 할 수 있는지 명확 :

Graph g 
Source s 
top_sorted_list = top_sort(g) 

cost = {} // A mapping between a node, the cost of its shortest path, and 
      //its parent in the shortest path 

for each vertex v in top_sorted_list: 
    cost[vertex].cost = inf 
    cost[vertex].parent = None 

cost[s] = 0 

for each vertex v in top_sorted_list: 
    for each edge e in adjacensies of v: 
     if cost[e.dest].cost > cost[v].cost + e.weight: 
     cost[e.dest].cost = cost[v].cost + e.weight 
     e.dest.parent = v 

지금 당신이 목적지로의에서 모든 최단 경로를 찾아 볼 수 있습니다. 비용 매핑에서 목적지를 찾아 부모를 얻고 부모가 s 인 노드를 얻을 때까지이 과정을 반복하면 가장 짧은 경로를 얻을 수 있습니다.