Dijkstra의 알고리즘의 Dial 버전에서 이중 연결 목록이 사용되는 이유는 무엇입니까?

Question

여러 논문과 슬라이드 덱 Dijkstra의 단일 소스 최단 경로 알고리즘에 대한 Dial의 구현을 살펴 보았습니다. 그들은 모두 양동이가 이중 연결 목록으로 저장된다고 말합니다. (예 : http://www.cs.ucsb.edu/~suri/cs231/ShortestPaths.pdf, http://www.acsu.buffalo.edu/~nagi/courses/684/4.shortestpath.pdf). 그러나 필요한 작업은이 (지금까지 내가 볼로) 위치 :

1. 확인 양동이가

2. 은 (순서는 중요하지 않습니다)

양동이에 노드를 추가 비어있는 경우

3. 전달 노드를 삭제하는 동안 버킷을 반복합니다.

그들 모두는 단지 새로운 노드 목록의 시작 부분에 포인터를 변경하고 기존의 제 1 노드의 다음 포인터를 변경, 2 (쉽게 싱글 링크드리스트를 수행 할 수 있습니다 양동이에).

그래서 왜 이중 연결 목록이 바람직하지 않은 이유가 누락 되었습니까?

Answer 1

나는 그것을 알아 냈다. 내가 놓친 연산은 버켓을 반복하면서 인접한 버텍스를 이동시켜 다른 버킷에서 노드를 삭제해야한다는 것입니다. 이는 이중 연결 목록의 경우 O(1), 단일 연결 목록의 경우 O(size of bucket)에서 수행 할 수 있습니다.