1
그래프 G는 방향이없는 그래프이며 모든 에지의 가중치는 동일합니다. u, v는 주어진 2 개의 꼭지점, O (| V |)의 그래프 G에서 u와 v 사이의 최단 경로 수를 찾는 방법은 무엇입니까?O (| V |)의 무향 그래프에서 u와 v 사이의 최단 경로를 찾는 방법은 무엇입니까?
| V | G에서 정점의 수를 나타냅니다.
A
답변
1
Dijkstra는 욕심이 많고 증가하는 순서로 경로를 소비하기 때문에. 나중에 음의 가중치가 발견되면 이전에 발견 된 경로가 더 이상 최단 경로가 아니므로 Dijkstra가 실패 할 수 있습니다.
예 :
A -> B (5)
A -> C (5)
C -> B (-10)
익스트라는 A- 확인할> B (5) B A에서 최단 경로 인 보이지만 실제로, 최단 경로 A-> C 것이다 - (> B - 5)
관련 문제
- 1. 무 방향성 그래프에서 두 정점 사이의 모든 최단 경로를 찾는 방법은 무엇입니까?
- 2. 무향 그래프에서 사이클 찾기 v 유향 그래프에서 사이클 찾기
- 3. 그래프에서 가장 긴 경로를 찾는 방법은 무엇입니까?
- 4. 그래프에서 두 vertives 간의 최단 경로를 찾는 방법은 무엇입니까?
- 5. 두 개의 꼭지점 사이의 무향 그래프에서 특정 모서리 찾기
- 6. 무향 그래프 경로를 찾는 알고리즘
- 7. 암시 적 그래프에서 최단 경로를 찾는 연결 검사의 수 최소화하기
- 8. O (| V |^2)의 Prim의 MST 알고리즘
- 9. 체스 판에서 두 지점 사이의 최단 경로를 찾는 방법은 무엇입니까?
- 10. $. $$ V
- 11. 최단 경로의 수를 찾는 알고리즘
- 12. 그래프에서 제약 조건을 만족하는 최단 경로를 찾는 방법
- 13. 그래프에서 깊이가 제한된 경로를 찾는 방법은 무엇입니까?
- 14. 알고리즘이 무향 된 트리에서 경로를 찾는 것
- 15. O (V + E) 공간 복잡도의 의미는 무엇입니까?
- 16. 그래프에서 경로가 아닌 최단 경로
- 17. 무 방향성 그래프에서 s (시작점)부터 v (모든 점)까지의 최단 경로가 고유한지 여부를 찾는 방법은 무엇입니까?
- 18. 의 Hyper-V 가상화
- 19. 가중치가 부여 된 그래프에서 두 노드 간의 최단 경로를 찾는 가장 효율적인 (Big O) 알고리즘
- 20. 특정 비용의 무향 그래프에서 경로 찾기
- 21. 그림 대 V 사이의 차이
- 22. O (| V | + | E |)에서 인접성 목록의 역함수
- 23. 최소 비용 경로를 얻기위한 최단 경로 수정
- 24. 전체 그래프에서 두 꼭지점 간의 최단 경로
- 25. 고도를 사용하여 최단 경로를 찾는 그래프 알고리즘
- 26. 방향 및 무향 그래프에서 모든 사이클 찾기
- 27. 무향 그래프에서 브릿지 찾기?
- 28. 무향 그래프에서 4 사이클
- 29. 파이썬 목록에서 점 사이의 최단 거리를 찾는 클리너 방법은 무엇입니까?
- 30. 행렬에서 최단 경로를 찾는 방법