python - Dijkstra 算法的 Python 实现不适用于所有图形类型
问题描述
下面是我为实现编写的代码,它与在函数之前初始化的名为“graph”的图形完美配合。但它不断遇到“graph2”错误。
'''
The graphs below will be used to test the directed and
undirected capabilities of my algorithm.
'''
graph = {"A": {"B": 2, "C" : 4},
"B" : {"C" : 5, "D" : 6},
"C" : {"D" : 2}
}
graph2 = {"A" : {"B" : 4, "C" : 2, "D" : 8},
"B" : {"A" : 4, "C" : 1, "D" : 3},
"C" : {"A" : 2, "B" : 1, "D" : 4},
"D" : {"A" : 8, "B" : 3, "C" : 4}
}
infinity = float("inf")
start = "A"
end = "D"
def DijkstrasAlgorithm(grid, sourceNode, endNode):
# "allnodes" is used to contain all nodes present in the grid inputted into the function.
# "visitedNodes" is used to store nodes that have been visited.
# "distances" stores edges (connections between 2 nodes) and their weights (the magnitude of their distance).
# "parents" is a dictionary used to form the basis with which the shortest path can be outputted, by interlinking the
# the parents of each class from the start to the end.
currentNode, allNodes, visitedNodes = sourceNode, set(), set()
distances, parents, paths = [], dict(), []
# This for loop adds all individual nodes to the set, which becomes a list, called 'allNodes'
for i in grid:
allNodes.add(i)
for j in grid[i]:
allNodes.add(j)
allNodes = sorted(list(allNodes))
#This for loop sets all distances between all nodes equal to infinity
for i in grid:
for j in grid[i]:
distances.append([i, j, infinity])
#This for loop sets the initial parent node of all nodes equal to None
for node in allNodes:
parents[node] = None
# This for loops sets the distances for all nodes that can be set
for i in grid:
for j in grid[i]:
try:
distances.append([i, j, grid[i][j]])
distances.remove([i, j, infinity])
except KeyError:
continue
except:
print("Error occurred during edge weight update.")
# This while loop is the actual part of the code that accounts for Dijkstras algorithm
# it continues to iterate choosing the node of minimum distance until the length of the 'allNodes' set is equal to zero
while len(allNodes) > 0:
# This if-statement ends the loop once the destination has been reached
if currentNode == endNode:
break
# These 2 statements remove the current node from the 'allNodes' set and add them to
# the visited nodes set
allNodes.remove(currentNode)
visitedNodes.add(currentNode)
comparisonRange = []
# This for loop chooses the closes nodes to the comparison node to compare
# and select the node of minimum distance
for edge in distances:
if (edge[0] == currentNode) and (edge[1] not in visitedNodes):
comparisonRange.append(edge)
comparisonRange = sorted(comparisonRange, key = lambda x: x[2])
parents[comparisonRange[0][1]] = currentNode
currentNode = comparisonRange[0][1]
# The above code is the 'greedy' part of the algorithm selecting the node of minimum distance
# each time
possiblePath = []
# The for loop below appends the nodes in order of visitation
# Its starts with the node whose parent is still None, which can only be the start node
# and all nodes that branch from it and so on so forth are appended to the possiblePath list.
# This ensures possible path holds the nodes in order of visitation.
for node in parents.keys():
if parents[node] == None:
possiblePath.append(node)
if parents[node] in possiblePath:
possiblePath.append(node)
# This code adds one possible path to the group of possible paths named 'paths'
paths.append(possiblePath)
# This for loop creates other possible paths spanning from the first one
# simply by deleting a previous choice
for i in range(len(paths[0]) - 1):
alternatePath = [element for element in paths[i]]
alternatePath.pop(1)
if len(alternatePath) == 2:
break
paths.append(alternatePath)
# This list holds zero for the initial length of each possible path
pathLengths =[[0] for item in paths]
# This for loop is used to calculate the lengths of possible paths from
# items contained within each possible path. This is done by passing those
# items into the 'graph' dictionary and calculating the length between them
for path in paths:
length = 0
for index in path:
try:
for secondKey in grid[index]:
if secondKey == path[path.index(index)+1]:
try:
length += grid[index][secondKey]
except KeyError:
continue
pathLengths[paths.index(path)] = length
except KeyError:
continue
# The minimum path variable below chooses the minimum length in pathLengths
# and uses that index to find the path that it corresponds to in the list
# paths
minimumPath = paths[pathLengths.index(min(pathLengths))]
return minimumPath
DijkstrasAlgorithm(graph, start, end)
我也考虑过使用类,但我不知道如何实现它们。
请告诉我你的想法,给我关于如何改进代码和我的编程技能的建议,你能否告诉我我可以使用的任何方法,以确保我的实现可以在输入到其中的任何图形上工作。
解决方案
如果您可以在图形算法中使用邻接矩阵(https://en.wikipedia.org/wiki/Adjacency_matrix),因为它更快,例如https://gist.github.com/shintoishere/f0fa40fe1134b20e7729