Алгоритм хранения dist (node, start) для всех узлов в неориентированном графе

Question

Цель состоит в том, чтобы создать массив с именем siz, который хранит длину всех путей от начального узла. В идеальном случае я бы вызвал f (start) и ожидал, что siz [v] заполнится для всех вершин v в графе.

Это алгоритм, который я использую.

def f (node):
    vis[node] = 1
    for elem in adj[node]:
        if vis[elem]==0:
            for i in siz[node]:
                    siz[elem].append(i + w[(node,elem)])
            f(elem)

Описания переменных:

1. adj [cur_nod] содержит всех соседей узла cur_nod
2. siz [cur_nod] (это список, а не тип данных int) содержит все расстояния от узла 1 до узла cur_nod
3. w (x, y) обозначают вес ребра, соединяющего узлы x и y
4. vis [nod] дорожек, если узел посещен. 0 - нет, 1 - посещено.

Рекурсия не выглядит корректной, и я не знаю, когда на самом деле пометить узел как посещенный. Кроме того, поскольку есть циклы, я не хочу, чтобы расстояния включали циклы. Например, A -> B -> C -> A -> D не должно быть регистром вообще. Это должен быть просто A -> D или все другие пути, по которым существует путь от A к D без прохождения цикла.

Чтобы привести пример того, как этот алгоритм не работает должным образом:

Если я введу узлы и веса ребер как w (1,2) = 1, w (2,3) = 2, w (2,4) = 7 и w (3,4) = 1.

Тогда siz = [[-1], [0], [1], [3], [4]]. (Обратите внимание, что изначально я установил siz [1] = 0 и siz [0] = - 1, поскольку мой начальный узел равен 1, а массив 0 проиндексирован, но мне нужно, чтобы он был 1 проиндексирован), тогда как идеальный siz должен иметь был [[-1], [0], [1], [3,9], [4,8]]

Answer 1

Что вы можете сделать, это просто рассмотреть текущий путь, по которому вы идете. Для последнего посещенного узла создайте соответствующий новый путь и добавьте его в 'siz', который я переименовал в node_paths. Затем выполните повторение для каждого соседа.

Поскольку путь, заданный для f (см. Код ниже), является копией , вам не нужно вручную удалять добавленный узел (однако, если, например, например, вы используете path.append(node), когда вы выходите f, вам, таким образом, придется path.pop())

data = [
(1, 2, 1),
(1, 3, 2),
(2, 4, 4),
(3, 4, 8),
]
adj = {}
w = {}
node_paths = {}
for (src, dst, weight) in data:
  if src not in adj:
    adj[src] = []
  if dst not in adj:
    adj[dst] = []

  adj[src].append(dst)
  adj[dst].append(src)
  w[(src, dst)] = weight
  w[(dst, src)] = weight

def f (path, weight, node, node_paths):
  if node in path:
    return
  path_to_node = path + [node]
  weight_to_node = weight + w[(path[-1], node)]
  if node not in node_paths:
    node_paths[node] = []
  node_paths[node].append((path_to_node[1:], weight_to_node))
  for neigh in adj[node]:
    f(path_to_node, weight_to_node, neigh, node_paths)

node_paths = {}
start = 1
w[(-1, start)] = 0
f([-1], 0, start, node_paths)
print(node_paths)

#{1: [([1], 0)], 2: [([1, 2], 1), ([1, 3, 4, 2], 14)], 4: [([1, 2, 4], 5), ([1, 3, 4], 10)], 3: [([1, 2, 4, 3], 13), ([1, 3], 2)]}

В приведенном выше коде я сохраняю как путь, так и взвешенную сумму, чтобы упростить отладку, но вы очевидно, может отбросить сохраненный путь

Несколько моментов:

• При отладке просто избегайте ввода пользовательских данных и жесткого кода, это помогает воспроизводимость и ускоряет попытки
• Хорошее свойство 1,2,4,8 в том, что (учитывая двоичное представление) любая комбинация (среди чисел), которую вы берете, даст другую сумму, которая «уникально» описывает ваш путь (даже если там у нас просто есть путь в распоряжении в любом случае)
• Я не следовал вашему алгоритму, потому что думаю, что он не работает для диаграмм с ромбами, как на приведенном выше графике (даже если в ориентированном графе нет цикла) (поскольку мы, вероятно, собираем одинаковые пути) (но я просто угадал, не проверял предположение и может ошибаться)