[알고리즘] 벨만-포드 알고리즘 vs 존슨 알고리즘

그래프에서 한 정점에서 다른 모든 정점으로의 최단 경로를 구하는 방법은 여러 가지가 있습니다. 그 중에서도 벨만포드 알고리즘과 존슨 알고리즘은 음의 간선이 포함된 그래프에서 최단 경로를 찾는 데 효과적인 두 가지 알고리즘입니다.

 

벨만-포드 알고리즘

벨만포드 알고리즘은 그래프의 모든 간선을 반복적으로 순회하면서, 해당 간선을 거쳐가는 경로의 거리가 현재까지 알려진 최단 거리보다 짧다면 최단 거리를 갱신하는 방식으로 최단 경로를 구합니다.

def bellman_ford(graph, start):
  """
  그래프에서 한 정점에서 다른 모든 정점으로의 최단 경로를 구하는 알고리즘

  Args:
    graph: 그래프
    start: 출발 정점

  Returns:
    각 정점까지의 최단 경로
  """

  dist = [float("inf") for _ in range(len(graph))]
  dist[start] = 0

  for _ in range(len(graph)):
    for u, v, w in graph:
      if dist[u] + w < dist[v]:
        dist[v] = dist[u] + w

  return dist

벨만포드 알고리즘의 시간 복잡도는 **O(VE)**이며, 여기서 V는 정점의 개수, E는 간선의 개수입니다.

 

존슨 알고리즘

존슨 알고리즘은 벨만포드 알고리즘과 다익스트라 알고리즘을 결합한 혼합 알고리즘입니다. 존슨 알고리즘은 먼저 그래프의 모든 간선 가중치를 음수로 변환한 다음, 벨만포드 알고리즘을 사용하여 최단 경로를 찾습니다. 마지막으로, 최단 경로의 가중치를 양수로 되돌리기 위해 간선 가중치를 다시 변경합니다.

def johnson(graph, start):
  """
  그래프에서 한 정점에서 다른 모든 정점으로의 최단 경로를 구하는 알고리즘

  Args:
    graph: 그래프
    start: 출발 정점

  Returns:
    각 정점까지의 최단 경로
  """

  # 그래프의 모든 간선 가중치를 음수로 변환
  for u, v, w in graph:
    graph[u][v] = -w

  # 벨만포드 알고리즘을 사용하여 최단 경로를 구함
  dist = bellman_ford(graph, start)

  # 최단 경로의 가중치를 양수로 되돌림
  for u, v, w in graph:
    graph[u][v] = -dist[v]

  # 다익스트라 알고리즘을 사용하여 최단 경로를 구함
  for v in range(len(graph)):
    if v != start:
      dist[v] = float("inf")
    dijkstra(graph, start, v)

  return dist

존슨 알고리즘의 시간 복잡도는 **O(V^2 + VE)**입니다.

 

 

두 알고리즘 비교

항목	벨만-포드 알고리즘	존슨 알고리즘
음의 간선 허용 여부	가능	가능
시간 복잡도	O(VE)	O(V^2+VE)
장점	음의 간선 허용, 최단 경로의 개수가 1개가 아닌 경우	음의 간선 허용, 다익스트라 알고리즘에 비해 시간 복잡도가 빠름
단점	시간 복잡도가 느림	그래프의 모든 간선 가중치를 변환하고 다시 되돌려야 함

 

사용 시 고려사항

음의 간선이 포함된 그래프에서 최단 경로를 구해야 하는 경우, 존슨 알고리즘이 적합합니다. 음의 간선이 존재할 때 다익스트라 알고리즘은 사용할 수 없으므로, 존슨 알고리즘을 활용하여 최단 경로를 찾을 수 있습니다. 알고리즘 선택은 그래프의 특성과 문제의 요구사항에 따라 결정되어야 합니다.

 

 

이상으로 벨만포드 알고리즘과 존슨 알고리즘에 대한 간단한 비교를 살펴보았습니다. 각 알고리즘은 그래프에서 최단 경로를 찾는 데 유용하며, 음의 간선이 있는 경우에도 적용할 수 있습니다. 그러나 알고리즘을 선택할 때는 그래프의 크기와 특성, 문제의 요구사항에 따라 고려해야 할 사항이 있습니다.

벨만포드 알고리즘은 음의 간선을 허용하며 최단 경로의 개수가 1개가 아닌 경우에 유용합니다. 그러나 그래프가 크면 실행 시간이 길어질 수 있습니다.

반면에 존슨 알고리즘은 음의 간선을 허용하면서도 다익스트라 알고리즘에 비해 빠른 속도를 제공합니다. 하지만 그래프의 모든 간선 가중치를 변경하고 되돌려야 하는 번거로움이 있습니다.

따라서 최적의 선택을 하려면 문제의 특성과 그래프의 크기를 고려하여 적절한 알고리즘을 선택하는 것이 중요합니다. 각각의 상황에 맞게 알고리즘을 활용하여 최단 경로 문제를 해결하시길 바랍니다.