다익스트라 알고리즘 (Dijkstra's Algorithm)

가중치가 있는 그래프에서 시작 포인트로부터 다른 모든 포인트까지의 최단 경로를 찾는 알고리즘입니다.

알고리즘

1. 초기화
   • 데이터 공간의 모든 포인트를 미탐색 상태로 표시합니다.
   • 시작 포인트의 거리를 0으로, 다른 모든 포인트의 거리를 무한대로 설정합니다.
2. 반복 과정
   • 미방문 포인트들 중에서 최소 거리를 가진 포인트를 선택합니다.
   • 선택된 포인트에서 다른 포인트들까지의 거리를 계산하고, 더 짧은 경로가 발견되면 거리 값을 업데이트합니다.
   • 현재 포인트를 탐색 완료로 표시합니다.
3. 종료 조건
   • 모든 포인트가 탐색될 때까지 반복합니다.

코드로 이해하기

import math
import numpy as np

class Point3D:
    def __init__(self, x, y, z):
        self.x = x
        self.y = y
        self.z = z

# 3D 디스턴스 함수
def distance(p1, p2):
    return math.sqrt((p2.x - p1.x)**2 + 
                     (p2.y - p1.y)**2 + 
                     (p2.z - p1.z)**2)

# 다익스트라 알고리즘
def dijkstra(points, start):
    n = len(points)
    dist = [float('inf')] * n
    prev = [-1] * n
    visited = [False] * n
    
    dist[start] = 0
    
    # 방문하지 않은 포인트 중 최소 거리를 가진 포인트 찾기
    for i in range(n):
        u = -1
        
        min_dist = float('inf')
        for j in range(n):
            if not visited[j] and dist[j] < min_dist:
                min_dist = dist[j]
                u = j
        
        if u == -1:
            break
        
        visited[u] = True
        
        # 인접 포인트 처리
        for v in range(n):
            if u != v:  # 자기 자신이 아닌 경우
                weight = distance(points[u], points[v])
                if not visited[v] and dist[u] + weight < dist[v]:
                    dist[v] = dist[u] + weight
                    prev[v] = u
    
    return prev

A 알고리즘 (A-Star Algorithm)*

A 알고리즘*은 시작 포인트에서 목표 포인트까지의 최단 경로를 찾는 알고리즘으로, 다익스트라 알고리즘에 휴리스틱 함수를 추가하여 탐색 효율성을 높인 방식입니다.

알고리즘