FIFO 대기열이있는 Bellman-Ford는 반복 속도를 어떻게 올립니까?

Question

내 강연자는 다음과 같이 언급합니다.

• 루프 1 반복의 실행 시간을 줄이십시오. 효율적인 휴식 시간을 줄 수있는 가장자리 만 고려하십시오.

• v에서 나가는 가장자리가 마지막으로 d [v]가 감소 된 이후로 이완되지 않은 경우에는 정점 v가 활성화됩니다.

• 활성 정점에서 나가는 가장자리에서 휴식을 수행합니다. 대기열 데이터 구조에

• 저장 활성 정점.

제 질문은, FIFO 큐가 Bellman-Ford의 반복을 어떻게 빠르게할까요? 어떤 상황에서 당신은 'enqueue'합니까?

Answer 1

대기열은 활성 노드를 추적하는 데 편리한 데이터 구조이기 때문에 존재합니다.

노드에 연결된 엣지를 느슨하게하려고 할 때 노드를 대기열에 추가합니다. 노드에 도달하면 활성 노드에서 해당 노드로 모든 에지가 완화됩니다.

이러한 단계를 수행하면 Bellman-Ford 알고리즘이 Dijksta's algorithm에 가까운 것으로 변환됩니다. 노드가 활성 인 경우

---

, 그것은 다음 고려 달려있다. 또한 은 노드를 방문 했으므로 이미 알고있는 모든 것을 결정한 것입니다. 아직 도달하지 않은 노드는 입니다. 방문한 노드는입니다.

당신은 색상과 같은 세 가지 상태 생각할 수 있습니다. 당신은 초기 노드가 활성 색, 그리고 모든 다른 방문하지 않은 인되면서 시작. 이동하면 활성 색이 바깥쪽으로 이동하여 을 둘러싼 경계선이 노드를 방문합니다. 당신은 더 이상 활성 노드가 없을 때 당신은 완료하고, 모든 가을 방문 채색된다.

---

대기열에 대한 대안으로 두 개의 목록을 사용할 수 있습니다. 첫 번째 노드에는 현재 고려중인 활성 노드와 두 번째 목록에 넣은 활성 노드가 새로 포함됩니다. 첫 번째 목록을 모두 사용한 후에는 목록을 비우고 두 목록을 서로 바꿉니다. 대신 하나의 큐를 사용하여 현재 반복과 다음 반복 사이에 뚜렷한 경계를 두지 않고 반복을 혼합합니다.