ITPE * JackerLab

개요플로이드-워셜(Floyd-Warshall) 알고리즘은 그래프에서 모든 정점 쌍 간의 최단 경로를 효율적으로 구하는 알고리즘이다. 다익스트라나 벨만-포드와 달리 단일 시작점이 아닌 전체 정점 간의 경로를 계산하며, 동적 계획법(Dynamic Programming) 기반으로 3중 반복문을 통해 구현된다. 네트워크 분석, 지도 서비스, 경로 최적화 등에서 광범위하게 활용된다.1. 개념 및 정의Floyd-Warshall 알고리즘은 가중치가 있는 방향 그래프에서 정점 i에서 j로 가는 최단 거리 d[i][j]를, 중간 정점 k를 거쳐 최적화해 나가는 방식이다. 음수 가중치는 가능하나, 음수 사이클은 허용되지 않는다.2. 알고리즘 동작 원리 단계 설명 1단계거리 행렬 d[i][j]를 초기화 (자기 자신은 0,..

개요경로 탐색 알고리즘(Pathfinding Algorithm)은 시작 지점에서 목표 지점까지 도달하는 최적의 경로를 찾는 알고리즘이다. 이는 그래프 이론을 기반으로 하며, 다양한 조건(최단 거리, 최소 비용, 장애물 회피 등)에 따라 여러 알고리즘이 활용된다. 게임 개발, 내비게이션, 네트워크 라우팅, 인공지능 등 다양한 분야에서 필수적인 요소이며, 최적화된 탐색을 통해 성능과 정확도를 향상시킬 수 있다. 본 글에서는 주요 경로 탐색 알고리즘의 개념, 특징, 시간 복잡도 및 활용 사례를 중심으로 설명한다.1. 개념 및 정의경로 탐색은 그래프의 정점(Vertex)과 간선(Edge) 구조를 바탕으로 출발 노드에서 도착 노드까지 이동 가능한 경로를 찾는 연산이다. 경로의 최단 거리, 최소 비용, 경유지 조건..