[algorithms] ch4. Paths in graphs (Dijkstra's algorithm, priority queue, heap)

(23.03.17)

algorithms  S. Dasgupta, C. H. Papadimitriou, and U. V. Vazirani (2008) 책 읽고 정리하기

http://algorithmics.lsi.upc.edu/docs/Dasgupta-Papadimitriou-Vazirani.pdf

 

 

정리한 내용

4.4 Dijkstra's algorithm

4.5 Prority queue implementations

---

Dijkstra's algorithm은 BFS를 좀더 일반적인 graph로 가져온 것인데,

BFS와는 다르게 edge의 length가 positive integers로 구성되어있다. 

 

 

 

 

Dijkstra's algorithm 수행 예제

 

priority queue - 우선순위 큐

heap - heap

 

dijkstra's algorithm python code

#dijkstra's algorithm
#pritority queue -> heap
import heapq

def dijkstra(graph, start_node):
    distances = {node: float('inf') for node in graph}
    queue = []
    distances[start_node] = 0 #start_node's distance = 0
    heapq.heappush(queue, [start_node, distances[start_node]])
    print(f'queue: {queue}')

    while queue:
        node, distance = heapq.heappop(queue)

        if distance > distances[node]:
            continue

        for new_node, new_distance in graph[node].items():
            d = distance + new_distance
            if d < distances[new_node]:
                distances[new_node] = d
                print(f'distances: {distances}')
                heapq.heappush(queue, [new_node, d])
                print(f'queue: {queue}')

    return distances



if __name__ == '__main__':
    #dijkstra - input: graph, output: shortest length for each node

    # graph = dict()
    graph = {
        'A': {'B': 8, 'C': 1, 'D': 2},
        'B': {},
        'C': {'B': 5, 'D': 2},
        'D': {'E': 3, 'F': 5},
        'E': {'F': 1},
        'F': {'A': 5}
    }

    print(f"bfs {dijkstra(graph, 'A')}")

 

https://github.com/gompaang/algorithm_python

GitHub - gompaang/algorithm_python