최단 경로 알고리즘

1. 최단 경로 알고리즘이란?

최단 경로 알고리즘(shortest path algorithm)

• 두 노드 사이의 구성 edge weight의 합이 최소가 되는 경로를 찾는 알고리즘
• 그래프의 특성에 따라 사용되는 최단 거리 알고리즘이 다르다.
  • 방향성의 유무
  • 가중치의 유무
  • 음수 가중치의 유무
  • cycle의 유무
• BFS 알고리즘은 unweighted graph에서만 쓸 수 있다.
• Weighted graph에 Dijkstra 알고리즘을 쓸 수 있다.
• Negative weighted graph에 Bellman-Ford 알고리즘을 쓸 수 있다.

2. BFS 최단 경로 알고리즘

BFS predecessor

• 특정 노드에 오기 직전의 노드

Backtraking

1. 현재 노드를 경로에 추가한다.
2. 현재 노드의 predecessor로 이동한다.
3. predecessor가 있다면 1단계로 이동한다.

BFS 최단 경로 알고리즘

1. 모든 노드를 방문하지 않은 노드로 표시한다. (O(n))
2. 시작 노드를 방문 표시 후, 큐에 넣는다.
3. 큐 가장 앞 노드를 꺼낸다.
4. 꺼낸 노드에 인접한 노드(A)에 접근한다.
5. A가 처음 방문한 노드면 방문한 노드 표시를 해준다.
6. A의 predecessor 변수를 큐에서 꺼낸 노드로 설정한다.
7. A를 큐에 넣는다.
8. 꺼낸 노드에 인접한 노드에 전부 접근하기 전까지 4단계로 돌아간다.
9. 큐에 아무 노드가 없을 때까지 3단계로 돌아간다.
10. Backtraking한다.

from collections import deque


class StationNode:
    """지하철 역을 나타내는 노드"""
    def __init__(self, station_name):
        self.station_name = station_name
        self.adjacent_stations = []
        self.visited = False

    def add_connection(self, station):
        """파라미터로 받은 역과 엣지를 만들어주는 메소드"""
        self.adjacent_stations.append(station)
        station.adjacent_stations.append(self)


    def create_station_graph(input_file):
        stations = {}

        # 일반 텍스트 파일을 여는 코드
        with open(input_file) as stations_raw_file:
            for line in stations_raw_file:  # 파일을 한 줄씩 받아온다
                previous_station = None  # 엣지를 저장하기 위한 변수
                raw_data = line.strip().split("-")

                for name in raw_data:
                    station_name = name.strip()

                    if station_name not in stations:
                        current_station = StationNode(station_name)
                        stations[station_name] = current_station

                    else:
                        current_station = stations[station_name]

                    if previous_station is not None:
                        current_station.add_connection(previous_station)

                    previous_station = current_station

        return stations


    def bfs(graph, start_node):
        """최단 경로용 bfs 함수"""
        queue = deque()

        # 모든 노드를 방문하지 않은 노드로 표시, 모든 predecessor는 None으로 초기화
        for station_node in graph.values():
            station_node.visited = False
            station_node.predecessor = None

        # 시작점 노드를 방문 표시한 후 큐에 넣어준다
        start_node.visited = True
        queue.append(start_node)

        while queue:  # 큐에 노드가 있을 때까지
            current_station = queue.popleft()  # 큐의 가장 앞 데이터를 갖고 온다
            for neighbor in current_station.adjacent_stations:  # 인접한 노드를 돌면서
                if not neighbor.visited:  # 방문하지 않은 노드면
                    neighbor.visited = True  # 방문 표시를 하고
                    neighbor.predecessor = current_station  # 이 노드가 어디서 왔는지 표시
                    queue.append(neighbor)  # 큐에 넣는다


    def back_track(destination_node):
        """최단 경로를 찾기 위한 back tracking 함수"""
        res_str = ""  # 리턴할 결과 문자열
        temp = destination_node  # 도착 노드에서 시작 노드까지 찾아가는 데 사용할 변수

        # 시작 노드까지 갈 때까지
        while temp is not None:
            res_str = f"{temp.station_name} {res_str}"  # 결과 문자열에 역 이름을 더하고
            temp = temp.predecessor  # temp를 다음 노드로 바꿔준다

        return res_str


stations = create_station_graph("./new_stations.txt")  # stations.txt 파일로 그래프를 만든다

