dkdkdkslfkdl   1년 전

아래의 코드에서 방문처리를 안하도록 visit을 제거하니까 정답이 됐습니다

그 이유가 뭔지 궁금합니다

dolchaelatte   1년 전

다익스트라는 가중치가 서로 다른 간선에서 최단거리를 구하는 알고리즘이기 때문에,

멀리 돌아오는 ( 탐색이 늦게 되는 ) 경우가 최단 거리일 수 있습니다.

그래서 visited 처리를 하시면, 더 짧은 거리를 들고와도

visited==true 이기 때문에 아래 코드에 진입 할 수가 없습니다.


dkdkdkslfkdl   1년 전

항상 가장 가까운 곳을 탐색하기 때문에 탐색이 늦게 된 경로가 최단거리일 수 없는거 아닌가요?

sianke1991   1년 전

간선의 가중치가 있어서,

돌아가는 길이 더 짧을 수 있습니다.

zenith82114   1년 전

// 정점 수, 간선 수
3 3

// 출발, 도착
1 3

// 간선 (시작, 끝, 거리)
1 3 1000
1 2 1
2 3 1

경로가 발견되는 순서는 거리 순서가 아니기 때문에 우선순위 큐에서 제거되기 전에는 모르는 일입니다. 중복에 관계없이 모든 방문을 허용해야 합니다.

dkdkdkslfkdl   1년 전

아직도 잘 이해가 안되네요..

위와 같은 예시에서 

정점1 탐색: dist[2]=1,dist[3]=1000, 큐={2,3}

정점2 탐색: dist[3]=2, 큐={3,3}

이런 식으로 되지 않나요?

거리가 1000일 때의 정점3이 거리가 2일 때보다 먼저 큐에 들어가긴 하지만 큐에서 나오는 건 항상 거리가 짧은게 먼저 아닌가요?

제가 한 방문처리는 큐에서 나왔을때 하기 때문에 문제가 안될 거라고 생각했는데요..

dolchaelatte   1년 전

작성자님 코드의 로직이 뭔지 이해가 정확히는 안 갑니다.

일단 구현하신건 다익스트라가 아닙니다. 

AC를 visited를 없앴을 때 받으신 건, 구현이 bfs처럼 이루어졌기 때문인 것 같아요.

bfs처럼 이루어지면 당연히 탐색은 간선을 지난 횟수가 적을 수록 빨리 이루어지기 때문에 가중치에 따라 

더 적은 거리가 나중에 들어올 수 있어요.  그래서 visited 처리를 해주면 안됩니다.

(제가 첫 댓글에 단 건 좀 적절하지 않은 답글인 것 같아요. 무시해주세요. )

priority queue를 사용하시긴 하셨는데, 원래 다익스트라에선 거리가 확정된 노드의 인접한 간선을 탐색하도록 하는데,

priority queue에 cmp 함수로 비슷한 효과를 내려고 했지만, 사람들이 priority queue에 노드의 번호까지 들고 들어가는 건 현재 확정된 노드의 번호를 

나중에도 사용하기 때문이에요. 

제가 위에 댓글에 첨부한 코드 부분도 해당 노드에 연결되는 곳만 탐색하는 것이 아니라 

모든 노드를 검사하도록 짜져있는데, 사실 inf 처리 되어 오류가 안 난 거지만 여기서도 다익스트라 코드와는 멀다는게 느껴집니다.

zenith82114   1년 전

답변 정정하겠습니다.

제대로 구현된 다익스트라였다면 원래 하셨던 대로 스킵 처리를 하면 정확히 맞습니다. 그런데 pq에 정점 번호만 들어가고 cmp 함수가 외부에 있는 dist를 참조하는 것은 틀린 구현입니다. cmp 함수는 삽입/삭제할 때 일어나는 heapify 과정에서만 호출되기 때문에, 아직 꺼내질 때가 되지 않은 정점이 최단거리가 감소했을 때 pq에 즉시 반영되지 못해서 pq가 모순된 상태에 빠질 수 있습니다. 물론 그때 새로 삽입되는 정점은 최신 갱신된 거리를 가지고 들어가지만 그 이전까지 삽입되었던 동일 정점들은 큐 안에서 다른 정점들과의 위치 관계가 꼬이게 됩니다.

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