🙄 최단 경로 알고리즘
➡ 최단 경로 알고리즘이란?
- 최단 경로를 구하는 구체적인 방법들
- 그래프의 특성에 따라 사용되는 알고리즘이 다름
- 무가중치에서 쓰이는
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()
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 = ""
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")
bfs(stations, stations["을지로3가"])
print(back_track(stations["강동구청"]))
🙄 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
하지 않은 노드를 돌면서:
- 현재 노드를
complete
처리한다