그래프에서 최단 경로를 구하는 벨만-포드(Bellman-Ford) 알고… | [7급 서울시 알고리즘] 26년 1회차 기출문제 상세 페이지

1[7급 서울시 알고리즘] 26년 1회차
그래프에서 최단 경로를 구하는 벨만-포드(Bellman-Ford) 알고리즘에 대한 설명으로 가장 옳지 않은 것은? (단, N은 정점(vertex)의 개수, M은 간선(edge)의 개수이다. 각 정점은 1, 2, …, N으로 번호가 매겨져 있고, 1번이 시작점이다.)
1
1번 정점에서 도달 가능한 음의 가중치를 갖는 사이클이 그래프에 존재하는지 여부를 판단하는 데 사용할 수 있다.
2
총 N-1번의 라운드로 이루어지며, 라운드 K에서는 정점 1부터 정점 K까지의 최단 경로를 구한다.
3
시간 복잡도는 O(NM)이다.
4
사이클이 없는 그래프에서 알고리즘이 수행되는 동안, 모든 정점에 대한 거리 추정치는 실제 최단 경로의 거리와 같거나 이보다 크다.
해설

옳지 않은 설명은 라운드 K에서 정점 1부터 정점 K까지의 최단 경로를 구한다는 것이다.

벨만-포드의 각 라운드는 모든 간선을 한 번씩 완화하며, K번째 라운드가 끝나면 간선을 K개 이하로 쓰는 최단 경로가 모든 정점에 대해 확정된다. 정점 번호와는 관계가 없다.

  • 음의 사이클 판별: N−1 라운드 뒤 한 번 더 완화해 값이 줄어드는 정점이 있으면 시작점에서 도달 가능한 음의 사이클이 있다.
  • 시간 복잡도: N−1 라운드마다 간선 M개를 완화하므로 O(NM)이다.
  • 거리 추정치: 추정치는 실제로 존재하는 경로의 길이로만 갱신되므로 항상 실제 최단 거리 이상이다.

오류나 개정된 내용이 보이면 알려주세요

이어서 풀어보기

[7급 서울시 알고리즘] 26년 1회차 20문항 이어서 보기문제·정답·해설을 한 페이지에서 이어서 볼 수 있어요7급 서울시 알고리즘 기출문제 암기장 전체 보기