knapscak and graph optimization problems def printpath(path)"""assumes path is list of nodes""result 'for in range(len(path))result result str(path[ ]if !len(path result result '->return result def dfs(graphstartendpathshortest)"""assumes graph is digraphstart and end are nodespath and shortest are lists of nodes returns shortest path from start to end in graph""path path [startprint 'current dfs path:'printpath(pathif start =endreturn path for node in graph childrenof(start)if node not in path#avoid cycles if shortest =none or len(pathlen(shortest)newpath dfs(graphnodeendpathshortestif newpath !noneshortest newpath return shortest def search(graphstartend)"""assumes graph is digraphstart and end are nodes returns shortest path from start to end in graph""return dfs(graphstartend[]nonefigure depth-first-search shortest-path algorithm def testsp()nodes [for name in range( )#create nodes nodes append(node(str(name)) digraph(for in nodesg addnode(ng addedge(edge(nodes[ ],nodes[ ]) addedge(edge(nodes[ ],nodes[ ]) addedge(edge(nodes[ ],nodes[ ]) addedge(edge(nodes[ ],nodes[ ]) addedge(edge(nodes[ ],nodes[ ]) addedge(edge(nodes[ ],nodes[ ]) addedge(edge(nodes[ ],nodes[ ]) addedge(edge(nodes[ ],nodes[ ]) addedge(edge(nodes[ ],nodes[ ]) addedge(edge(nodes[ ],nodes[ ])sp search(gnodes[ ]nodes[ ]print 'shortest path found by dfs:'printpath(spfigure test depth-first-search code