next.second를 통해서 가는 것이 바로 가는 것보다 비용이 작은 경우 그 값으로 최신화를 해주고, 그래야 어디를 거쳐서 갔을 때 더 적은 비용이 발생하는지 알 수 있지 않을까요

@shg9411 님 답변 감사드립니다.

next.second를 통해서 가는 것이 발로 가는 것 보다 비용이 작은 경우 그 값으로 최신화를 해준다고 말씀해주신 부분이, dist[next.second]를 최신화 해주는 것이 아닌가요..? 

next.first를 업데이트 하지 않는 경우로 예를 들어보면,

1 2 10 

1 3 1 

3 2 2

2 5 4

이렇게 그래프가 있고, 시작점(K)이 1이라면 맨 처음에 dist배열은 전부 다 무한대로 초기화 되어 있다가 K=1을 입력 받으면서 dist[1] = 0이 됩니다. 그리고 while문을 진행하면서 dist[2] = 10, dist[3] = 1이 되고, dist[4]는 여전히 무한대입니다. 그리고 우선순위큐에 (도착지, 비용) = (3, 1), (2,10)순으로 저장이 됩니다. 

그러면 다음 반복에서 (3,1)이 pop되고, 1은 이미 방문한 정점이니까 제외하고, 2의 경우 dist[2] = 10이고, 1->3->2의 비용은 dist[3] + 2->3의 비용(next.first에 해당하는 값) 이 되어서 1 + 2 = 3이 됩니다. dist[2]보다 dist[3] + 2->3의 값이 더 작으므로 dist[2]를 3으로 최신화합니다. 그리고 우선순위 큐에 (2, 2)가 push돼서, 최종적으로 (2,2), (2,10)순으로 저장이 됩니다.(next.first를 갱신안한 버전입니다.)

그 다음엔 (2,2)가 pop되고, 1, 3은 이미 방문했으므로 4만 방문하는데, dist[4]를 dist[2] + 2->4까지의 직접적인 비용 = 3 + 5 = 8이 됩니다. 

결론적으로 dist[1] = 0, dist[2] = 3, dist[3] = 1, dist[4] = 8이 됩니다.

다른 여러 예제를 돌려봐도 next.first를 갱신 안해줘도 이런식으로 계속 올바른 답이 구해지는데 혹시 부가적인 설명 부탁드려도 될까요?ㅠㅠ

감사합니다.

우선순위 큐는 (도착지, 비용)이 아니라 (비용,도착지)입니다.

처음에 큐에 넣으시는 값이 (0,K)인 것만 봐도 알 수 있고, 비용을 우선순위로 보는게 올바른 방법이겠죠.

예를 들어주신 간선 중 2 5 4는 2 4 4를, dist[4] 값은 7을 잘못 적으신 것으로 알고 적어보겠습니다.

처음 1에 대한 정점을 갱신하면

dist[2] = 10, dist[3] = 1이 되겠죠

큐에는 (1,3)(10,2)이 들어가고요. (비용 도착지)

3을 거쳐서 갈 경우 갱신되는 곳은 2까지 가는 길 입니다.

기존에 비용 10에서 3을 거쳐 갈 경우 (1+2=)3이 더 작기 때문이죠.

큐에는 (3,2)이 들어가고 (3,2)(10,2)가 들어있습니다.

2를 거쳐서 갈 경우 4까지 가는 길은 위와 같이 기존의 INF에서 (3+4=)7로 갱신됩니다.

큐에 들어가고 큐에는 (7,4)(10,2)가 들어가게 되고

4를 통해서 가는 길이 더 빠른 경우는 없습니다.

마지막으로 2를 통해서 가는 경우 기존의 2를 갈 때의 비용(3)보다 크기에 검사하지 않고

0 3 1 7이 출력되야겠죠.

@shg9411님 답변 정말 감사드립니다! 

우선 질문하는 입장에서 예시 설명이 미흡한 점 죄송합니다ㅜㅜ 마지막에 예시를 바꾸면서 다시 확인한다고 했는데 제대로 확인하지 못한 것 같습니다.

그럼에도 불구하고 이해하기 쉽게 설명해주셔서 감사합니다.

