我在查找从名为 S 的源到名为 T 的目的地的 K 最短路径时遇到问题。我的代码如下所示
K = 4
S = 'C'
T = 'A'
B = {}
P = set()
count = {}
for U in graph.keys():
count[U] = 0
B[S] = 0
while(len(B)>=1 and count[T]<K):
PU = min(B, key = B.get)
cost = B[PU]
U = PU[len(PU)-1]
del B[PU]
count[U] += 1
if U==T:
P.add(U)
if count[U]<=K:
V = graph[U].keys()
for v in V:
if v not in PU:
PV = PU+v
B[PV] = cost+1
这相当于伪代码的实际代码,可以在 https://en.wikipedia.org/wiki/K_shortest_path_routing 找到。 。实际的变量也与伪代码中的相同。此外,我的图表如下所示:
{
'A': {'C': 4.0, 'B': 10.0, 'E': 10.0, 'D': 10.0, 'G': 1.0, 'F': 2.0, 'I': 3.0, 'H': 3.0, 'J': 10.0}, 'C': {'A': 4.0, 'B': 5.0, 'E': 9.0, 'D': 6.0, 'G': 9.0, 'F': 10.0, 'I': 5.0, 'H': 10.0, 'J': 5.0}, 'B': {'A': 2.0, 'C': 10.0, 'E': 8.0, 'D': 1.0, 'G': 8.0, 'F': 4.0, 'I': 2.0, 'H': 2.0, 'J': 6.0}, 'E': {'A': 9.0, 'C': 5.0, 'B': 10.0, 'D': 4.0, 'G': 9.0, 'F': 9.0, 'I': 3.0, 'H': 3.0, 'J': 7.0}, 'D': {'A': 4.0, 'C': 6.0, 'B': 5.0, 'E': 7.0, 'G': 1.0, 'F': 1.0, 'I': 2.0, 'H': 9.0, 'J': 3.0},
'G': {'A': 2.0, 'C': 10.0, 'B': 3.0, 'E': 1.0, 'D': 10.0, 'F': 5.0, 'I': 5.0, 'H': 6.0, 'J': 1.0}, 'F': {'A': 2.0, 'C': 3.0, 'B': 6.0, 'E': 7.0, 'D': 8.0, 'G': 10.0, 'I': 1.0, 'H': 8.0, 'J': 2.0}, 'I': {'A': 1.0, 'C': 1.0, 'B': 2.0, 'E': 1.0, 'D': 6.0, 'G': 7.0, 'F': 1.0, 'H': 6.0, 'J': 2.0},
'H': {'A': 3.0, 'C': 4.0, 'B': 5.0, 'E': 1.0, 'D': 2.0, 'G': 6.0, 'F': 4.0, 'I': 1.0, 'J': 4.0},
'J': {'A': 5.0, 'C': 6.0, 'B': 1.0, 'E': 8.0, 'D': 7.0, 'G': 9.0, 'F': 8.0, 'I': 10.0, 'H': 1.0}}
我的输出看起来像这样
{'A'}
而应该有四个路径。
另外,请注意我不允许使用 Networkx 或图形库。我必须只使用Python 中的基本库。
有人能够理解这个问题吗?
最佳答案
我对您的代码做了一些更改。您检查节点是否是目标的位置及其后的代码存在错误。
K = 4
S = 'C'
T = 'F'
B = {}
P = set()
count = {}
for U in graph.keys():
count[U] = 0
B[S] = 0
while(len(B)>=1 and count[T]<K):
PU = min(B, key = B.get)
print('Minimum Distance found in this loop : ' , PU)
cost = B[PU]
U = PU[len(PU)-1]
del B[PU]
count[U] += 1
if(U == T):
P.add(PU)
print('Closest neighbour of ' , S , ' is : ', U)
print('Reached target')
print('Final map : ', P)
exit(0)
else:
if count[U] <= K:
V = graph[U].keys()
print('Looking at neighbours of : ', PU)
for v in V:
if v not in PU:
PV = PU + v
print(PV)
B[PV] = cost+1
print('B dictionary is : ', B)
运行这个程序,你会得到类似的结果:
Minimum Distance found in this loop : C
Looking at neighbours of : C
CA
CB
CE
CD
CG
CF
CI
CH
CJ
B dictionary is : {'CA': 1, 'CB': 1, 'CE': 1, 'CD': 1, 'CG': 1, 'CF': 1, 'CI': 1, 'CH': 1, 'CJ': 1}
Minimum Distance found in this loop : CA
Closest neighbour of C is : A
Reached target
Final map : {'CA'}
输出应该具有相当的 self 描述性。 另外,你有与每个节点相关的权重(我认为是这样),那么我不明白为什么你将到每个相应邻居的距离计数只增加 1
关于python - K最短路径Python,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/44098799/