Ниже приведен код, который я написал для реализации, и он отлично работает с графом с именем '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)
Я также думал об использовании классов, но я не знаю, как их реализовать.
Пожалуйста, скажите мне, что вы думаете, дайте мои предложения о том, как улучшить код и мои навыки программирования в целом, и не могли бы вы также сообщить мне о любых методах, которые я мог бы использовать, чтобы моя реализация могла работать с любым графом, введенным в него.