최단경로 알고리즘
정보관리기술사 제123회 4교시 31번 문항으로, 과목은 SW공학/프로젝트관리입니다. ‘시간 복잡도’ 키워드는 정보관리기술사 기출 4문항에 나왔습니다.
원문 문제
정보관리기술사 제123회 31번. 최단경로 알고리즘
- 가. 최단경로 알고리즘의 유형 4가지
- 나. 다음 그래프(A, B, C, D, E 5개 노드로 구성된 그래프, A가 출발지, E가 목적지)에서 4가지 알고리즘 계산방법
- 다. "나"의 4가지 알고리즘 계산결과 비교
핵심 키워드
- 최단경로 알고리즘
- 다익스트라
- 벨만-포드
- 플로이드-워셜
- 그래프 탐색
- 경로 최적화
- 시간 복잡도
고득점 가이드 — 1. 개요
최단경로 알고리즘은 그래프상 두 정점 간 가중치 합이 최소인 경로를 탐색하는 그래프 이론 핵심 기법이다. 물류 배송·통신망 라우팅·게임 AI 경로 탐색 등 다양한 도메인에서 활용되며, 그래프 특성 (단일·전체 출발지, 음수 가중치 허용 여부) 에 따라 적합한 알고리즘이 달라진다. 본 답안에서는 대표 알고리즘 4 가지의 유형, 주어진 5 거점 그래프의 계산 절차, 결과 비교를 차례로 다룬다.
출제 이력
- 최단경로 알고리즘기출 1문항
- 다익스트라기출 1문항
- 벨만-포드기출 1문항
- 플로이드-워셜기출 1문항
- 그래프 탐색기출 1문항
- 경로 최적화기출 1문항
- 시간 복잡도기출 4문항