May-08-2019, 01:41 PM
I'm making a project (the code I'm showing here is related to a part but not the same, more like practice exercise) where I have weighted edges and need to find the shortest path from node A to node B with DFS, the shortest path being the one where the sum of the edges' weights is the shortest. The original code given in this exercise considers the shortest path as the one that goes through less nodes, I have to alter it. I already added the weight parameter to the Edge class, and the addEdge method in the Digraph class was changed so that the key of the edges dictionary is the source node and the value is a list like [destination node, weight of the edge]. In theory, I kinda understand what I have to do to change the rest (like have a variable suming the weights of the paths as it goes, compare it and keep the smallest sum) but I'm very very new to programming and I get confused easily, so can anyone help? No breaks please. Sorry for my English, it's not my mother tongue. Here is the code:
class Node(object):
def __init__(self, name):
"""
Requires: name is a string
"""
self.name = name
def getName(self):
return self.name
def __str__(self):
return self.name
class Edge(object):
def __init__(self, src, dest, weight):
"""
Requires: src and dst Nodes, weight float
"""
self.src = src
self.dest = dest
self.weight = weight
def getSource(self):
return self.src
def getDestination(self):
return self.dest
def getWeight(self):
return self.weight
def __str__(self):
return self.src.getName() + '---' + str(self.weight) + '--->' + self.dest.getName()
class Digraph(object):
#nodes is a list of the nodes in the graph
#edges is a dict mapping each node to a list of its children and weights
def __init__(self):
self.nodes = []
self.edges = {}
def addNode(self, node):
if node in self.nodes:
raise ValueError('Duplicate node')
else:
self.nodes.append(node)
self.edges[node] = []
def addEdge(self, edge):
src = edge.getSource()
dest = edge.getDestination()
weight = edge.getWeight()
if not(src in self.nodes and dest in self.nodes):
raise ValueError('Node not in graph')
self.edges[src].append([dest, weight])
def childrenOf(self, node):
return self.edges[node]
def hasNode(self, node):
return node in self.nodes
def __str__(self):
result = ''
for src in self.nodes:
for dest in self.edges[src]:
result = result + src.getName() + '->'
+ dest.getName() + '\n'
return result
#all done till here
def printPath(path):
"""
Requires: path a list of nodes
"""
result = ''
for i in range(len(path)):
result = result + str(path[i])
if i != len(path) - 1:
result = result + '->'
return result
def DFS(graph, start, end, path, shortest):
"""
Requires:
graph a Digraph;
start and end nodes;
path and shortest lists of nodes
Ensures:
a shortest path from start to end in graph
"""
path = path + [start]
print('Current DFS path:', printPath(path))
if start == end:
return path
for node in graph.childrenOf(start):
if node not in path: #avoid cycles
if shortest == None or len(path) < len(shortest):
newPath = DFS(graph, node, end, path, shortest)
if newPath != None:
shortest = newPath
return shortest
def search(graph, start, end):
"""
Requires:
graph a Digraph;
start and end are nodes
Ensures:
shortest path from start to end in graph
"""
return DFS(graph, start, end, [], None)
