파이썬을 이용하여 다익스트라, BFS, Greedy를 이용하여 최단 경로가 어떻게 되는지 간단히 코딩해보았다.
init을 통해 간선 정보 및 노드 최단 경로, 경로 추적을 초기화 해주고
다익스트라(우선순위 큐가 아닌 2중 포문을 이용한 코드)
BFS(우선순위 큐가 아닌 큐를 이용한 코드)
Greedy(재귀를 이용한 코드)
를 통해 각각 결과가 어떻게 나오는지 관찰해본다.
이때 탐욕에서는 결과가 50이 나오는데 이는
A에서 출발할때 가장 가까운 C로 가고 C에서는 가장 가까운 D로 가고 D에서는 가장 가까운 F로 가기 때문에
실제 정답은 35이지만 탐욕을 이용하면 50이 나오게 되는 탐욕 알고리즘의 한계를 보여주는 결과물을 볼 수 있다.
import queue
graph = {}
infinity = float("inf")
costs = {}
parents = {}
processed = []
# 초기화
def init():
global graph, infinity, costs, parents, processed
graph = {} # 간선 정보 입력
graph["A"] = {}
graph["A"]["B"] = 5
graph["A"]["C"] = 0
graph["B"] = {}
graph["B"]["D"] = 15
graph["B"]["E"] = 20
graph["C"] = {}
graph["C"]["D"] = 30
graph["C"]["E"] = 35
graph["D"] = {}
graph["D"]["F"] = 20
graph["E"] = {}
graph["E"]["F"] = 10
graph["F"] = {}
# ----------------------------------------
infinity = float("inf")
# ------------------------------------------
costs = {} # 해당 노드 최단경로 입력
costs["A"] = infinity
costs["B"] = infinity
costs["C"] = infinity
costs["D"] = infinity
costs["E"] = infinity
costs["F"] = infinity
# -------------------------------------------
parents = {} # 추적 경로를 위해 부모 설정
parents["B"] = None
parents["C"] = None
parents["D"] = None
parents["E"] = None
parents["F"] = 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
# 다익스트라 알고리즘
def dijkstra(graph, start, final):
node = start
costs[start] = 0
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: # 현재 가지고있는 cost보다 new_cost가 더 최단거리라면
costs[n] = new_cost # 갱신
parents[n] = node
processed.append(node)
node = find_lowest_cost_node(costs)
# 경로 추적 로직
trace = []
current = final
while current != start:
trace.append(current)
current = parents[current]
trace.append(start)
trace.reverse()
print("=== Dijkstra ===")
print(start, "에서 ", final, "까지의 정보")
print("최단 거리 : ", costs[final])
print("진행 과정 : ", processed)
print("경로 : ", trace)
# BFS
def bfs(graph, start, final):
q = queue.Queue()
costs[start] = 0
q.put({"cur": start, "cost": costs[start]})
while True:
if q.empty():
break
val = q.get()
cur = val["cur"]
cost = val["cost"]
costs[cur] = cost
for next in graph[cur]:
nextCost = graph[cur][next] + cost
# next의 cost가 nextCost보다 크다면 갱신해준다.(더 최단거리로)
if costs[next] >= nextCost:
costs[next] = nextCost
parents[next] = cur
q.put({"cur": next, "cost": nextCost})
# 추적 경로
trace = []
current = final
while current != start:
trace.append(current)
current = parents[current]
trace.append(start)
trace.reverse()
print("=== BFS ===")
print(start, "에서 ", final, "까지의 정보")
print("최단 거리 : ", costs[final])
print("경로 : ", trace)
# 탐욕
def greedy(graph, start, final):
if start == final: # 도착했다면
trace = []
current = final
while current != greedy_start:
trace.append(current)
current = parents[current]
trace.append(greedy_start)
trace.reverse()
#결과 출력
print("=== Greedy ===")
print(greedy_start, "에서 ", final, "까지의 정보")
print("최단 거리 : ", costs[final])
print("경로 : ", trace)
return
cur = start
# 현재 노드에서 가장 가까운 노드로 이동(minNode)
minNode = -1
minCost = infinity
for next in graph[cur]:
nextCost = graph[cur][next] + costs[cur]
if minCost > nextCost:
minNode = next
minCost = nextCost
if minNode == -1:
return
costs[minNode] = minCost
parents[minNode] = cur
# 그다음 노드로 진입
greedy(graph, minNode, final)
init()
dijkstra(graph, "A", "F")
init()
bfs(graph, "A", "F")
init()
greedy_start = "A"
costs[greedy_start] = 0
greedy(graph, "A", "F")
=== Dijkstra ===
A 에서 F 까지의 정보
최단 거리 : 35
진행 과정 : ['A', 'C', 'B', 'D', 'E', 'F']
경로 : ['A', 'B', 'E', 'F']
=== BFS ===
A 에서 F 까지의 정보
최단 거리 : 35
경로 : ['A', 'B', 'E', 'F']
=== Greedy ===
A 에서 F 까지의 정보
최단 거리 : 50
경로 : ['A', 'C', 'D', 'F']
'Basic > Python' 카테고리의 다른 글
Python 간단한 진법 변환기 (0) | 2020.10.14 |
---|---|
python priority queue 사용 방법 (heap queue) (0) | 2020.10.11 |
Python 다익스트라, BFS, Greedy를 이용한 최단 경로 (4) | 2020.09.08 |
pygame으로 벽돌깨기 만들기 (0) | 2020.09.01 |
파이썬 파일 입출력을 통한 구구단 만들기 (0) | 2020.08.11 |
Python tuple 여러 사용 방법 (0) | 2020.07.07 |
-
박강현 2020.11.21 22:04
안녕하세요! 이제 막 코딩을 공부하기 시작한 문과 대학생입니다. 다익스트라 알고리즘 공부를 위해 방문하였는데, 질문이 생겨서 질문드립니다. 시간복잡성으로 질문드립니다.
2중 포문으로 다익스트라를 구현하셨는데, 그렇게 될 경우 시간 복잡성은 어떻게 구하고(계산하고), 어떻게 나오는 지 궁금합니다.
아는게 많지 않아서 블로그 하시는 선생님께 무작정 물어보는 경우가 많습니다ㅜㅜ
-
강민기 2020.11.22 23:34
안녕하십니까 관련 코딩 공부하고 있는 고등학교 1학년입니다. 위 코드중 다익스트라 부분만(BFS 전까지) 때어와서 init() dijkstra(graph, "A", "F") 이 두 줄 까지 쓴 후 돌려보니 'fianl' 이 정의되지 않았다고 오류가 발생하더라구요... 어디서 문제가 발생하였는지 알려주실 수 있나요? 그래프 변수만 제가 바꾸고 나머지는 위 코드와 동일합니다. 오류는 trace(#경로 추적 로직)에서 2번째 줄, 'current = final'에서 발생했습니다.
도움을 받을 수 있다면 감사하겠습니다!