| V | = n 및 | E | = m 인 무향 (길이 없음) 그래프 G = (V, E)와 2 개의 꼭지점 v, w가 주어지면최단 경로의 수를 찾는 알고리즘
나는이 문제와 함께 일해 왔지만 실행 시간을 O (m + n)이되게하는 데 어려움이있다.
실행 시간은 O (m + n)이어야한다.이 그래프는 방향이없고 가중치가 없기 때문에이 방법을 시도했습니다. BFS를 사용하여 가장 짧은 v-w-path의 길이를 결정하십시오. 그런 다음 DFS를 사용하여 두 개의 노드가 연결되고 경로 길이가 BFS의 출력과 같도록 v-w 최단 경로 수를 찾습니다. 그러나이 계획의 실행 시간은 O (m + n) + O (m + n)입니다.
또한 Dijkstra 알고리즘을 수정하려고했습니다. 방문 노드 집합에 노드가 추가 될 때 최단 경로 길이와 최단 경로 번호를 저장합니다. 그리고 저는 실행 시간의 계산에 매달 렸습니다.
이 질문은 Dijsktra's algorithm의 수정을 찾고 있습니다. Dijkstra의 알고리즘을 사용하면 각 노드에 대해 해당 노드에 대한 최단 경로의 길이를 유지 관리하고 이웃 노드에 대한 최단 경로 및 해당 인접 노드에서 노드로의 단순 링크의 길이를 기반으로 한 노드에서이를 업데이트합니다 문제의.
각 노드에서 가장 짧은 경로의 길이, 경로의 최단 경로에 선행 할 수있는 노드의 테이블 및 해당 노드에 대한 최단 경로 수 이 이웃들에 대한 최단 경로 수의 합계 여야합니다. 노드에 대한 새로운 최단 경로를 찾으면 (최단 경로가 이전보다 짧으면)이 정보를 모두 삭제하거나 경로의 두 번째 마지막 노드에 대해 해당 테이블의 항목을 업데이트합니다. 새 경로가 해당 노드에 대한 이전 최단 경로와 동일한 길이
정말 고마워요. 매우 도움이됩니다. 달리기 시간에 대한 정보를 좀 더 주시겠습니까? 나는 주어진 알고리즘의 실행 시간을 결정하는 데 좋지 않으며, 실제로 그것을하는 법을 배우기를 원한다. 그걸로 나를 도울 수 있니? –
Wikipedia의 복잡도 정보를 살펴보면 각 버텍스를 한 번만 방문하면 큰 그래프의 경우 우선 순위 큐 계산을 실행하는 데 대부분의 시간을 소비하여 처음 방문 할 정점을 알아낼 수 있음을 알 수 있습니다. 정점을 방문 할 때 테이블 항목을 추가 또는 수정하고 경로 합계를 늘리거나 테이블 항목을 지울 필요가 있습니다. 표를 지우면 많은 항목을 삭제할 수 있지만 각 항목을 작성할 때이 비용을 고려하면 항목 당 비용이 적게 듭니다. 따라서이 모든 추가 작업이 O (n) 비용에 전혀 영향을 미치지 않을지 의심 스럽습니다. – mcdowella
O (N)에서 수정 된 BFS를 사용하여 여러 경로 수를 확인할 수 있습니다. 다음은 solution입니다.
무엇을 이미 시도 했습니까? – thb
게시 할 때 이미 시도한 것을 말해주십시오. 처음에는 검색하지 않고도 운동 결과를 묻는 것처럼 보이지 않습니다. 확실하지 않습니다.) – Mitvailer
나는 가장자리가 가중치가 있습니까? – templatetypedef