■ 그래프에서 다익스트라 알고리즘(Dijkstra Algorithm)을 사용해 최단 경로를 구하는 방법을 보여준다.
▶ 예제 코드 (PY)
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 |
import heapq import sys def getDijkstraShortestPathDictionary(graphDictionaryDictionary, startNode): distanceDictionary = {node : sys.maxsize for node in graphDictionaryDictionary} distanceDictionary[startNode] = 0 queueList = [] heapq.heappush(queueList, (distanceDictionary[startNode], startNode)) while queueList: currentDistance, node = heapq.heappop(queueList) if distanceDictionary[node] < currentDistance: continue for adjacentNode, distance in graphDictionaryDictionary[node].items(): weightedDistance = currentDistance + distance if weightedDistance < distanceDictionary[adjacentNode]: distanceDictionary[adjacentNode] = weightedDistance heapq.heappush(queueList, (weightedDistance, adjacentNode)) return distanceDictionary graphDictionaryDictionary = { "A" : {"B" : 10, "C" : 3 }, "B" : {"C" : 1, "D" : 2 }, "C" : {"B" : 4, "D" : 8, "E" : 2}, "D" : {"E" : 7 }, "E" : {"D" : 9 } } shortestPathDictionary = getDijkstraShortestPathDictionary(graphDictionaryDictionary, "B") print(shortestPathDictionary) """ {'A': 9223372036854775807, 'B': 0, 'C': 1, 'D': 2, 'E': 3} """ |