Python - Graph Data Structure - How Do I Implement Breadth-First Search to Find Reachable Vertices Correctly -

in python, have graph class has dictionary of vertex objects. each vertex object has dictionary of edges (which consist of starting node, ending node, , weight...imagine end of arrow pointing node cost-to-travel number assigned it).

with these classes, i'm graphing--well, graph--for time takes planes fly city city. graph, i'm supposed determine shortest-path (fastest-path) between 2 nodes using dijkstra's algorithm. i'm supposed determine vertices reachable starting vertex.

i'm able add edges , delete edges (and consequently, add nodes) in graph. however, life of me, can not seem figure out simple way implement dijkstra's algorithm or breadth-first search (to determine reachable vertices) using data structures have created.

if suggest need alter or implement these algorithms work correctly, appreciate help. is homework assignment have been working on week, many hours per day, , can't seem passed wall. again, appreciate advice or help. i'm not expecting write code me, pseudocode (and applying it--copying , pasting pseudocode wikipedia won't me out i've been there).

your code way complicated.

start code implementing fundamentals , add features gradually. in order started i'll post simple fundamental when handling graphs.

from collections import deque  class fringe(object):     def __init__(self, kind= 'stack'):         f= deque()         self._p= f.append if kind 'stack' else f.appendleft         self._f= f      def __call__(self, item):         self._p(item)         return self      def __iter__(self):         while len(self._f):             item= self._f.pop()             yield item      def __repr__(self):         return self._f.__repr__().replace('deque', 'fringe')  def paths(g, start, terminal, f= fringe()):     node, path in f((start, [start])):         node in g[node]:             if node terminal:                 yield path+ [terminal]             elif node not in path:                 f((node, path+ [node])) 

and test:

if __name__ == '__main__':     a, b, c, d, e, f= 'a', 'b', 'c', 'd', 'e', 'f'     g= {a: [b, c], b: [c, d], c: [d], d: [c], e: [f], f: [c]}     print 'all paths from:', a, 'to:', d     print 'bfs'     path in paths(g, a, d): print path     print 'dfs'     path in paths(g, a, d, fringe('queue')): print path 

run produce:

all paths from: to: d bfs ['a', 'c', 'd'] ['a', 'b', 'd'] ['a', 'b', 'c', 'd'] dfs ['a', 'b', 'd'] ['a', 'c', 'd'] ['a', 'b', 'c', 'd']