[알고리즘 공부] 최단 경로

최단 경로 (Shortest Path)

 

 이번 말씀드릴 알고리즘은 '최단 경로'에 대해서 알아보도록 하겠습니다. 최단 경로는 말 그대로 가장 짧은 경로를 찾는 알고리즘입니다. 그리고 위 알고리즘은 다음과 같은 상황에 주로 사용됩니다. 

 

예시

• 한 지점에서 다른 특정 지점가지의 최단 경로를 구해야 하는 경우
• 모든 지점에서 다른 모든 지점까지의 최단 경로를 모두 구해야 하는 경우

 최단 경로 문제는 보통 그래프로 표현하는데 각 지점은 그래프에서 '노드'로 표현되고 지점간 연결된 도로는 그래프에서 '간선'으로 표현됩니다. 또한 실제 코딩 테스트에서 최단 경로를 모두 출력하는 문제보다는 단순히 최단 거리를 출력하도록 요구하는 문제가 많이 출제된다고 알려져 있습니다.

 

 오늘도 참고서인 <이코테>에 따라서 최단 거리 알고리즘의 종류 중 다익스트라 최단 경로와 플로이드 워셜 알고리즘을 다루도록 하겠습니다. 그리고 앞서 알고리즘과 다이나믹 프로그래밍 알고리즘이 최단 경로 알고리즘에 그대로 적용된다는 특징이 있다고 하네요!. 그래서 앞서 배운 그리디 알고리즘 및 다이나믹 프로그래밍 알고리즘의 한 유형이라고 볼 수 있습니다. 다익스트라 알고리즘과 플로이드 워셜 알고리즘에 대한 간단한 설명은 아래와 같습니다.

 

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

• 도로망에서 한 도시에서 다른 모든 도시로 가는 가장 빠른 경로를 찾는 방법과 비슷하다.
• 시작점에서 가장 가까운 점을 찾고 그 점을 거쳐 다른 점으로 가는 경로가 더 짧아지는 지 확인
• 위 과정을 반복하면 시작점에서 모든 다른 점들까지의 최단 경로를 찾을 수 있음
• EX) 지도에서 한 도시에서 다른 모든 도시로 가는 최단 거리를 찾고 싶을 때 사용 가능

 

플로이드 워셜 알고리즘 (Floyd-Warshall Alogrithm)

• 플로이드-워셜 알고리즘은 모든 도시 쌍에 대해 다른 모든 도시를 거쳐 가는 경로를 고려하여 최단 경로를 찾음
• 각 도시를 거쳐 가는 경로를 고려하면서 두 도시 간의 직접 경로와 다른 도시를 거쳐 가는 경로 중 더 짧은 경로를 선택합니다.
• 이 과정을 모든 도시에 대해 반복함으로써 모든 도시 쌍 간의 최단 경로를 찾음.
• EX) 여러 도시 간의 모든 가능한 여행 경로 중 가장 짧은 경로를 찾고 싶을 때 사용할 수 있음.

---

 

다익스트라 알고리즘 예제

 

 

def dijkstra(graph, start):
    # 모든 노드까지의 거리를 무한대로 초기화합니다.
    distances = {vertex: float('infinity') for vertex in graph}
    # 시작 노드까지의 거리는 0입니다.
    distances[start] = 0
    # 방문한 노드를 추적하기 위한 집합입니다.
    visited = set()

    # 아직 방문하지 않은 모든 노드를 방문할 때까지 반복합니다.
    while visited != set(graph.keys()):
        # 방문하지 않은 노드 중에서 가장 가까운 노드를 선택합니다.
        current_vertex = min((vertex for vertex in distances if vertex not in visited), key=lambda vertex: distances[vertex])
        
        # 선택된 노드의 이웃을 순회하며 거리를 업데이트합니다.
        for neighbor, weight in graph[current_vertex].items():
            new_distance = distances[current_vertex] + weight
            if new_distance < distances[neighbor]:
                distances[neighbor] = new_distance
        # 현재 노드를 방문한 것으로 표시합니다.
        visited.add(current_vertex)
    
    # 모든 노드까지의 최단 거리를 반환합니다.
    return distances

# 그래프는 딕셔너리로 표현되며, 간선의 가중치와 함께 저장됩니다.
graph = {
    'A': {'B': 1, 'C': 4},
    'B': {'A': 1, 'C': 2, 'D': 5},
    'C': {'A': 4, 'B': 2, 'D': 1},
    'D': {'B': 5, 'C': 1}
}

print(dijkstra(graph, 'A'))  # 시작점 A에서 다른 모든 점까지의 최단 거리를 출력

---

 

 

플로이드 워셜 알고리즘 예제

 

def floyd_warshall(weights):
    n = len(weights)
    # 최단 거리 정보를 저장할 2차원 리스트를 초기화합니다.
    dist = [[float('infinity') for _ in range(n)] for _ in range(n)]
    
    # 각 노드에서 자기 자신으로의 거리는 0입니다.
    for i in range(n):
        dist[i][i] = 0
    
    # 주어진 가중치를 바탕으로 초기 거리를 설정합니다.
    for i in range(n):
        for j in range(n):
            dist[i][j] = weights[i][j]

    # 각 노드를 거쳐 가는 경우를 고려하여 최단 거리를 갱신합니다.
    for k in range(n):
        for i in range(n):
            for j in range(n):
                dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])
    
    # 모든 노드 쌍 간의 최단 거리를 반환합니다.
    return dist

# 그래프는 2차원 리스트로 표현됩니다. 무한대는 연결되지 않음을 의미합니다.
graph = [
    [0, 1, 4, float('infinity')],
    [1, 0, 2, 5],
    [4, 2, 0, 1],
    [float('infinity'), 5, 1, 0]
]

print(floyd_warshall(graph))  # 모든 노드 쌍 간의 최단 거리를 출력

---

마무리

 이번 글에서는 최단 경로 알고리즘에서 다익스트라와 플로이드워셜 알고리즘에 대해 살펴보았습니다. 뭔가 하루에 하나씩 올리는 것이 쉽지 않고 업로드를 위해서 공부를 하고 있는 것 같은 느낌을 받고 싶습니다. 그래서 기초 부분은 굉장히 중요한 부분이니 최대한 탄탄하게 잡고 넘어갈 수 있도록 스스로를 다그쳐봅니다. 조금 더 제 자신이 꼼꼼해지길 바라면서 오늘의 글은 여기서 마치도록 하겠습니다. 

 

 

참 고

2023.12.08 - [IT/관련 정보] - [코딩 테스트] 이것이 취업을 위한 코딩테스트다 with 파이썬

[코딩 테스트] 이것이 취업을 위한 코딩테스트다 with 파이썬