catbirdseat   3년 전

해당 문제에서 요구하는 출력은 "최단 경로"의 경로값이 아닌 "최소 경로값" 입니다.

예를 들어, 1에서 2까지 경로값이 100, 1에서 3까지 경로값이 1, 3에서 2까지 경로값이 2일 경우

1에서 2까지 가는 최단 경로는 1->2 이고 이 경우 경로값은 100이 돼야 합니다.

그러나 문제에서 요구하는 바는 최소 경로값 즉, 1->3->2 이며 이렇게 되면 답은 4입니다.

수정 부탁드립니다!

djm03178   3년 전

간선의 가중치가 곧 거리를 나타내는 것이니 최단 경로라고 해도 문제될 것이 없습니다.

catbirdseat   3년 전

답변 감사드립니다.

제가 애를 먹었던 이유를 설명드리자면

제가 아직 많은 문제를 풀어보진 않았지만, 가중치 그래프 문제에서 가중치에 비용, 거리, 시간 등 거리 외의 값이 들어가는 경우를 적지 않게 봤습니다.

저희가 부산까지 갈때 비용이 적게 드는 경로와, 최단 경로는 다르듯 추가적인 설명이 있어야 할 것 같습니다.

제가 아직 "가중치"의 개념이 익숙하지 않아 실례를 범했다면 사과드리겠습니다.

ryute   3년 전

https://en.wikipedia.org/wiki/...를 참고하면,

In graph theory, the shortest path problem is the problem of finding a path between two vertices (or nodes) in a graph such that the sum of the weights of its constituent edges is minimized.

정의가 처음부터 가중치 합을 최소로 하는 경로를 찾는 문제입니다. 원래 문제가 올바른 정의가 맞습니다.

catbirdseat   3년 전

아하! 제가 부족하게 알고 있었네요

알려주셔서 감사합니다!

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