Yen的最短路径算法中如何忽略等长路径（python networkx）
How to ignore paths of equal length in Yen's shortest path algorithm (python networkx)
我正在使用代码来实现 Yen 的算法以找到 k 条最短路径。但是我希望它产生不同长度的 k 最短路径，即如果多条路径具有相同的长度，它只选择其中之一和 returns 长度。
Yen的算法代码如下（转自https://github.com/nextgis/metro4all/wiki/Yen%27s-algorithm-for-networkx）：
import networkx as nx
import Queue
def path_cost(graph, path, weight=None):
pathcost = 0
for i in range(len(path)):
if i > 0:
edge = (path[i-1], path[i])
if weight != None:
pathcost += graph.get_edge_data(*edge)[weight]
else:
#just count the number of edges
pathcost += 1
return pathcost
def ksp(graph, source, target, num_k, weight):
# Shortest path from the source to the target
A = [nx.shortest_path(graph, source, target, weight=weight)]
A_costs = [path_cost(graph, A[0], weight)]#[nx.shortest_path_length(graph, source, target, weight=weight)]
# Initialize the heap to store the potential kth shortest path
B = Queue.PriorityQueue()
for k in range(1, num_k):
# The spur node ranges from the first node to the next to last node in the shortest path
try:
for i in range(len(A[k-1])-1):
# Spur node is retrieved from the previous k-shortest path, k - 1
spurNode = A[k-1][i]
# The sequence of nodes from the source to the spur node of the previous k-shortest path
rootPath = A[k-1][:i]
# We store the removed edges
removed_edges = []
for path in A:
if len(path) - 1 > i and rootPath == path[:i]:
# Remove the links that are part of the previous shortest paths which share the same root path
edge = (path[i], path[i+1])
if not graph.has_edge(*edge):
continue
removed_edges.append((edge, graph.get_edge_data(*edge)))
graph.remove_edge(*edge)
# Calculate the spur path from the spur node to the sink
try:
spurPath = nx.shortest_path(graph, spurNode, target, weight=weight)
# Entire path is made up of the root path and spur path
totalPath = rootPath + spurPath
totalPathCost = path_cost(graph, totalPath, weight)
# Add the potential k-shortest path to the heap
B.put((totalPathCost, totalPath))
except nx.NetworkXNoPath:
pass
#Add back the edges that were removed from the graph
for removed_edge in removed_edges:
graph.add_edge(
*removed_edge[0],
**removed_edge[1]
)
# Sort the potential k-shortest paths by cost
# B is already sorted
# Add the lowest cost path becomes the k-shortest path.
while True:
try:
cost_, path_ = B.get(False)
if path_ not in A:
A.append(path_)
A_costs.append(cost_)
break
except Empty:
break
except Queue.IndexError:
pass
return A_costs
我试图将 if path_ not in A: 末尾的行更改为 if (path_ not in A) and (cost_ not in A_costs):，但是 returns 错误
AttributeError Traceback (most recent call last)
<ipython-input-58-038c80524d5d> in <module>()
----> 1 ksp(G,'source','target',100,"weight")
<ipython-input-54-7b3d0aa42558> in ksp(graph, source, target, num_k, weight)
77 except Empty:
78 break
---> 79 except Queue.IndexError:
80 pass
81
AttributeError: 'module' object has no attribute 'IndexError'
什么是更好的方法？
编辑：
我的测试图如下：
G = nx.DiGraph()
G.add_node("source")
G.add_node("target")
for i in range(16):
G.add_node(i+1)
for i in range(4):
G.add_edge("source",i+1,weight=0)
G.add_edge(16-i,"target",weight=0)
W=np.empty([3,4,4])
W[0::]=np.array([[3,9,7,16],
[21,2,18,29],
[37,32,41,17],
[42,12,19,26]])
W[1::]=np.array([[9,12,10,22],
[24,5,11,28],
[40,35,38,19],
[45,6,43,27]])
W[2::]=np.array([[1,2,3,4],
[5,6,7,8],
[9,10,11,12],
[13,14,15,16]])
for i in range(4):
for j in range(4):
G.add_edge(i+1,j+5,weight=W[0,i,j])
G.add_edge(i+5,j+9,weight=W[1,i,j])
G.add_edge(i+9,j+13,weight=W[2,i,j])
如果我这样做
print newnewksp(G,'source','target',8,"weight")
print newksp(G,'source','target',35,"weight")
print ksp(G,'source','target',35,"weight")
（其中 newksp 是我的建议，newnewksp @H4kim 的建议），我得到
[12.0, 13.0, 22.0, 27.0, 31.0, 40.0, 43.0, 50.0]
[12.0, 13.0, 14.0, 15.0, 16.0, 19.0, 20.0, 21.0, 22.0, 23.0, 27.0, 28.0, 29.0, 30.0, 31.0, 32.0, 34.0, 35.0, 36.0, 37.0, 39.0, 40.0, 41.0, 42.0, 47.0, 48.0, 49.0, 50.0, 51.0, 52.0, 53.0, 54.0, 55.0, 56.0, 57.0]
[12.0, 13.0, 13.0, 14.0, 14.0, 15.0, 15.0, 16.0, 19.0, 20.0, 20.0, 21.0, 21.0, 22.0, 22.0, 22.0, 22.0, 22.0, 23.0, 23.0, 23.0, 23.0, 24.0, 24.0, 24.0, 25.0, 25.0, 25.0, 27.0, 27.0, 28.0, 28.0, 28.0, 29.0, 29.0]
我认为您的更改没问题，但 Queue.IndexError 应替换为 IndexError，因为它是 python 内置异常。相反 Empty 不是内置异常，所以它应该是 Queue.Empty.
我想我们不应该在主循环中更改 A，因为它对算法至关重要。相反，我们可以尝试通过跟踪 set :
中的不同成本值来更改结束条件
import networkx as nx
import Queue
def path_cost(graph, path, weight=None):
pathcost = 0
for i in range(len(path)):
if i > 0:
edge = (path[i-1], path[i])
if weight != None:
pathcost += graph.get_edge_data(*edge)[weight]
else:
#just count the number of edges
pathcost += 1
return pathcost
def ksp(graph, source, target, num_k, weight):
# Shortest path from the source to the target
A = [nx.shortest_path(graph, source, target, weight=weight)]
A_costs = [path_cost(graph, A[0], weight)]
unique_costs = set(A_costs)
# Initialize the heap to store the potential kth shortest path
B = Queue.PriorityQueue()
k = 1
while len(unique_costs) < num_k:
# The spur node ranges from the first node to the next to last node in the shortest path
try:
for i in range(len(A[k-1])-1):
# Spur node is retrieved from the previous k-shortest path, k - 1
spurNode = A[k-1][i]
# The sequence of nodes from the source to the spur node of the previous k-shortest path
rootPath = A[k-1][:i]
# We store the removed edges
removed_edges = []
for path in A:
if len(path) - 1 > i and rootPath == path[:i]:
# Remove the links that are part of the previous shortest paths which share the same root path
edge = (path[i], path[i+1])
if not graph.has_edge(*edge):
continue
removed_edges.append((edge, graph.get_edge_data(*edge)))
graph.remove_edge(*edge)
# Calculate the spur path from the spur node to the sink
try:
spurPath = nx.shortest_path(graph, spurNode, target, weight=weight)
# Entire path is made up of the root path and spur path
totalPath = rootPath + spurPath
totalPathCost = path_cost(graph, totalPath, weight)
# Add the potential k-shortest path to the heap
B.put((totalPathCost, totalPath))
except nx.NetworkXNoPath:
pass
#Add back the edges that were removed from the graph
for removed_edge in removed_edges:
graph.add_edge(
*removed_edge[0],
**removed_edge[1]
)
# Sort the potential k-shortest paths by cost
# B is already sorted
# Add the lowest cost path becomes the k-shortest path.
while True:
try:
cost_, path_ = B.get(False)
if path_ not in A:
A.append(path_)
A_costs.append(cost_)
unique_costs.add(cost_)
break
except Queue.Empty:
break
except IndexError:
pass
k += 1
return list(unique_costs)
它 returns 下面以你的例子为例：
>>> print ksp(G,'source','target',35,"weight")
[12.0, 13.0, 14.0, 15.0, 16.0, 19.0, 20.0, 21.0, 22.0, 23.0, 24.0, 25.0, 27.0, 28.0, 29.0, 30.0, 31.0, 32.0, 33.0, 34.0, 35.0, 36.0, 37.0, 38.0, 39.0, 40.0, 41.0, 42.0, 43.0, 44.0, 45.0, 46.0, 47.0, 48.0, 49.0]
我正在使用代码来实现 Yen 的算法以找到 k 条最短路径。但是我希望它产生不同长度的 k 最短路径，即如果多条路径具有相同的长度，它只选择其中之一和 returns 长度。
Yen的算法代码如下（转自https://github.com/nextgis/metro4all/wiki/Yen%27s-algorithm-for-networkx）：
import networkx as nx
import Queue
def path_cost(graph, path, weight=None):
pathcost = 0
for i in range(len(path)):
if i > 0:
edge = (path[i-1], path[i])
if weight != None:
pathcost += graph.get_edge_data(*edge)[weight]
else:
#just count the number of edges
pathcost += 1
return pathcost
def ksp(graph, source, target, num_k, weight):
# Shortest path from the source to the target
A = [nx.shortest_path(graph, source, target, weight=weight)]
A_costs = [path_cost(graph, A[0], weight)]#[nx.shortest_path_length(graph, source, target, weight=weight)]
# Initialize the heap to store the potential kth shortest path
B = Queue.PriorityQueue()
for k in range(1, num_k):
# The spur node ranges from the first node to the next to last node in the shortest path
try:
for i in range(len(A[k-1])-1):
# Spur node is retrieved from the previous k-shortest path, k - 1
spurNode = A[k-1][i]
# The sequence of nodes from the source to the spur node of the previous k-shortest path
rootPath = A[k-1][:i]
# We store the removed edges
removed_edges = []
for path in A:
if len(path) - 1 > i and rootPath == path[:i]:
# Remove the links that are part of the previous shortest paths which share the same root path
edge = (path[i], path[i+1])
if not graph.has_edge(*edge):
continue
removed_edges.append((edge, graph.get_edge_data(*edge)))
graph.remove_edge(*edge)
# Calculate the spur path from the spur node to the sink
try:
spurPath = nx.shortest_path(graph, spurNode, target, weight=weight)
# Entire path is made up of the root path and spur path
totalPath = rootPath + spurPath
totalPathCost = path_cost(graph, totalPath, weight)
# Add the potential k-shortest path to the heap
B.put((totalPathCost, totalPath))
except nx.NetworkXNoPath:
pass
#Add back the edges that were removed from the graph
for removed_edge in removed_edges:
graph.add_edge(
*removed_edge[0],
**removed_edge[1]
)
# Sort the potential k-shortest paths by cost
# B is already sorted
# Add the lowest cost path becomes the k-shortest path.
while True:
try:
cost_, path_ = B.get(False)
if path_ not in A:
A.append(path_)
A_costs.append(cost_)
break
except Empty:
break
except Queue.IndexError:
pass
return A_costs
我试图将 if path_ not in A: 末尾的行更改为 if (path_ not in A) and (cost_ not in A_costs):，但是 returns 错误
AttributeError Traceback (most recent call last)
<ipython-input-58-038c80524d5d> in <module>()
----> 1 ksp(G,'source','target',100,"weight")
<ipython-input-54-7b3d0aa42558> in ksp(graph, source, target, num_k, weight)
77 except Empty:
78 break
---> 79 except Queue.IndexError:
80 pass
81
AttributeError: 'module' object has no attribute 'IndexError'
什么是更好的方法？
编辑： 我的测试图如下：
G = nx.DiGraph()
G.add_node("source")
G.add_node("target")
for i in range(16):
G.add_node(i+1)
for i in range(4):
G.add_edge("source",i+1,weight=0)
G.add_edge(16-i,"target",weight=0)
W=np.empty([3,4,4])
W[0::]=np.array([[3,9,7,16],
[21,2,18,29],
[37,32,41,17],
[42,12,19,26]])
W[1::]=np.array([[9,12,10,22],
[24,5,11,28],
[40,35,38,19],
[45,6,43,27]])
W[2::]=np.array([[1,2,3,4],
[5,6,7,8],
[9,10,11,12],
[13,14,15,16]])
for i in range(4):
for j in range(4):
G.add_edge(i+1,j+5,weight=W[0,i,j])
G.add_edge(i+5,j+9,weight=W[1,i,j])
G.add_edge(i+9,j+13,weight=W[2,i,j])
如果我这样做
print newnewksp(G,'source','target',8,"weight")
print newksp(G,'source','target',35,"weight")
print ksp(G,'source','target',35,"weight")
（其中 newksp 是我的建议，newnewksp @H4kim 的建议），我得到
[12.0, 13.0, 22.0, 27.0, 31.0, 40.0, 43.0, 50.0]
[12.0, 13.0, 14.0, 15.0, 16.0, 19.0, 20.0, 21.0, 22.0, 23.0, 27.0, 28.0, 29.0, 30.0, 31.0, 32.0, 34.0, 35.0, 36.0, 37.0, 39.0, 40.0, 41.0, 42.0, 47.0, 48.0, 49.0, 50.0, 51.0, 52.0, 53.0, 54.0, 55.0, 56.0, 57.0]
[12.0, 13.0, 13.0, 14.0, 14.0, 15.0, 15.0, 16.0, 19.0, 20.0, 20.0, 21.0, 21.0, 22.0, 22.0, 22.0, 22.0, 22.0, 23.0, 23.0, 23.0, 23.0, 24.0, 24.0, 24.0, 25.0, 25.0, 25.0, 27.0, 27.0, 28.0, 28.0, 28.0, 29.0, 29.0]
我认为您的更改没问题，但 Queue.IndexError 应替换为 IndexError，因为它是 python 内置异常。相反 Empty 不是内置异常，所以它应该是 Queue.Empty.
我想我们不应该在主循环中更改 A，因为它对算法至关重要。相反，我们可以尝试通过跟踪 set :
import networkx as nx
import Queue
def path_cost(graph, path, weight=None):
pathcost = 0
for i in range(len(path)):
if i > 0:
edge = (path[i-1], path[i])
if weight != None:
pathcost += graph.get_edge_data(*edge)[weight]
else:
#just count the number of edges
pathcost += 1
return pathcost
def ksp(graph, source, target, num_k, weight):
# Shortest path from the source to the target
A = [nx.shortest_path(graph, source, target, weight=weight)]
A_costs = [path_cost(graph, A[0], weight)]
unique_costs = set(A_costs)
# Initialize the heap to store the potential kth shortest path
B = Queue.PriorityQueue()
k = 1
while len(unique_costs) < num_k:
# The spur node ranges from the first node to the next to last node in the shortest path
try:
for i in range(len(A[k-1])-1):
# Spur node is retrieved from the previous k-shortest path, k - 1
spurNode = A[k-1][i]
# The sequence of nodes from the source to the spur node of the previous k-shortest path
rootPath = A[k-1][:i]
# We store the removed edges
removed_edges = []
for path in A:
if len(path) - 1 > i and rootPath == path[:i]:
# Remove the links that are part of the previous shortest paths which share the same root path
edge = (path[i], path[i+1])
if not graph.has_edge(*edge):
continue
removed_edges.append((edge, graph.get_edge_data(*edge)))
graph.remove_edge(*edge)
# Calculate the spur path from the spur node to the sink
try:
spurPath = nx.shortest_path(graph, spurNode, target, weight=weight)
# Entire path is made up of the root path and spur path
totalPath = rootPath + spurPath
totalPathCost = path_cost(graph, totalPath, weight)
# Add the potential k-shortest path to the heap
B.put((totalPathCost, totalPath))
except nx.NetworkXNoPath:
pass
#Add back the edges that were removed from the graph
for removed_edge in removed_edges:
graph.add_edge(
*removed_edge[0],
**removed_edge[1]
)
# Sort the potential k-shortest paths by cost
# B is already sorted
# Add the lowest cost path becomes the k-shortest path.
while True:
try:
cost_, path_ = B.get(False)
if path_ not in A:
A.append(path_)
A_costs.append(cost_)
unique_costs.add(cost_)
break
except Queue.Empty:
break
except IndexError:
pass
k += 1
return list(unique_costs)
它 returns 下面以你的例子为例：
>>> print ksp(G,'source','target',35,"weight")
[12.0, 13.0, 14.0, 15.0, 16.0, 19.0, 20.0, 21.0, 22.0, 23.0, 24.0, 25.0, 27.0, 28.0, 29.0, 30.0, 31.0, 32.0, 33.0, 34.0, 35.0, 36.0, 37.0, 38.0, 39.0, 40.0, 41.0, 42.0, 43.0, 44.0, 45.0, 46.0, 47.0, 48.0, 49.0]