[Python] 최적화된 최단 경로 알고리즘 작성하기

 

 

다음은 소스 노드와 그래프의 다른 모든 노드 사이의 최단 경로를 찾기 위해 Dijkstra의 알고리즘을 구현하는 Python 함수입니다.

import heapq

def dijkstra(graph, source):
  # Set up distance dictionary and predecessor dictionary
  distances = {node: float('inf') for node in graph}
  predecessors = {node: None for node in graph}

  # Set the distance to the source node to be 0
  distances[source] = 0

  # Create a priority queue to store the nodes that need to be processed
  queue = []
  heapq.heappush(queue, (0, source))

  # Process nodes in the queue until it is empty
  while queue:
    # Pop the node with the smallest distance from the queue
    distance, node = heapq.heappop(queue)

    # Update the distances and predecessors of the neighbors of the node
    for neighbor, weight in graph[node].items():
      if distance + weight < distances[neighbor]:
        distances[neighbor] = distance + weight
        predecessors[neighbor] = node
        heapq.heappush(queue, (distances[neighbor], neighbor))

  # Return the distances and predecessors dictionaries
  return distances, predecessors

 

 

이 함수는 인접 목록으로 표시되는 그래프와 소스 노드를 가져오고 두 개의 사전을 포함하는 튜플을 반환합니다.

distances: 각 노드를 소스 노드로부터의 거리에 매핑하는 사전
선행자: 소스 노드에서 최단 경로에 있는 선행 노드에 각 노드를 매핑하는 사전입니다.
예를 들어 다음과 같은 그래프가 있는 경우:

 

 

 

graph = {
  'A': {'B': 5, 'C': 1},
  'B': {'A': 5, 'C': 2, 'D': 1},
  'C': {'A': 1, 'B': 2, 'D': 4, 'E': 8},
  'D': {'B': 1, 'C': 4, 'E': 3, 'F': 6},
  'E': {'C': 8, 'D': 3},
  'F': {'D': 6}
}

 

 

 

다음 코드를 사용하여 노드 A에서 다른 모든 노드까지의 최단 경로를 찾을 수 있습니다.

distances, predecessors = dijkstra(graph, 'A')

 

거리 사전에는 다음 키-값 쌍이 포함됩니다.

{
  'A': 0,
  'B': 5,
  'C': 1,
  'D': 6,
  'E': 8,
  'F': 11
}

 

 

선행자 사전에는 다음 키-값 쌍이 포함됩니다.

 

 

{
  'A': None,
  'B': 'A',
  'C': 'A',
  'D': 'B',
  'E': 'C',
  'F': 'D'
}

 

이러한 사전을 사용하여 대상 노드에서 시작하여 선행 노드 체인을 따라 소스로 되돌아가 소스 노드에서 다른 노드로의 최단 경로를 재구성할 수 있습니다.