다익스트라 java코드 관련 문의

[hjlim4u]

python-for-coding-test/9/2.java

Line 56 in 7c35923

int cost = d[now] + graph.get(now).get(i).getDistance();

int cost = dist + graph.get(now).get(i).getDistance(); 가 더 정확한 표현 아닐까요?

[bombo-dev]

개선된 다익스트라 알고리즘을 사용하신 것 같습니다. node를 꺼내왔다는 건 이미 해당 노드에 대한 처리가 완료되어 우선순위 큐에 담겨있고, 해당 노드에 대한 최소 거리 정보가 distance 테이블에 담긴 것을 알 수 있습니다. 질문자님의 말씀처럼 if(d[now] < dist) continue; 가 있기 때문에 해당 코드로 작성을 하여도 코드 진행 상에는 문제가 없지만 표현적으로 얘기하면 단순히 우선순위 큐에 담겨 있는 노드의 비용과 그 노드에 연결된 비용을 계산 하는 것이냐, 아 이 노드의 최소 거리는 이건데(d[now]) 이 노드의 최소 거리와 해당 노드와 연결된 다른 노드에 연결된 비용을 계산하느냐 입니다. 만약 단순히 해당 노드의 비용만 필요해서 비교를 해야 한다면 if(d[now] < distance) continue; 라는 조건이 필요하지도 않겠지요.