knapscak and graph optimization problems def bfs(graphstartend)"""assumes graph is digraphstart and end are nodes returns shortest path from start to end in graph""initpath [startpathqueue [initpathwhile len(pathqueue! #get and remove oldest element in pathqueue tmppath pathqueue pop( print 'current bfs path:'printpath(tmppathlastnode tmppath[- if lastnode =endreturn tmppath for nextnode in graph childrenof(lastnode)if nextnode not in tmppathnewpath tmppath [nextnodepathqueue append(newpathreturn none figure breadth-first-search shortest path when the lines sp bfs(gnodes[ ]nodes[ ]print 'shortest path found by bfs:'printpath(spare added at the end of testsp and the function is executed it prints current dfs path current dfs path -> current dfs path -> -> current dfs path -> -> -> current dfs path -> -> -> -> current dfs path -> -> -> -> current dfs path -> -> -> current dfs path -> current dfs path -> -> current dfs path -> -> -> current dfs path -> -> -> current dfs path -> -> -> current dfs path -> -> shortest path found by dfs -> -> -> current bfs path current bfs path -> current bfs path -> current bfs path -> -> current bfs path -> -> current bfs path -> -> current bfs path -> -> -> current bfs path -> -> -> current bfs path -> -> -> current bfs path -> -> -> shortest path found by bfs -> -> ->