-1
이진 행렬의 두 점 사이에서 최단 경로를 찾고 싶습니다.이진 행렬의 두 점 사이의 최단 경로
매트릭스의 소스와 대상은 사용자가 지정합니다. 우리는 행렬에서 1 인 위치를 선택할 수 있으며 왼쪽, 오른쪽으로 대각선으로 이동하여 &을 올립니다.
대각선으로 이동하는 것이 루트 2이면 그렇지 않습니다. 따라서 알고리즘을 찾는 방법을 원합니다.
A
답변
3
당신이 찾고있는 것은 단일 소스 최단 경로 알고리즘입니다. 즉, 그래프에서 소스 노드를 선택하고 모든 노드 또는 하나의 노드에서 가장 짧은 노드를 찾습니다. 여러 알고리즘이 목적을 위해 존재 -
제안 사항을 읽어보고 용도에 맞는 것을 선택하십시오.
+0
Bellman Ford는 Dijkstra 알고리즘보다 최악의 성능을 나타 내기 때문에 일반적으로 포지티브 에지가있는 그래프에는 사용되지 않습니다. Floyd Warshall은 모든 쌍의 최단 경로입니다. 동일한 그래프에서 많은 쿼리를 사용하면 좋습니다. – nhahtdh
+0
나는이 모든 알고리즘을 읽었지 만 매트릭스의 크기가 400 * 400과 같이 크기 때문에이 알고리즘을 적용하기가 어렵습니다. 위의 알고리즘은 대각선 거리를 결정할 수 없기 때문에. –
+0
plz 좀 도와주세요 ... 나는 알고리즘과 C 코드를 필요로하는 바이너리 행렬 (400 * 400)을 파일, 소스 및 대상 축 (사용자 = 60,9 및 d = 400,300)으로 가정합니다. 대각선으로 이동 한 경우 루트 사이의 최단 경로를 찾거나 그렇지 않으면 1 –
관련 문제
- 1. 세 점 사이의 최단 경로
- 2. 좌표계의 두 점 사이의 최단 경로
- 3. 알고리즘 : 모든 점 사이의 최단 경로
- 4. 하스켈을 사용하여 그리드의 두 점 사이의 최단 경로 찾기
- 5. 두 점 사이의 최단 거리를 가져옵니다
- 6. 두 노드 사이의 최단 경로 찾기 (정점)
- 7. 두 도형 사이의 최단 경로 찾는 법?
- 8. 여러 점 사이의 최단 거리
- 9. AI 검색 문제 : 장애물이있는 평면에서 2 점 사이의 최단 경로
- 10. 게임 경로 찾기 : 가중치가 적용된 두 점 사이의 최단 경로 찾기
- 11. 두 점 사이의 가장 긴 경로
- 12. Starfield 애니메이션을위한 두 점 사이의 각도 경로
- 13. 두 점 사이의 경로 찾기 R
- 14. android : 두 점 사이의 거리를 계산하는 방법
- 15. 두 주소 간의 최단 경로
- 16. n GPS 점 사이의 최단 거리 계산
- 17. 특정 노드와 점 사이의 최단 거리
- 18. 두 점 사이의 시간 측정
- 19. 두 줄 사이의 최단 거리
- 20. 두 점 사이의 부드러운 곡선?
- 21. 구면의 Geodesics (최단 거리 경로) 사이의 교차점
- 22. 이진 검색 트리에서 리프에 대한 최단 경로
- 23. 두 노드 사이의 최단 경로 찾기 더 이상 아이디어가 없습니다
- 24. FK를 사용하여 데이터베이스의 두 열 사이의 최단 경로 찾기
- 25. 장애물이있는 점 A에서 점 B까지의 Java 2D 배열 최단 경로
- 26. 두 점 사이의 방향
- 27. 두 행렬 간의 최단 경로
- 28. 전체 그래프에서 두 꼭지점 간의 최단 경로
- 29. k 번째 최단 경로 찾기?
- 30. C 프로그래밍 언어, 최단 경로
http://en.wikipedia.org/wiki/Dijkstra%27s_algorithm –
먼저 행렬에서 _graph_를 생성하십시오. 힌트 : 모든 가로/세로 인접 셀 사이에는 1의 무게가 있고 가장자리는 대각선으로 인접한 모든 셀 사이의 가장자리에 무게 sqrt (2)가 있습니다. 그런 다음 Dijkstra를 적용하십시오. –