1
nlogn의 하한선을 얻으려면 내가 알고있는 정렬 알고리즘을 사용하고 Dijkstra의 단일 소스 최단 경로 문제를 변형/적용합니다.Dijkstra 단일 소스 경로로 정렬 변환 하시겠습니까?
숫자 값을 기반으로 그래프를 작성해야하며 Dijkstra가 순서대로 트래버스 할 필요가 있다는 것을 알고 있습니다. 나머지는 어떤 도움을 주며 어떻게 평가합니까?
A
답변
0
star graph (하나의 중앙 노드와 여러 개의 "외부 링 노드"가있는 그래프, 각 외부 링 노드는 중앙 노드에 연결하는 한 개의 에지를 가짐) n 개의 외부 링 노드가있는 것으로 생각하십시오. 그런 다음, 외부 링의 각 노드 v i을 비용이 어레이의 i 번째 항목 인 에지로 중앙 노드에 링크하십시오. 그런 다음 중앙 노드에서 시작하는 Dijkstra의 알고리즘을 실행하면 알고리듬은 정렬 된 순서로 배열 요소를 나열하는 것과 같이 거리의 오름차순으로 외부 링 노드를 각각 방문합니다.
희망이 도움이됩니다.