Dijkstra Algorithm (Google map 에서도 사용하는 경로 찾기)

Dijkstra Algorithm은 지도에서 가장 빠른 패스를 찾아주는 것 처럼 네트워크에서 두 지점간 가장 짧은 루트를 찾는데 쓰이는 알고리즘이다. 아래와 같은 분야에서 응용될 수 있다.

• GPS navigation systems finding the fastest route (가장 빠른 루트를 찾는 GPS 네비게이션)
• Routing data packets in computer networks (컴퓨터 네트워크에 있어서 데이터 패킷의 라우팅)
• Delivery services optimizing routes for efficiency (배달 서비스의 효율적인 루트 최적화)
• Social networks (suggesting connections) (쇼셜네트워크에 있어서 커넥션 제안)
• Finance (finding optimal investment paths) (금융에 있어서 최적화 투자 패스)
• Project management (finding the most efficient workflow) (프로젝트 관리에 있어서 가장 효율적인 워크플로 찾기)

그래프의 종류와 용어

 

B -> F 에의 최단 루트 찾기

(1) 출발 B의 노드는 0 로 초기화 나머지는 무한(∞)값 초기화 (2) B의 이웃 노드들(A, B, E)을 찾아서 거리값으로 노드들의 값을 설정 (3) (1) 로 돌아가는데 이번에는 가장 작은 거리의 노드(E)를 선택

 

Python 으로 구현

 

각 노드별 이웃 노드들을 dict 로 구성

graph = {    "A": {"B": 3, "C": 3},    "B": {"A": 3, "D": 3.5, "E": 2.8},    "C": {"A": 3, "E": 2.8, "F": 3.5},    "D": {"B": 3.5, "E": 3.1, "G": 10},    "E": {"B": 2.8, "C": 2.8, "D": 3.1, "G": 7},    "F": {"G": 2.5, "C": 3.5},    "G": {"F": 2.5, "E": 7, "D": 10}, }

 

그래프 저장, 구성할 클래스

from heapq import heapify, heappop, heappush class Graph:   def __init__(self, graph: dict = {}):       self.graph = graph  # dictionary   # 예) node1='A', node='B', weight=3   def add_edge(self, node1, node2, weight):       if node1 not in self.graph:  # 현 노드의 이름           self.graph[node1] = {}  # 존재하지 않으면 빈 dict 를 생성       self.graph[node1][node2] = weight  # 현 노드 . 이웃 노드의 거리(weight)등록   def shortest_distances(self, source: str):     # 각 노드(node1) 값을 inf 로 초기화 -> {'A': inf , 'B': inf , 'C': inf , 'D': inf , 'E': inf , 'F': inf , 'G': inf }     distances = {node: float("inf") for node in self.graph}     # 출발 노드를 0 으로 초기화     distances[source] = 0       # 초기값으로 (거리0, source) 를 tuple 리스트를 힙 queue 화     pq = [(0, source)]     heapify(pq)     # 방문한 노드를 저장     visited = set()     while pq:  # While the priority queue isn't empty       current_distance, current_node = heappop(pq)       if current_node in visited:           continue       visited.add(current_node)       for neighbor, weight in self.graph[current_node].items():           # Calculate the distance from current_node to the neighbor           tentative_distance = current_distance + weight           if tentative_distance < distances[neighbor]:               distances[neighbor] = tentative_distance               heappush(pq, (tentative_distance, neighbor))       predecessors = {node: None for node in self.graph}     # 시작 노드('B') 로부터의 각 노드의 가장 짧은 거리 dict     # distances =  {'A': 3, 'B': 0, 'C': 5.6, 'D': 3.5, 'E': 2.8, 'F': 9.1, 'G': 9.8}     for node, distance in distances.items():         # 현 노드의  (이웃 노드, 거리) 를 반복         for neighbor, weight in self.graph[node].items():             # 이웃 노드의 시작 노드(B) 로부터의 거리 합 = 현 노드의 합 + 거리 라면 다음 이동 할 노드OK             if distances[neighbor] == distance + weight:                 # 현 노드의 다음 이동 노드 등록                 predecessors[neighbor] = node     # predecessors = {'A': 'B', 'B': None, 'C': 'E', 'D': 'B', 'E': 'B', 'F': 'C', 'G': 'E'}     return distances, predecessors   def shortest_path(self, source: str, target: str):       # 출발노드(source) 기준의 각 노드와 다음 이동 노드의 dict       _, predecessors = self.shortest_distances(source)       path = []       current_node = target         # 노드이동 경로는 목적지(target)부터 시작       while current_node:           path.append(current_node)           current_node = predecessors[current_node]       # Reverse the path and return it       path.reverse()       return path

 

predecessors

현 노드에서 이동 할 전의 노드를 결정. 예를 들면, 현 노드가 F라고 하면 다음 노드의 후보는 C, G 가 된다.

F 의 값은 (이전 노드 값 + 거리) 가 되므로 9.1 = ( x + y ) 가 되기 위한 조건은 C 가 해당된다. 

G 는 (9.1 < 9.8 + 2.5) 이므로 탈락되게 된다.

 

"B"  에서 "F"에의 최단 경로 탐색 

G = Graph(graph) G.shortest_path("B", "F") # ['B', 'E', 'C', 'F']