다익스트라는 가중치가 서로 다른 간선에서 최단거리를 구하는 알고리즘이기 때문에,
멀리 돌아오는 ( 탐색이 늦게 되는 ) 경우가 최단 거리일 수 있습니다.
그래서 visited 처리를 하시면, 더 짧은 거리를 들고와도
visited==true 이기 때문에 아래 코드에 진입 할 수가 없습니다.
다익스트라는 가중치가 서로 다른 간선에서 최단거리를 구하는 알고리즘이기 때문에,
멀리 돌아오는 ( 탐색이 늦게 되는 ) 경우가 최단 거리일 수 있습니다.
그래서 visited 처리를 하시면, 더 짧은 거리를 들고와도
visited==true 이기 때문에 아래 코드에 진입 할 수가 없습니다.
항상 가장 가까운 곳을 탐색하기 때문에 탐색이 늦게 된 경로가 최단거리일 수 없는거 아닌가요?
간선의 가중치가 있어서,
돌아가는 길이 더 짧을 수 있습니다.
// 정점 수, 간선 수 3 3 // 출발, 도착 1 3 // 간선 (시작, 끝, 거리) 1 3 1000 1 2 1 2 3 1
경로가 발견되는 순서는 거리 순서가 아니기 때문에 우선순위 큐에서 제거되기 전에는 모르는 일입니다. 중복에 관계없이 모든 방문을 허용해야 합니다.
아직도 잘 이해가 안되네요..
위와 같은 예시에서
정점1 탐색: dist[2]=1,dist[3]=1000, 큐={2,3}
정점2 탐색: dist[3]=2, 큐={3,3}
이런 식으로 되지 않나요?
거리가 1000일 때의 정점3이 거리가 2일 때보다 먼저 큐에 들어가긴 하지만 큐에서 나오는 건 항상 거리가 짧은게 먼저 아닌가요?
제가 한 방문처리는 큐에서 나왔을때 하기 때문에 문제가 안될 거라고 생각했는데요..
작성자님 코드의 로직이 뭔지 이해가 정확히는 안 갑니다.
일단 구현하신건 다익스트라가 아닙니다.
AC를 visited를 없앴을 때 받으신 건, 구현이 bfs처럼 이루어졌기 때문인 것 같아요.
bfs처럼 이루어지면 당연히 탐색은 간선을 지난 횟수가 적을 수록 빨리 이루어지기 때문에 가중치에 따라
더 적은 거리가 나중에 들어올 수 있어요. 그래서 visited 처리를 해주면 안됩니다.
(제가 첫 댓글에 단 건 좀 적절하지 않은 답글인 것 같아요. 무시해주세요. )
priority queue를 사용하시긴 하셨는데, 원래 다익스트라에선 거리가 확정된 노드의 인접한 간선을 탐색하도록 하는데,
priority queue에 cmp 함수로 비슷한 효과를 내려고 했지만, 사람들이 priority queue에 노드의 번호까지 들고 들어가는 건 현재 확정된 노드의 번호를
나중에도 사용하기 때문이에요.
제가 위에 댓글에 첨부한 코드 부분도 해당 노드에 연결되는 곳만 탐색하는 것이 아니라
모든 노드를 검사하도록 짜져있는데, 사실 inf 처리 되어 오류가 안 난 거지만 여기서도 다익스트라 코드와는 멀다는게 느껴집니다.
답변 정정하겠습니다.
제대로 구현된 다익스트라였다면 원래 하셨던 대로 스킵 처리를 하면 정확히 맞습니다. 그런데 pq에 정점 번호만 들어가고 cmp 함수가 외부에 있는 dist를 참조하는 것은 틀린 구현입니다. cmp 함수는 삽입/삭제할 때 일어나는 heapify 과정에서만 호출되기 때문에, 아직 꺼내질 때가 되지 않은 정점이 최단거리가 감소했을 때 pq에 즉시 반영되지 못해서 pq가 모순된 상태에 빠질 수 있습니다. 물론 그때 새로 삽입되는 정점은 최신 갱신된 거리를 가지고 들어가지만 그 이전까지 삽입되었던 동일 정점들은 큐 안에서 다른 정점들과의 위치 관계가 꼬이게 됩니다.
댓글을 작성하려면 로그인해야 합니다.
dkdkdkslfkdl 1년 전
아래의 코드에서 방문처리를 안하도록 visit을 제거하니까 정답이 됐습니다
그 이유가 뭔지 궁금합니다