DAG에서 노드를 통과하는 최단 경로 수를 계산합니다.

Question

DAG에서 특정 노드를 통과하는 경로 수를 계산하는 알고리즘을 찾고 있습니다 ('betweenness'개념과 비슷 함). 다음 조건이 있습니다. 및 제약 조건 :

모든 노드가 아니라 그래프에서 소스/대상 노드 집합에 대한 계산을 수행해야합니다. 즉 중간 노드 n에 대해 노드 집합에서 몇 개의 가장 짧은 경로가 있는지 알고 싶습니다. S는 노드 D의 집합을 통과시킵니다 (별개로, 적어도 하나의 비공유 노드가있는 두 개의 경로를 의미 함)

DAG가있을 수 있다고 생각하는 알고리즘은 무엇입니까? 매우 크지 만 가장자리가 희박하고 암탉 노드의 깊은 중첩 루프에는 ce 기본 설정이 제공되지 않습니다.

Answer 1

Src/Dest 노드의 각 쌍에 너비가 큰 첫 번째 검색을 사용하고 경로에 지정된 노드가있는 노드를 찾을 수 있습니다. 최단 경로를 찾았 으면 크기를 늘리는 경로에 도달 할 때까지 계속 대기열을 비우도록 검색을 약간 수정해야합니다. 이렇게하면 최단 경로가 여러 개인 경우 무작위 적으로 우습게 구속되지 않습니다. 물론 이것은 가중치가없는 그래프의 옵션 일뿐입니다.