Dijikstra 알고리즘에서 방문한 노드는 고려되지 않나요?

Question

현재 Dijikstra 알고리즘에 대해 공부하고 있습니다. 질문 그대로 이 알고리즘은 방문한 노드를 closed 상태로 놓고 , 방문하지 않은 인접한 노드를 향해 현재까지의 최단 거리를 업데이트합니다. 만약 다른 방향의 노드가 최저 비용임을 인지하면 그 노드로 다시 돌아서 갑니다. 그런데 트리든 그래프든 노드를 방문할 때에는 순회(traversal)를 하지 않나요? 그렇다면 다른 경로를 찾았을 때 돌아가는 비용 역시 발생한다고 하는데 이론서에서는 그런 비용은 발생하지 않는다고 합니다. 제가 생각하는 트리구조는 다른 방향의 자식 노드를 방문할 때에는 부모 노드까지 올라가서 다시 내려가야 하는데 이 알고리즘은 그것을 고려하지 않으니 헷갈립니다. 아시는 분은 답변 부탁드립니다.

누렁렁이 · Accepted Answer

우선순위큐를 이용해서 그렇습니다.하나의 노드에서 다른 노드를 순회할 때, 다음 방문할 노드를 우선순위 큐 (비용이 더 낮은 노드를 먼저 pop 하는 큐)에서 가져옵니다.즉 다른 경로를 찾았을 때 돌아가지 않아도 이미 우선순위 큐에서 꺼낸 값을 그대로 쓰기 때문에 다시 역방향으로 탐색하는 과정이 필요가 없는겁니다.

YYDG · Answer

윗노드로 가는 비용을 줄이기 위해 무엇을 해야할까요?

Dijikstra 알고리즘에서 방문한 노드는 고려되지 않나요?

2개의 답변

Q&A 목록