2
인접 행렬을 사용하여 비 가중 그래프에서 두 노드 간의 최단 경로를 결정하는 알고리즘을 찾고 있습니다. 나는 Dijkstra와 Bellman - Ford를 알고 있지만 발견 된 노드 중 두 노드 사이의 최단 경로를 결정하는 것은 없습니다.가중치가 부여 된 그래프/트리의 주어진 노드 간 최단 경로
어떤 도움을 크게 apreciated된다
A
답변
5
하나의 간단한 옵션은 두 번째 노드가 발견 될 때까지 첫 번째 노드에서 시작하는 폭 우선 검색을 실행하는 것입니다. 각 노드에 상위 포인터를 저장하면 첫 번째 노드에서 두 번째 노드까지 경로를 읽을 수 있습니다. 또한 이것은 그래프의 크기에서 선형 시간으로 실행됩니다.
희망이 도움이됩니다.
+0
그것은 아주 좋은 생각입니다. 고마워요! –
+0
잘했습니다. 다시 한 번 감사드립니다! –
관련 문제
- 1. 가중치가 부여 된 국가 간 무역 네트워크를 시각화하는 방법은 무엇입니까?
- 2. 가중치가 부여 된 그래프에서 두 노드 간의 최단 경로를 찾는 가장 효율적인 (Big O) 알고리즘
- 3. 세대 간 주소 간 최단 거리/경로
- 4. 링크 된 그래프의 최단 경로
- 5. 그래프에서 노드 간 최단 거리 찾기
- 6. 유향 그래프의 최단 경로 찾기
- 7. DAG 최단 경로
- 8. 연료 제한이있는 최단 경로
- 9. 지도의 최단 경로
- 10. Matlab dijkstra 최단 경로 : 노드 목록
- 11. 두 노드 사이의 최단 경로 찾기 (정점)
- 12. 주어진 MAZE c에서 K 번째 최단 경로
- 13. 주어진 꼭지점에 대한 모든 최단 경로
- 14. 두 노드 간의 최단 경로 수
- 15. 연료 탱크가있는 최단 경로
- 16. Dijkstra의 최단 경로 - HackerRank
- 17. 두 노드 사이의 최단 경로 찾기 더 이상 아이디어가 없습니다
- 18. 여러 세트의 최단 경로
- 19. Neo4jrb로 최단 경로 찾기
- 20. Networkx - 최단 경로 길이
- 21. R, 최단 경로 결정
- 22. 최단 경로 알고리즘 개선
- 23. Dijsktra의 최단 경로 알고리즘
- 24. 그래프의 최단 경로 수
- 25. 가중치가없는 최단 경로
- 26. Giraph 최단 경로 예제
- 27. 가중치가없는 그래프의 최단 경로 찾기
- 28. k 번째 최단 경로 찾기?
- 29. 최단 경로 알고리즘 업데이트
- 30. 그래프의 최단 경로
이 질문은 너무 일반적인/이론적으로 cs.stackexchange.com에서 더 잘 대답 할 수 있습니다. 그래프 태그를 참조하십시오 : http://cs.stackexchange.com/questions/tagged/graphs –
[인접 행렬에서 최단 경로를 찾으려면 Dijkstra 알고리즘을 사용할 수 있습니다] (http://stackoverflow.com/questions/8379866/) using-dijkstra-algorithm-to-find-shortest-path-in-anacacency-matrix)를 사용합니다. 또한 [이 논문] (http://www.mpi-inf.mpg.de/departments/d1/teaching/ss12/AdvancedGraphAlgorithms/Slides14.pdf)에서는 행렬 곱셈을 사용하여 최단 경로를 계산하는 방법을 설명합니다. –
호기심에서 Dijkstra의 알고리즘과 Bellman-Ford를 사용하여 두 노드 간의 최단 경로를 찾을 수 없다고 생각하는 이유는 무엇입니까? – templatetypedef