친절한 설명 덕분에 선배님께서 하시는 말씀은 잘 이해가 되었습니다.

하지만(죄송하지만...) 아직 왜 dist[next.second]뿐만 아니라, next.first도 갱신이 되는지 잘 모르겠습니다...ㅜㅜ

다른 예를 들어서,
1 2 10
2 3 5
의 그래프가 있고, 시작점 1을 기준으로 다익스트라 알고리즘을 적용하면 결론은 dist[1] = 0, dist[2] = 10, dist[3] = 15가 됩니다.

여기서 dist[3]은 1부터 3까지 가는 최소비용을 의미합니다. 이 때 최소비용은 1->3을 바로 가든, 예시엔 없지만 다른 점 4,5,6이 존재 한다고 가정할 때, 1-4-5-6-3 이런식으로 다른 정점을 들려서 가든 상관없이, 무조건 비용이 최소인 경로로 갔을 때의 비용을 의미한다고 배웠습니다.

그리고 cur이 2이고, next가 (5,3)인경우에, next.first는 2에서 3으로 다른 정점을 거치지 않고 바로 가는 비용이라고 생각합니다. 즉 2-4-3(4는 없지만 예를 든것입니다!)같은 어느 다른 정점을 거치는 것이 아닌, 2에서 3으로 바로 갈 때의 비용입니다. 그리고 이 비용은 입력을 통해 받았습니다.

이처럼 dist[x]와 next.first의 차이는, dist는 시작점 기준으로 어떠한 정점을 들리던 상관없이, x까지의 최소비용을 나타내고, next.first는 cur 기준 next.second까지 어떠한 다른 경로도 거치지 않고, 비용의 크기도 고려하지 않는, cur에서 next.second로 바로 가는, 즉 입력을 통해 받은 비용이라고 생각합니다.

이전 문단의 cur = 2, next = (5,3)인 상황에서 51행의 dist[next.second] = dist[cur] + next.first 코드를 실행하면 이는 곧 dist[3] = dist[2] + 5 = 15가 됩니다.
이러고 나서 왜 52행을 통해서 next.first까지 dist[next.second]의 값인 15로 갱신해주는지 모르겠습니다. 2에서 3으로 바로 가는 비용은 입력받은대로 항상 5라고 생각하는데 왜 이 값을 바꿔주는지 잘 모르겠습니다.

이미 충분히 많은 도움 주셔서 답변을 안해주셔도 충분히 감사합니다! 하지만 여유가 되신다면, 오늘이 아니라 다음 기회에도 괜찮으니 선배님 조언을 마지막으로 들어보고 싶습니다ㅠㅠ 저도 다시 고민해보겠습니다! 늦은 시간에도 불구하고 친절한 설명 다시 한 번 감사드립니다!

인접행렬에 있는 비용(auto next : adj[cur])은 입력을 통해서 받은 값이 맞습니다.

현재 인접행렬에 있는 값을 바꾸는 것(next.first = dist[next.second])은 상관없이 우선순위 큐에 들어가는 값일 뿐이죠.

저때문에 더 헷갈리실 지 모르겠지만 next는 단순한 pair<int,int>를 나타낼 뿐 또 참조되지는 않습니다. 

if(visit[cur])
break;

visit[cur] = 1;

라인 아래에 있기 때문에 정점은 한번만 탐색하기 때문이죠.

현재 코드 내에서는 새로운 pair를 삽입하는 대신 next pair의 값을 바꿔서 삽입하신거고요.

제가 첫 댓글을 요지와는 상관이 없는 쪽으로 달아둔 것 같아서 조금 더 헷갈리셨을 것 같네요.

https://www.acmicpc.net/source/21278815

이 코드 보시면 조금 이해에 도움이 될 수 있지 않을까 싶네요.

@shg9411님 답변 감사드립니다!

드디어 이해했습니다ㅠㅠ 제가 처음부터 개념을 잘못 알고 있었네요ㅠㅠ 선배님께서 써주신 주석을 보고 이해했습니다. 왜 갱신된 비용으로 pair를 만들어야하는지를요ㅠㅠ

늦은 시간까지 정말 감사드립니다! 행복한 하루 되세요!!

다시 한 번 감사드립니다!