Dijkstra 기록

560 단어
재료.
  • ① G v 는 노드 이 고 E 는 변 이 므 로 가중치
  • 를 알 아야 한다.
  • ② array d [v] 원점 에서 노드 v 까지 의 최 단 경로
  • ③ array pai / pre [v] 노드 v 의 전구 노드
  • 알고리즘 프로 세 스
  • 첫 번 째 초기 화, 원점 은 s, d [s], 0, 나머지 노드 i d [i] 무한
  • 두 번 째 단계 (집합 S 와 집합 Q, S + Q = V 가 존재 함) ① 시작: S 는 비어 있 고 Q 는 V ② 진행: Q 에서 원점 에서 가장 가 까 운 결점 u 를 선택 하여 Q 에서 S 로 이동한다.(시작 할 때 u 는 원점) u 가 가리 키 는 모든 변 을 이완 시 키 고 개선 하면 d [] 와 pre []
  • 를 업데이트 합 니 다.
    알고리즘 사상
    Dijkstra                     ***   ***
    

    의혹: u 가 S 에 가입 한 후 d [u] 는 s 에서 u 까지 의 최 단 경로 로 책 을 보 는 증명

    좋은 웹페이지 즐겨찾기