Вот решение Рубин с использованием взвешенной матрицы ADJ и избежать циклов. Это немного грязно, но швы работают. Я тестирую график с узлами a, b, c, d, e, f в контуре соединения (как кольцо), но с двумя дополнительными соединениями (b < -> f и c < -> f) Циклы генерации для проверки алгоритма.
# Generate all paths from A to E
@grapascii =
'
C-----D
/\ |
B---F---E
\/
A
'
@nodes = %w{A B C D E F}
n = -1 # represents no connection
#weighted adj matrix
@adjmat = [
#a b c d e f
[n, 1, n, n, n, 1], # a
[1, n, 3, n, n, 1], # b
[n, 4, n, 2, n, 1], # c
[n, n, 4, n, 1, n], # d
[n, n, n, 1, n, 1], # e
[1, 6, 1, n, 2, n] # f
]
# generate a neighbors hash for easy and fast future acccess
def gen_neighbors(nodes, adjmat)
len = nodes.length
neighbors = {}
for i in 0..(len - 1)
for j in 0..(len - 1)
if adjmat[i][j] >= 0 && i != j
neighbors[nodes[i]] ||= []
neighbors[nodes[i]] << {:node => nodes[j], :cost => adjmat[i][j]}
end
end
end
return neighbors
end
@neighbors = gen_neighbors(@nodes, @adjmat)
def all_paths(currpath, destnode, currcost, paths)
#the current node is always tha last one on the current evaluated path
currnode = currpath.last
# just the neighbors that is nor on the current evaluated path, to avoid cycles
current_neighbors = @neighbors[currnode].select{|n| !currpath.include?(n[:node])}
#each neighbor is a hash with :node and :cost
current_neighbors.each do |neighbor|
# yes. we have to duplicate that. maybe there is a better solution...
new_path = currpath + [neighbor[:node]]
cost = currcost + neighbor[:cost]
if neighbor[:node] == destnode
#FOUND PATH
paths << {:path => new_path, :cost => cost}
else
all_paths(new_path, destnode, cost, paths)
end
end
end
puts @grapascii
puts "NEIGHBORS HASH:"
@neighbors.each do |node, neighbors|
neighbors_and_cost = neighbors.map{|n| "#{n[:node]}(#{n[:cost]})"}
puts "#{node} => #{neighbors_and_cost.join(', ')}"
end
# start path with the start node
startpath = ['A']
# paths variable will hold all possible paths without cycles
paths = []
all_paths(startpath, 'E', 0, paths)
puts "PATHS:"
# sort paths by total cost(optional)
paths.sort!{|a, b| a[:cost] <=> b[:cost]}
paths.each do |path|
puts "#{path[:path]} => #{path[:cost]}"
end
Выход:
C-----D
/\ |
B---F---E
\/
A
NEIGHBORS HASH:
A => B(1), F(1)
B => A(1), C(3), F(1)
C => B(4), D(2), F(1)
D => C(4), E(1)
E => D(1), F(1)
F => A(1), B(6), C(1), E(2)
PATHS:
["A", "F", "E"] => 3
["A", "B", "F", "E"] => 4
["A", "F", "C", "D", "E"] => 5
["A", "B", "F", "C", "D", "E"] => 6
["A", "B", "C", "D", "E"] => 7
["A", "B", "C", "F", "E"] => 7
["A", "F", "B", "C", "D", "E"] => 13
На самом деле, вы могли бы просто сделать рекурсивный DFS, но даем всегда в качестве параметра посещенных узлов и убедившись, что вы не копать глубже в узлы уже посещенных в текущем DFS (таким образом, избегая циклов). Обратите внимание, что это отличается от глобального посещенного списка, поскольку он не позволит вам посещать один и тот же узел более одного раза. –
О, и в качестве плюса посещаемый список, который вы ведете, - это именно тот путь, который вам нужен, когда вы найдете конечный узел. –
Мне плохо, что я должен упомянуть, что я пробовал нерекурсивную DFS. но проблема в том, чтобы найти один простой путь в приведенном выше рисунке {a -> b -> c -> e -> f}, тогда вы ищите второй путь, но 'e' стали посещать уже, поэтому не можете идти дальше. рекурсивная DFS решает это? – arslan