无权最短路径

def makeAdjacencyList():
    al = {}
    al[1] = [2, 4]
    al[2] = [4, 5]
    al[3] = [1, 6]
    al[4] = [5, 6, 7, 3]
    al[5] = [7]
    al[6] = []
    al[7] = [6]
    return al


class Vertex(object):
    def __init__(self):
        self.known = False
        self.dist = None
        self.path = None


def initializeTable(adjacencyList, vertexAsStart):
    T = {}
    for vrtx in adjacencyList.iterkeys():
        v = Vertex()
        T[vrtx] = v
    T[vertexAsStart].dist = 0
    return T


def findShortestPathInUnweightedGraph(adjacencyList):
    T = initializeTable(adjacencyList, 3)
    vertexs = adjacencyList.keys()
    currDist = 0
    for i in vertexs:
        for v in vertexs:
            if T[v].known == False and T[v].dist == currDist:
                T[v].known = True
                for w in adjacencyList[v]:
                    if T[w].dist == None:
                        T[w].dist = currDist + 1
                        T[w].path = v
        currDist += 1
    return T

adjacencyList = makeAdjacencyList()
T = findShortestPathInUnweightedGraph(adjacencyList)
                    
dct = {}    

for vrtx, attrs in T.iteritems():
    dct.setdefault(attrs.dist, [])
    dct[attrs.dist].append(vrtx)
        

print dct

for vrtx, attrs in T.iteritems():
    print vrtx, attrs.known, attrs.dist, attrs.path

{0: [3], 1: [1, 6], 2: [2, 4], 3: [5, 7]}
1 True 1 3
2 True 2 1
3 True 0 None
4 True 2 1
5 True 3 2
6 True 1 3
7 True 3 4