Статьи

Алгоритм недели: алгоритм Беллмана-Форда в Python

Ноябрь 8, 2018

Последняя проблема класса Algorithms 2 потребовала от нас написания алгоритма для вычисления кратчайшего пути между двумя узлами на графике и одним алгоритмом, который позволяет нам сделать это — Беллман-Форд .

Беллман-Форд вычисляет кратчайший путь из одного источника, что означает, что если у нас есть 5-вершинный граф, нам нужно будет запустить его 5 раз, чтобы найти кратчайший путь для каждой вершины, а затем найти кратчайшие пути из этих кратчайших путей.

Отличительной особенностью Bellman-Ford по сравнению с Djikstra является то, что он способен справляться с отрицательными весами.

Псевдокод алгоритма выглядит следующим образом:

  • Пусть A = 2-D массив размером n * n, где n — количество вершин
  • Инициализация A [0, s] = 0 ; А [0, v] = бесконечность для всех V ≠ ев , где s является узел мы находим кратчайший путь для
  • для i = 1,2,3,… n-1

    • для каждого v ∈ V

      • A [i, v] = min {A [i-1, v],

         min (w, v) ∈ E {A [k-1, w] + стоимость wv }
         & nbsp}

      • где (w, v) — входящие ребра вершины v
  • проверить наличие отрицательных циклов, выполнив еще раз и проверив A [n] = A [n-1]
  • Если они равны, верните A [n-1], в противном случае сообщите об отрицательном цикле.

Моя первая версия выглядела так:

import os
file = open(os.path.dirname(os.path.realpath(__file__)) + "/g_small.txt")
vertices, edges = map(lambda x: int(x), file.readline().replace("\n", "").split(" "))
 
adjacency_list = [[] for k in xrange(vertices)]
for line in file.readlines():
    tail, head, weight = line.split(" ")
    adjacency_list[int(head)-1].append({"from" : int(tail), "weight" : int(weight)})
 
s=0
cache = [[0 for k in xrange(vertices+1)] for j in xrange(vertices+1)]
cache[0][s] = 0
 
for v in range(0, vertices):
  if v != s:
    cache[0][v] = float("inf")
 
for i in range(1, vertices):
  for v in range(0, vertices):
    least_adjacent_cost = calculate_least_adjacent_cost(adjacency_list, i, v, cache[i-1])
    cache[i][v] = min(cache[i-1][v], least_adjacent_cost)
 
# detecting negative cycles
for v in range(0, vertices):
  least_adjacent_cost = calculate_least_adjacent_cost(adjacency_list, i, v, cache[vertices-1])  
  cache[vertices][v] = min(cache[vertices-1][v], least_adjacent_cost)
 
if(not cache[vertices] == cache[vertices-1]):
    raise Exception("negative cycle detected")
 
shortest_path = min(cache[vertices-1])
print("Shortest Path: " + str(shortest_path))

где define_least_adjacent_cost определяется так:

def calculate_least_adjacent_cost(adjacency_list, i, v, cache):
    adjacent_nodes = adjacency_list[v]
 
    least_adjacent_cost = float("inf")
    for node in adjacent_nodes:
      adjacent_cost = cache[node["from"]-1] + node["weight"]
      if adjacent_cost < least_adjacent_cost:
        least_adjacent_cost = adjacent_cost
    return least_adjacent_cost

Как вы можете видеть, мы используем список смежности в качестве представления графа, отображая каждый узел на соответствующие ребра. Затем мы инициализируем кэш согласно алгоритму, а затем имеем два вложенных цикла for, которые мы используем для определения кратчайшего пути от s до каждой вершины.

Функция calculate_least_adjacent_cost используется для определения того, какое из входящих ребер в вершине имеет наименьшую стоимость, с учетом предыдущих вычислений кратчайшего пути, которые мы сделали до исходных вершин этих входящих ребер.

Затем у нас есть дополнительный вызов в конце, чтобы проверить наличие отрицательных циклов. Если нет изменений в значениях, вычисленных по s для каждой вершины, мы знаем, что у нас нет отрицательных циклов, потому что в противном случае один из них вступил бы в силу и дал бы нам другой результат.

Этот алгоритм работает, но он неэффективен в использовании пространства — наш кэш имеет размер n * n, когда мы заботимся только о двух строках — предыдущей и текущей — поэтому мы можем просто использовать вместо этого список.

Если мы сделаем это, код теперь будет выглядеть так:

s=0
cache = [[] for j in xrange(vertices+1)]
cache[s] = 0
 
for v in range(0, vertices):
  if v != s:
    cache[v] = float("inf")
 
for i in range(1, vertices):
  for v in range(0, vertices):
    previous_cache = cache
    least_adjacent_cost = calculate_least_adjacent_cost(adjacency_list, i, v, previous_cache)
    cache[v] = min(previous_cache[v], least_adjacent_cost)
 
# detecting negative cycles
for v in range(0, vertices):
  previous_cache = copy.deepcopy(cache)
  least_adjacent_cost = calculate_least_adjacent_cost(adjacency_list, i, v, previous_cache)
  cache[v] = min(previous_cache[v], least_adjacent_cost)
 
if(not cache == previous_cache):
    raise Exception("negative cycle detected")

Делая это, мы теряем историю алгоритма во время выполнения, что означает, что в его текущем состоянии мы не сможем определить наш кратчайший путь, мы просто знаем его стоимость.

Для графа 1000, граничного графа 47978, требуется 27 секунд, чтобы пройти весь граф и обнаружить отрицательный цикл, если он есть.

Код для этого алгоритма на GitHub , как всегда.

372
Share: