거리표가 주어진 지도에서 최소 비용 경로 찾기

나에게 맞는 깊이로 시작하기

준비 순서

1. 가상 장소 A~F와 양방향 연결선 9개를 만들고 연결선마다 양수 거리 단위를 붙입니다. 실제 학교 출입구·버스 노선·개인의 이동 데이터는 사용하지 않으며, 그래프가 가상이라고 표시합니다.
2. 출발점에서 목적지까지 가능한 단순 경로를 적고 각 간선 가중치를 합산합니다. 간선이 적은 경로와 거리 합이 작은 경로를 따로 표시해 두 기준의 차이를 확인합니다.
3. 고등 선택에서는 출발점 거리 0, 나머지는 무한대라고 놓고 가장 작은 임시 거리의 정점을 확정합니다. 이웃의 거리를 현재값과 새 경로값 중 작은 것으로 갱신하고, 표를 반복해 목적지의 최솟값과 경로를 복원합니다. 계산에서 음수 간선이 없다는 전제를 확인합니다.

완성도를 높이는 기준

학교의 공식 채점표가 아닌, 이 탐구를 스스로 점검하는 기준입니다.

함께 쓸 보조 자료

• 가상 그래프: 정점 / 간선 / 양수 비용 / 단위
• 경로 비교표: 경로 순서 / 간선 비용 합 / 이동 횟수 / 선택 기준

아래 활동지에는 주제별 기록표와 탐구 보고서의 기본 구성 칸을 함께 담았습니다.

이 순서로 읽으면 도움이 됩니다

1. 1. 추천 기준이 바뀌면 같은 입력도 다른 결과가 나올까?

   정점·간선과 규칙을 표로 나타내어 단계별 계산을 기록한다.

2. 2. 추천 기준이 바뀌면 같은 입력도 다른 결과가 나올까?

   그래프 경로 계산을 입력·규칙·출력의 알고리즘으로 정리한다.

자료를 더 찾을 곳

• Cornell University CS 2110 · Shortest Paths ↗

  lecture section “Weighted Graphs,” definition of non-negative edge weights and shortest path — 가중 그래프의 최단 경로는 간선 가중치 합을 최소화하는 경로이며 해당 다익스트라 설명은 비음수 가중치를 전제한다.

위 링크는 자료를 탐색하는 출발점입니다. 제출물에는 실제로 읽은 개별 자료의 제목·작성자·발행일·주소·확인한 위치를 적어 주세요.

질문을 한 걸음 더 넓히면

가상 그래프에 지름길 간선을 하나 추가하고 최단 경로가 바뀌는 조건과 새 경로 비용을 계산한다.

제출 전에 스스로 점검하기

• □ 간선 가중치를 합산하고 비용 단위를 일관되게 썼나요?
• □ 최소 거리와 실제 이동 시간·접근성·안전을 혼동하지 않았나요?
• □ 학교의 안내문에 나온 분량·형식·평가 기준·AI 사용 조건을 확인했나요?
• □ 도움을 받은 부분과 내가 조사·해석·수정한 과정을 구별했나요?