0
는 난이시작하여 단일 노드로 끝나는 무향 그래프에 모든 점을 포함 경로의 최단 조합
k는 경로s의 개수algorithm(k, s)가 시작 및 종료이다 필요 노드
모든 노드가 서로 연결되는 무향 그래프 노드 n 번호 부여는 모든 노드를 통과하는 경로를 k 반환의 k 경로로 커버되는 거리의 합이 가장 짧습니다.
예. n = 10이 주어지면, algorithm(2,5)은 나에게 2 개의 배열 배열을 줄 수 있습니다. 두 배열에 의해 커버되는 거리의 합이 가장 짧고 모든 노드가 가로 지르게됩니다.
[[5,1,2,3,10,5],[5,4,6,7,8,9,5]]
Djikstra의 알고리즘은 하나 개의 노드에서 다른 최단 경로를 발견,하지만 k 경로의 최단 조합.
엔 알고리즘은 k 경로의 최단 경로가 아닌 한 노드에서 다른 노드로 최단 경로 수를 찾습니다.
모든 n 노드가 포함되도록 노드 s으로 시작하고 끝나는 k 경로의 최단 조합을 찾는 데 도움이되는 알고리즘은 무엇입니까?
우리는 DFS를 사용할 때마다 매번 경로의 길이를 계산함으로써 그렇게 할 수 있다고 생각합니다. 우리가 k에 도달하면 다음 노드가 시작 노드인지 여부를 확인합니다. 참인 경우 참, 그렇지 않은 경우 거짓입니다. 시작 노드 다음에 다른 노드를 선택할 때마다 (즉, 가중치가없는 그래프라고 가정) 매번 다른 가능성을 갖기 때문에 모든 가능성을 반복합니다. – user3378649