인접 행렬이 주어지면 각 점을 적어도 한 번 탐색하고 이동 횟수를 반환하면서 두 노드 사이의 최단 경로를 어떻게 찾을 수 있습니까?인접 행렬의 길 찾기
예 I 그래서 추천 인접 행렬을
int[][] points = { { 0, 1 },{ 0, 2 },{ 1, 2 },{ 1, 3 },{ 3, 4 } };
...
가 0 1 2 3 4
0 [0] [1] [1] [0] [0]
1 [1] [0] [1] [1] [0]
2 [1] [1] [0] [0] [0]
3 [0] [1] [0] [0] [1]
4 [0] [0] [0] [1] [0]
0에서 최단 경로 - 4 인 (0-2) (2-1) (1-3) (3-4) 4로 계산한다.
나는 더 이상 갈 방법이 없다. 최소 스패닝 트리 솔루션일까요? 미리 감사드립니다.
Dukeling의 제안에 따라 해밀턴 경로 문제로 축소하여 NP 하드임을 확실히 확인하십시오. 이 문제를 해결하기 위해 폴리 시간 알고리즘 X가 있다고 가정합니다. 그렇다면 우리는 X 방향으로 끝나는 모든 다른 꼭지점을 방문하는 두 꼭지점 사이의 최소 길이 경로를 찾는 문제를 X에게 요청할 수 있음을 의미합니다.
모든 꼭지점을 최소 한 번 방문해야하므로이 경로의 최소 길이는 (| V | - 1)입니다. 그래서 우리 알고리즘이 크기 (| V | - 1)의 경로를 제공한다면 우리는 모든 쌍의 꼭지점에 알고리즘 X를 적용 할 수 있기 때문에 폴리 시간에서 해밀턴 경로의 결정 성 문제에 대답했습니다 (그 중 O (n^2)).
동적 프로그래밍/재귀를 사용하는 방법이있을 수 있지만 폴리 시간임을 증명할 수는 없습니다. 모든 정점을 방문하는 s에서 t까지의 최단 경로는 G/{s} 그래프를보고, i에서 t까지의 최단 경로가 무엇인지를 Neighbors (s)에 문의하여 계산할 수 있습니다. 그런 다음 우리는 s에서 t까지의 최단 경로가 이웃 중 하나 (특히 t에 대한 최단 경로로 연결되는 경로)에 추가 된 s와 같아야한다는 것을 압니다.
이것은 수업 시간 지정을 고려하지 않아야합니다. *는 이미 그것이 켜져 있음을 의미합니다. 나는 단지 학습 경험을 위해 그것을하는 방법을 알아 내려고했습니다. – mjenkins2010
좋아, 나는 뭔가를 놓쳐 버렸을거야. 나는 더 생각해야 할 것이다. 내 주장이 실종 됐다는 것을 알 수 있니? 그것은 우리가 올바른 행동 방침을 찾는데 도움이 될 수 있습니다. –
http://en.wikipedia.org/wiki/Shortest_path; 골라보세요. –
적어도 한 번씩 각 지점으로 이동 -> [해밀턴 경로] (http://en.wikipedia.org/wiki/Hamiltonian_path)와 유사하게 들리지만 효율적으로 해결하기는 쉽지 않습니다. – Dukeling
[Johnson의 알고리즘] (http://en.wikipedia.org/wiki/Johnson%27s_algorithm) [여기] (http://stackoverflow.com/q/2939877/230513)을 검토하십시오. – trashgod