he1233   3년 전

처음에 다익스트라로 시도했다 n^2는 무조건 tle나는걸 알고 정렬 과정을 단축하기 위해 heap을 직접 구현하였는데, 예제는 물론 질문 게시판 내의 대부분의 테스트케이스를 확인하였지만 저에게 맞는 반례는 찾을 수 없었습니다. v,e의 숫자가 큰 경우는 입력이나 확인이 힘들어서 못하였지만..

다른분들의 글들을 보니 제 알고리즘과의 가장 큰 차이점은 push를 맨 처음에 (정점 수-1)만큼만 수행하고 이후에는 push가 없다는 것인데,

 제 코드에서는 처음에 우선순위 큐에 시작점을 제외한 모든 정점 번호를 넣고, 큐 내부 정렬은 정점 번호를 distance 배열(시작점으로부터 x번 정점까지의 최단거리)의 인덱스로 사용하여 distance 값을 기준으로 정렬시키게 하였습니다. 또한 vertex_heapindex 배열의 x번 인덱스에 heap 내의 x번 정점 위치(인덱스)를 저장하고 다익스트라 수행 중 distance값이 변경되면(기존 값보다 작아지면) vertex_heapindex 배열을 통해 변경된 정점에 해당하는 heap 인덱스 접근하고, 해당 인덱스를 기준으로 재배치를 수행시키는 개념입니다.

다른 분들은 현재 최단거리가 확정된 정점에서 연결된 간선만 넣는 형태이던데, 제가 사용한 방식은 왜 불가능한건지(어느 부분에서 논리적 문제가 있는지) 알고싶습니다.

댓글을 작성하려면 로그인해야 합니다.