최단경로2 알고리즘 - 최단경로, 그래프 알고리즘 최단경로 (다익스트라, 벨만포드, BFS)그래프에서 한 점에서 다른 점으로 가는 가장 빠른 길을 찾는 문제가 최단 경로(Shortest Path)이다. 네비게이션의 길찾기, 라우터의 패킷 전달, 비행기 노선 설계, SNS의 친구 추천, 게임 캐릭터의 이동 AI까지 — 그래프 위에서 동작하는 거의 모든 응용의 토대가 최단 경로 알고리즘이다. 가중치의 유무·음수 가중치 허용 여부·시작점이 하나인지 모두인지에 따라 적합한 알고리즘이 갈리며, 그 선택의 정확성이 시스템의 응답 시간을 직접 결정한다. 본 글은 BFS·다익스트라·벨만-포드·플로이드-워셜 네 가지 핵심 최단 경로 알고리즘의 차이와 사용 조건을 세심하게 정리한다(출처: CLRS — Introduction to Algorithms, 22~25장). 제가.. 2026. 5. 19. 자료구조 - 그래프 탐색 그래프 (BFS, DFS, 인접리스트)트리는 그래프의 특수한 형태(사이클 없음 + 단일 부모)였다면, 그래프는 그 제약을 모두 풀어 노드들이 임의의 방식으로 연결될 수 있는 가장 일반적인 자료구조이다. 도로망·SNS 인맥·웹 페이지의 하이퍼링크·전력망·항공 노선·통신 토폴로지·게임 맵까지, 현실 세계의 거의 모든 네트워크가 그래프로 모델링된다. 그래프 위에서 동작하는 탐색 알고리즘 BFS·DFS는 이후 등장하는 거의 모든 그래프 알고리즘(최단 경로·최소 신장 트리·위상 정렬 등)의 토대가 되며, 그 위에서 다익스트라·크루스칼·프림 같은 고급 알고리즘이 얹어진다. 본 글은 그래프의 정의·표현 방법·탐색 알고리즘을 세심하게 정리한다(출처: 위키백과 — Graph (abstract data type)). 제가.. 2026. 5. 16. 이전 1 다음