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

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

파이썬을 이용하여 다익스트라, 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']