CH 07 다익스트라 알고리즘
- 다익스트라 알고리즘 : 구간별 가중치가 있는 그래프에서 전체 가중치의 합이 가장 적은 구간
> 방향성 비순환 그래프(DAG) 또는 가중치가 양의 값인 사이클을 보유할 때만 적용
> 음의 가중치를 가진 그래프의 최단 경로 → 벨만-포드 알고리즘 (매 단계마다 모든 간선을 확인)
- 사이클 : 어떤 쟁점에서 출발해서 한 바퀴 돌아 같은 쟁점에서 끝나는 경로
graph = {}
graph["you"] = ["alice", "bob", "claire"]
# 간선의 가중치
graph["start"] = {}
graph["a"] = {}
graph["b"] = {}
graph["fin"] = {}
graph["start"]["a"] = 6
graph["start"]["b"] = 2
graph["a"]["fin"] = 1
graph["b"]["a"] = 3
graph["b"]["fin"] = 5
#print(graph["start"].keys())
#print(graph["start"].items())
# 정점의 가격
infinity = float("inf") ## 무한대
costs = {}
costs["a"] = 6
costs["b"] = 2
costs["fin"] = infinity ## 가격을 모르는 도착점 정점은 무한대로 설정
# 부모 열
parents = {}
parents["a"] = "start"
parents["b"] = "start"
parents["fin"] = None
# 정점 추적을 위한 배열
processed = []
def find_lowest_cost_node(costs):
lowest_cost = float("inf")
lowest_cost_node = None
for node in costs:
cost = costs[node]
if cost < lowest_cost and node not in processed: # 아직 미처리 정점 중 싼 것이 있으면
lowest_cost = cost # 새로운 최저 정점의 가격으로 설정
lowest_cost_node = node # 새로운 최저 정점으로 설정
return lowest_cost_node
node = find_lowest_cost_node(costs)
while node is not None:
cost = costs[node]
neighbors = graph[node]
for n in neighbors.keys():
new_cost = cost + neighbors[n]
if costs[n] > new_cost: # 해당 정점을 지나는 가격이 더 싸다면
costs[n] = new_cost # 정점의 가격 갱신
parents[n] = node # 부모를 해당 점정으로 갱신
processed.append(node)
node = find_lowest_cost_node(costs) # 다음으로 처리할 정점 찾아 반복
'''
출발점에서 가장 가까운 정점을 찾는다
이웃 정점의 가격을 갱신한다
만약 이웃 정점의 가격을 갱신하면 부모도 갱신한다
해당 정점을 처리한 사실을 기록한다
모든 정점을 처리할 때까지 반복한다
'''
참고자료
Hello Coding 그림으로 개념을 이해하는 알고리즘
