下面是我为该实现编写的代码，它与在函数之前初始化的名为“ 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中