×
Crocus
공부한 내용을 정리하는 블로그로 시작한
Crocus는 2014년 1월 14일 부터 시작하여
현재 월 6만명, 총 1,680,662명의 방문자 수를 기록하고 있습니다.
Donation
이제 많은 사용자들이 이용하는 만큼
더 다양한 서비스 개발/제공을 위해 후원금을 모금하고자 합니다.
후원을 해주시는 분들은 Donators 명단에 성명, 후원금을 기입해드리며
Crocus 블로그가 아닌 다른 곳에 정리해둔 저만의 내용을 공유해 드리고자 합니다.
Account
예금주 : 고관우
신한은행 : 110-334-866541
카카오뱅크 : 3333-01-7888060

👉 후원 페이지 바로가기 Donators
익명 : 5000원(Crocus응원합니다.)
busyhuman: 5000원(유용한 지식 감사합니다.)
익명 : 5000원(알고리즘 학습러)
728x90
반응형

파이썬을 이용하여 다익스트라, 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']
반응형
  1. 박강현 2020.11.21 22:04

    안녕하세요! 이제 막 코딩을 공부하기 시작한 문과 대학생입니다. 다익스트라 알고리즘 공부를 위해 방문하였는데, 질문이 생겨서 질문드립니다. 시간복잡성으로 질문드립니다.
    2중 포문으로 다익스트라를 구현하셨는데, 그렇게 될 경우 시간 복잡성은 어떻게 구하고(계산하고), 어떻게 나오는 지 궁금합니다.

    아는게 많지 않아서 블로그 하시는 선생님께 무작정 물어보는 경우가 많습니다ㅜㅜ

    • 가누 2020.11.22 17:18

      해당 코드는 O(N^2) 입니다.
      이중포문에서 현재 위치에서 나와 인접한 노드들을 관찰하는 방식인데 만약 n개의 노드가 모두 n개의 노드와 인접하고있다면
      최악의 경우는 엔제곱이됩니다.

  2. 강민기 2020.11.22 23:34

    안녕하십니까 관련 코딩 공부하고 있는 고등학교 1학년입니다. 위 코드중 다익스트라 부분만(BFS 전까지) 때어와서 init() dijkstra(graph, "A", "F") 이 두 줄 까지 쓴 후 돌려보니 'fianl' 이 정의되지 않았다고 오류가 발생하더라구요... 어디서 문제가 발생하였는지 알려주실 수 있나요? 그래프 변수만 제가 바꾸고 나머지는 위 코드와 동일합니다. 오류는 trace(#경로 추적 로직)에서 2번째 줄, 'current = final'에서 발생했습니다.

    도움을 받을 수 있다면 감사하겠습니다!

    • 가누 2020.11.23 21:42 신고

      음 그냥 댓글만 보면 될거같은데 코드를 봐야할거같아요