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)