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

In Python, I have a Graph class that has a dictionary of vertex objects. Each vertex object has a dictionary of edges (which consist of a starting node, ending node, and a weight...imagine the end of arrow pointing to another node with a cost-to-travel number assigned to it).

With these classes, I'm graphing--well, a graph--for the time it takes for planes to fly from city to city. From this graph, I'm supposed to determine the shortes开发者_StackOverflow社区t-path (fastest-path) between two nodes using Dijkstra's algorithm. I'm also supposed to determine all the vertices reachable from a starting vertex.

I'm able to add edges and delete edges (and consequently, add nodes) perfectly in the Graph. However, for the life of me, I can not seem to figure out a simple way to implement Dijkstra's algorithm or Breadth-First Search (to determine the reachable vertices) using the data structures I have created.

If anyone could suggest what I need to do to alter or implement these algorithms so that they work correctly, I would greatly appreciate any help. This is a homework assignment that I have been working on for nearly a week, many hours per day, and I just can't seem to get passed this wall. Again, I would appreciate any advice or help. I'm not expecting anyone to write code for me, but pseudocode would help (and applying it--copying and pasting pseudocode from Wikipedia won't help me out as I've already been there).

---

Your code is way too complicated.

Start with a code just implementing the fundamentals and add features gradually. In order to get you started I'll post something simple but fundamental when handling graphs.

from collections import deque

class fringe(object):
    def __init__(self, kind= 'stack'):
        f= deque()
        self._p= f.append if kind is '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()):
    for node, path in F((start, [start])):
        for node in G[node]:
            if node is terminal:
                yield path+ [terminal]
            elif node not in path:
                F((node, path+ [node]))

and a 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'
    for path in paths(G, a, d): print path
    print 'DFS'
    for path in paths(G, a, d, fringe('queue')): print path

run will produce:

All paths from: A to: D
BFS
['A', 'C', 'D']
['A', 'B', 'D']
['A', 'B', 'C', 'D']
DFS
['A', 'B', 'D']
['A', 'C', 'D']
['A', 'B', 'C', 'D']