TIL_42 : 최단 경로 알고리즘

🙄 최단 경로 알고리즘

➡ 최단 경로 알고리즘이란?

• 최단 경로를 구하는 구체적인 방법들
• 그래프의 특성에 따라 사용되는 알고리즘이 다름
• 무가중치에서 쓰이는 BFS 가중치에서 쓰이는 Dijkstra 를 알아보자

🙄 BFS 알고리즘

➡ BFS predecessor

• BFS 알고리즘에서 추가로 predecessor라는 변수 추가
• BFS를 할 때 특정 노드에 오기 직전의 노드를 저장해 줌

➡ 최단 경로용 BFS

최단 경로용 BFS

• 시작 노드를 방문 표시 후, 큐에 넣음
• 큐에 아무 노드가 없을 때까지:
  • 큐 가장 앞 노드를 꺼낸다
  • 꺼낸 노드에 인접한 노드들을 모두 보면서:
    • 처음 방문한 노드면:
      • 방문한 노드 표시를 해준다
      • predecessor 변수를 큐에서 꺼낸 노드로 설정
      • 큐에 넣어준다

Backtracking

• 현재 노드를 경로에 추가한다
• 현재 노드의 predecessor로 간다
• predecessor가 없을 때까지 위 단계들 반복

class StationNode:
    """지하철 역을 나타내는 역"""
    def __init__(self, station_name):
        self.station_name = station_name
        self.adjacent_stations = []
        self.visited = False
        self.predecessor = None
        
        
from collections import deque
from subway_graph import *

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      # predecessor 변수를 큐에서 꺼낸 노드로 설정
                queue.append(neighbor)  	  	    # 큐에 넣는다


def back_track(destination_node):
    """최단 경로를 찾기 위한 back tracking 함수"""
    res_str = ""  

    while destination_node is not None:
        res_str = "{} {}".format(destination_node.station_name, res_str) 
        destination_node = destination_node.predecessor
    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가 동대문역사문화공원 신당 상왕십리 왕십리 마장 답십리 장한평 군자 아차산 광나루 천호 강동구청 

🙄 Dijkstra 알고리즘

➡ 그래프 노드 3가지 변수

• 그래프 노드에 3가지 변수를 저장해야 함
  1. distance : 특정 노드까지의 최단 거리 예상치
  2. predecessor : 현재까지 최단 경로에서 바로 직전의 노드
  3. complete : 노드까지의 최단 경로를 찾았다고 표시하기 위한 변수

➡ 엣지 Relaxation

• 노드들을 방문하면서 해당 노드의 distance, predecessor 변수들을 업데이트 해주는 것
  ex) A에서 B를 방문할 때, B의 변수를 업데이트 해주는 것을 엣지 (A, B)를 relax한다라고 표현

➡ Dijkstra 알고리즘

• 시작점의 distance를 0으로, predecessor를 None으로
• 모든 노드가 complete일 때까지:
  • complete하지 않은 노드 중 distance가 가장 작은 노드 선택
  • 이 노드에 인접한 노드 중 complete하지 않은 노드를 돌면서:
    • 각 엣지를 relax한다
  • 현재 노드를 complete 처리한다