iamrane   2년 전

다익스트라 알고리즘은 한번 방문한 노드는 재방문을 하지 않는데 사이클을 무한으로 돌 수가 있나요?

아래 그림에서 0에서 2까지의 최단경로를 탐색한다고 하면 0->1>->2로만 갈 수 있는거 아닌가요? 0에서는 1로만 갈 수 있고, 1에서는 0은 이미 방문했기에 2로만 갈 수 있지 않나요?

preview

jihwan_0319   2년 전

제가 아는 다익스트라는 한번 간 노드를 다시 안가는 내용은 없습니다.

물론 가중치가 다 양수이면 다시 돌아왔을 때 무조건 그때 거리가 더 기니까 자연스럽게 그런 역할을 합니다.

leeingyun96   2년 전

Mark all nodes unvisited. Create a set of all the unvisited nodes called the unvisited set.


위키피디아긴 한데 간 노드를 방문처리해서 다시 안 가는 게 정석적인 구현일걸요.


"(지금 그림)음수 사이클이 있으면 그때 종료하고 뭔가를 리턴해야 하는데, 그렇지 않고 적당히 도달하고 끝난다" 혹은 "(일반적인 우선순위큐 구현)음수 사이클이 있으면 그때 종료하고 뭔가를 리턴해야 하는데, 진짜로 무한 사이클을 돌아서 타임아웃이 나든 에러가 나든 한다."가 문제라고 보는 게 더 맞을 것 같아요.

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