본문 바로가기

알고리즘 이론/다익스트라 알고리즘1

다익스트라 알고리즘(dijkstra algorithm) * 최단 경로 구하기 알고리즘의 하나 - 다익스트라 알고리즘은, 특정한 노드에서 출발해 마지막 노드에 도착하는 것까지의 경로를 구하는 것과 관련 있다. - 관련 문제: 백준 10282번 - 해킹 (www.acmicpc.net/problem/10282) 백준 5719번 - 거의 최단 경로(www.acmicpc.net/problem/5719) import heapq mygraph = { 'A':{'B':8, 'C':1, 'D':2}, 'B':{}, 'C':{'B':5, 'D':2}, 'D':{'E':3, 'F':5}, 'E':{'F':1}, 'F':{'A':5} } def dijkstra(graph, start): # 초기화 distances = { node:float('inf') for node in gr.. 2020. 10. 10.

티스토리툴바