Python 다익스트라, BFS, Greedy를 이용한 최단 경로

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