bfs(stations, stations["을지로3가"])  # 지하철 그래프에서 을지로3가역을 시작 노드로 bfs 실행
print(back_track(stations["강동구청"]))  # 을지로3가에서 강동구청역까지 최단 경로 출력

을지로3가 을지로4가 동대문역사문화공원 신당 상왕십리 왕십리 마장 답십리 장한평 군자 아차산 광나루 천호 강동구청

BFS 최단 경로 알고리즘의 시간 복잡도

• Worst-case time complexity: O(V+E)
• Best-case time complexity: O(V+E)
• Average time complexity: O(V+E)
• Worst-case space complexity: O(V)

3. Dijkstra 알고리즘

Dijkstra 알고리즘 변수들

• Distance: 최단 경로의 현재 추정치
• Predecessor: distance 값을 기준으로 가장 weight가 작은 predecessor를 저장하는 변수
• Complete: 가장 작은 distance를 찾았음을 표시하기 위한 변수

Edge relaxtion

• Distance와 비교하여 source node까지의 최단 경로의 현재 추정치를 노드에 업데이트하여 저장하는 것

Dijkstra 알고리즘

• Source node(s)에서 거리가 가장 작은 정점을 반복적으로 선택하고 인접한 정점의 거리를 업데이트하여 작동하는 최단 경로 알고리즘

1. 모든 노드의 distance를 infinity, predecessor를 None으로, complete를 False로 초기화한다. (O(n))
2. 방문하지 않은 노드 중 s와의 거리가 가장 짧은 노드(v)를 찾는다.
3. v를 방문 표시한다.
4. v의 아직 방문하지 않은 인접 노드 중에 s에서 v까지 경로가 현재 거리보다 짧은 경우 s에서 s의 distance를 업데이트하고, 방문하지 않은 인접 노드들의 predecessor를 v로 설정한다.
5. 방문하지 않은 정점이 있다면 2단계로 돌아간다.
6. 모든 정점에 대한 distance 딕셔너리과 predecessor 딕셔너리를 리턴한다.

import heapq


def dijkstra(graph, start):
    # Initialize distance and predecessor dictionaries
    dist = {vertex: float('inf') for vertex in graph}
    dist[start] = 0
    predecessor = {vertex: None for vertex in graph}

    # Create a priority queue and add the start vertex with distance 0
    pq = [(0, start)]

    # Loop until the priority queue is empty
    while pq:
        # Pop the vertex with the smallest distance from the priority queue
        current_dist, current_vertex = heapq.heappop(pq)

        # If the distance to the current vertex is already smaller than the
        # stored distance, skip the current iteration
        if current_dist > dist[current_vertex]:
            continue

        # Loop through the neighbors of the current vertex
        for neighbor, weight in graph[current_vertex].items():
            # Calculate the distance to the neighbor through the current vertex
            new_dist = dist[current_vertex] + weight

            # If the new distance is shorter than the stored distance, update the
            # distance and predecessor dictionaries and add the neighbor to the
            # priority queue with the new distance
            if new_dist < dist[neighbor]:
                dist[neighbor] = new_dist
                predecessor[neighbor] = current_vertex
                heapq.heappush(pq, (new_dist, neighbor))

    return dist, predecessor


my_graph = {
    'A': {'B': 2, 'C': 3},
    'B': {'A': 2, 'C': 1},
    'C': {'A': 3, 'B': 1, 'D': 4, 'E': 5},
    'D': {'C': 4, 'E': 1},
    'E': {'C': 5, 'D': 1}
}

distance, predecessor = dijkstra(my_graph, 'B')

print(f"distances: {distance}")
print(f"predecessors: {predecessor}")

distances: {'A': 2, 'B': 0, 'C': 1, 'D': 5, 'E': 6}
predecessors: {'A': 'B', 'B': None, 'C': 'B', 'D': 'C', 'E': 'C'}

Feedback

1. 최단 경로 알고리즘의 시간, 공간 복잡도를 분석해보자.
2. BFS 최단 경로 알고리즘에서 최단 경로가 여러 개일 경우를 분석해보자.
3. 다양한 언어들로 BFS, Dijkstra 등의 알고리즘으로 최단 거리 알고리즘을 구현해보자.
4. Dijkstra 알고리즘을 수학적으로 분석해보자.
5. Bellman-Ford 알고리즘에 대해 알아보자.

참고 자료

• Shortest path problem - Wikipedia
• 그래프 - 알고리즘 · 자료구조 강의 | 코드잇